@article{20218, abstract = {Humanity has long sought inspiration from nature to innovate materials and devices. As science advances, nature-inspired materials are becoming part of our lives. Animate materials, characterized by their activity, adaptability, and autonomy, emulate properties of living systems. While only biological materials fully embody these principles, artificial versions are advancing rapidly, promising transformative impacts in the circular economy, health and climate resilience within a generation. This roadmap presents authoritative perspectives on animate materials across different disciplines and scales, highlighting their interdisciplinary nature and potential applications in diverse fields including nanotechnology, robotics and the built environment. It underscores the need for concerted efforts to address shared challenges such as complexity management, scalability, evolvability, interdisciplinary collaboration, and ethical and environmental considerations. The framework defined by classifying materials based on their level of animacy can guide this emerging field to encourage cooperation and responsible development. By unravelling the mysteries of living matter and leveraging its principles, we can design materials and systems that will transform our world in a more sustainable manner.}, author = {Volpe, Giorgio and Araújo, Nuno A.M. and Guix, Maria and Miodownik, Mark and Martin, Nicolas and Alvarez, Laura and Simmchen, Juliane and Leonardo, Roberto Di and Pellicciotta, Nicola and Martinet, Quentin and Palacci, Jérémie A and Ng, Wai Kit and Saxena, Dhruv and Sapienza, Riccardo and Nadine, Sara and Mano, João F. and Mahdavi, Reza and Beck Adiels, Caroline and Forth, Joe and Santangelo, Christian and Palagi, Stefano and Seok, Ji Min and Webster-Wood, Victoria A. and Wang, Shuhong and Yao, Lining and Aghakhani, Amirreza and Barois, Thomas and Kellay, Hamid and Coulais, Corentin and Van Hecke, Martin and Pierce, Christopher J. and Wang, Tianyu and Chong, Baxi and Goldman, Daniel I. and Reina, Andreagiovanni and Trianni, Vito and Volpe, Giovanni and Beckett, Richard and Nair, Sean P. and Armstrong, Rachel}, issn = {1361-648X}, journal = {Journal of Physics Condensed Matter}, number = {33}, publisher = {IOP Publishing}, title = {{Roadmap for animate matter}}, doi = {10.1088/1361-648X/adebd3}, volume = {37}, year = {2025}, } @article{20219, abstract = {Reproduction is a fundamental biological process, with organisms reproducing sexually, asexually, and, in some cases, utilizing both modes of reproduction within the same population. Does the ability to reproduce through a combination of asexual and sexual modes offer an evolutionary advantage over relying on either mode alone? Here, we introduce an empirically driven theoretical model to examine the dynamics and interplay between sexual and asexual reproduction in stick insect populations. We analyse it using a novel phase transition approach and corroborate it using published experimental data. We find that the presence of males can either increase or decrease the overall population size. However, maintaining an optimal ratio of parthenogenetic to sexual reproduction is crucial for male resilience, effectively delaying male extinction. Conversely, extreme levels of parthenogenetic reproduction—whether too high or too low—can lead to male extinction, emphasizing the need for a balanced number of virgin females to ensure the persistence of males. Our model also explains male absence in Carausius morosus and persistence in Extatosoma tiaratum. Our findings provide valuable insights into the interplay of reproductive strategies and contribute to broader discussions on the transitions between sexual and asexual reproduction.}, author = {Ayalon, Oran and Rajendran, Harikrishnan}, issn = {1742-5662}, journal = {Journal of the Royal Society Interface}, number = {229}, publisher = {The Royal Society}, title = {{Interplay of asexual and sexual reproduction in bifunctional insects}}, doi = {10.1098/rsif.2025.0202}, volume = {22}, year = {2025}, } @article{20220, abstract = {Stress granules (SG) are biomolecular condensates that represent an adaptive response of cells to various stresses, including heat. However, the cell type–specific function and relevance of SG formation, especially during reproductive development, are largely not understood. Here, we show that the meiotic A-type cyclin TARDY ASYNCHRONOUS MEIOSIS (TAM) is recruited to SGs in male meiocytes of Arabidopsis after exposure to heat. We find that the amino terminus of TAM is necessary and sufficient for the localization of proteins to meiotic SGs. Swapping the amino terminus of TAM with the one of its sister protein CYCA1;1 resulted in a separation-of-function allele of TAM, which prevents the partitioning of TAM to SGs while restoring a wild-type phenotype in a tam mutant background under nonheat stress conditions. Notably, plants expressing this TAM version prematurely terminate meiosis under heat resulting in unreduced gametes. Thus, the formation of TAM-containing SGs is necessary for genome stability under heat stress.}, author = {De Jaeger-Braet, Joke G and Hartmann, Merle and Böttger, Lev and Yang, Chao and Hamada, Takahiro and Hoth, Stefan and Feng, Xiaoqi and Weingartner, Magdalena and Schnittger, Arp}, issn = {2375-2548}, journal = {Science Advances}, number = {32}, pages = {eadr5694}, publisher = {AAAS}, title = {{The recruitment of the A-type cyclin TAM to stress granules is crucial for meiotic fidelity under heat}}, doi = {10.1126/sciadv.adr5694}, volume = {11}, year = {2025}, } @article{20221, abstract = {We describe the design, synthesis, and single-molecule junction conductance of π-electron molecules bearing both radial and linear π-conjugation pathways, whereby cycloparaphenylene (CPP) radial cores are π-extended linearly with aryl alkyne substituents as models for previously reported CPP-arylene ethynylene conjugated polymers. Although radially and linearly conjugated molecules have been studied previously in isolation as junction-bridging molecular electronic units, this is the first study to examine molecules where both topologies are operative. Our results reveal that the presence of radial CPP components within the junction-spanning pathway leads to a reduction in the conductance of the backbone compared to model linear phenyl substituents. Through tight-binding and DFT-based calculations, we attribute this conductance change to intramolecular van der Waals (vdW) interactions between the CPP ring and the junction-spanning arylene-ethynylene molecular backbone. These interactions induce changes in the dihedral angles of the backbone, leading to a reduced overlap of π orbitals within the molecular junction.}, author = {Shi, Wanzhuo and Wang, Mengjiao and Venkataraman, Latha and Tovar, John D.}, issn = {1530-6992}, journal = {Nano Letters}, number = {31}, pages = {12101--12106}, publisher = {American Chemical Society}, title = {{Single-molecule conductance through hybrid radially and linearly π-conjugated macromolecules reveals an unusual intramolecular π-interaction}}, doi = {10.1021/acs.nanolett.5c03693}, volume = {25}, year = {2025}, } @article{20222, abstract = {Let X be a smooth projective hypersurface defined over Q. We provide new bounds for rational points of bounded height on X. In particular, we show that if X is a smooth projective hypersurface in Pn with n 4 and degree d 50, then the set of rational points on X of height bounded by B have cardinality On,d,ε (Bn−2+ε ). If X is smooth and has degree d 6, we improve the dimension growth conjecture bound. We achieve an analogue result for affine hypersurfaces whose projective closure is smooth.}, author = {Verzobio, Matteo}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {16}, publisher = {Oxford University Press}, title = {{Counting rational points on smooth hypersurfaces with high degree}}, doi = {10.1093/imrn/rnaf249}, volume = {2025}, year = {2025}, } @article{20223, abstract = {The first influential hypothesis for sex chromosome evolution was proposed in 1914 by H. J. Muller, who argued that once recombination was suppressed between the X and Y chromosomes, Y-linked genes become “sheltered” from selection, leading to accumulation of recessive loss-of-function (LOF) mutations and decay of Y-linked genes. The hypothesis fell out of favor in the 1970s because early mathematical models failed to support it and data on the dominance of lethal mutations were viewed as incompatible with the hypothesis. We reevaluate the main arguments against Muller's hypothesis and find that they do not conclusively exclude a role for sheltering in sex chromosome evolution. By relaxing restrictive assumptions of earlier models, we show that sheltering promotes fixation of LOF mutations with sexually dimorphic fitness effects, resulting in decay of X-linked genes that are exclusively expressed by males and Y-linked genes that are primarily, though not necessarily exclusively, expressed by females. We further show that drift and other processes contributing to Y degeneration (i.e. selective interference and regulatory evolution) expand conditions of Y-linked gene loss by sheltering. The actual contribution of sheltering to sex chromosome evolution hinges upon the distribution of dominance and sex-specific fitness effects of LOF mutations, which we discuss.}, author = {Mrnjavac, Andrea and Vicoso, Beatriz and Connallon, Tim}, issn = {1537-1719}, journal = {Molecular Biology and Evolution}, number = {8}, publisher = {Oxford University Press}, title = {{An extension of Muller's sheltering hypothesis for the evolution of sex chromosome gene content}}, doi = {10.1093/molbev/msaf177}, volume = {42}, year = {2025}, } @inproceedings{20224, abstract = {Traffic in datacenters may follow some pattern: some pairs of servers communicate more frequently than others. Demand-oblivious networks may perform poorly for such workloads, and demand-aware networks optimized for traffic should be used instead. Unfortunately, not all shapes of networks are feasible in real hardware. Practical limitations are usually provided in the form of a topology. For example, a network may be required to be a binary tree, a bounded-degree graph or a Fat tree. In this work, we consider a topology of a binary tree, one of the most fundamental network topologies. We show that already finding an optimal demand-aware binary tree network is NP-hard. Then, we explore how various optimization techniques, including simple local searches, as well as deterministic mutation and crossover operators, cope with generating efficient tree networks on real-life and synthetic workloads.}, author = {Martynov, Pavel and Buzdalov, Maxim and Pankratov, Sergei and Aksenov, Vitaliy and Schmid, Stefan}, booktitle = {Proceedings of the 2025 Genetic and Evolutionary Computation Conference}, isbn = {9798400714658}, location = {Malaga, Spain}, pages = {249--257}, publisher = {Association for Computing Machinery}, title = {{In the search of optimal tree networks: Hardness and heuristics}}, doi = {10.1145/3712256.3726425}, year = {2025}, } @inproceedings{20225, abstract = {We present the first supermartingale certificate for quantitative -regular properties of discrete-time infinite-state stochastic systems. Our certificate is defined on the product of the stochastic system and a limit-deterministic Büchi automaton that specifies the property of interest; hence we call it a limit-deterministic Büchi supermartingale (LDBSM). Previously known supermartingale certificates applied only to quantitative reachability, safety, or reach-avoid properties, and to qualitative (i.e., probability 1) -regular properties.We also present fully automated algorithms for the template-based synthesis of LDBSMs, for the case when the stochastic system dynamics and the controller can be represented in terms of polynomial inequalities. Our experiments demonstrate the ability of our method to solve verification and control tasks for stochastic systems that were beyond the reach of previous supermartingale-based approaches.}, author = {Henzinger, Thomas A and Mallik, Kaushik and Sadeghi, Pouya and Zikelic, Dorde}, booktitle = {37th International Conference on Computer Aided Verification}, isbn = {9783031986789}, issn = {1611-3349}, location = {Zagreb, Croatia}, pages = {29--55}, publisher = {Springer Nature}, title = {{Supermartingale certificates for quantitative omega-regular verification and control}}, doi = {10.1007/978-3-031-98679-6_2}, volume = {15932}, year = {2025}, } @article{20249, abstract = {We develop a heuristic for the density of integer points on affine cubic surfaces. Our heuristic applies to smooth surfaces defined by cubic polynomials that are log K3, but it can also be adjusted to handle singular cubic surfaces. We compare our heuristic to Heath-Brown’s prediction for sums of three cubes, as well as to asymptotic formulae in the literature around Zagier’s work on the Markoff cubic surface, and work of Baragar and Umeda on further surfaces of Markoff-type. We also test our heuristic against numerical data for several families of cubic surfaces.}, author = {Browning, Timothy D and Wilsch, Florian Alexander}, issn = {1420-9020}, journal = {Selecta Mathematica New Series}, number = {4}, publisher = {Springer Nature}, title = {{Integral points on cubic surfaces: heuristics and numerics}}, doi = {10.1007/s00029-025-01074-1}, volume = {31}, year = {2025}, } @article{20250, abstract = {Population III stars are possible precursors to early supermassive black holes (BHs). The presence of soft UV Lyman–Werner (LW) background radiation can suppress Population III star formation in minihaloes and allow them to form in pristine atomic-cooling haloes. In the absence of molecular hydrogen (⁠H2⁠) cooling, atomic-cooling haloes enable rapid collapse with suppressed fragmentation. High background LW fluxes from preceding star-formation have been proposed to dissociate H2⁠. This flux can be supplemented by LW radiation from one or more Population III star(s) in the same halo, reducing the necessary background level. Here, we consider atomic-cooling haloes in which multiple protostellar cores form close to one another nearly simultaneously. We assess whether the first star’s LW radiation can dissociate nearby ⁠, enabling rapid accretion on to a nearby protostellar core, and the prompt formation of a second, supermassive star (SMS) from warm, atomically-cooled gas. We use a set of hydrodynamical simulations with the code enzo, with identical LW backgrounds centred on a halo with two adjacent collapsing gas clumps. When an additional large local LW flux is introduced, we observe immediate reductions in both the accretion rates and the stellar masses that form within these clumps. While the LW flux reduces the H2 fraction and increases the gas temperature, the halo core’s potential well is too shallow to promptly heat the gas to >1000 K and increase the second protostar’s accretion rate. We conclude that this internal LW feedback scenario is unlikely to facilitate SMS or massive BH seed formation.}, author = {Sullivan, James and Haiman, Zoltán and Kulkarni, Mihir and Visbal, Eli}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, number = {2}, pages = {822--838}, publisher = {Oxford University Press}, title = {{Can supermassive stars form in protogalaxies due to internal Lyman-Werner feedback?}}, doi = {10.1093/mnras/staf1269}, volume = {542}, year = {2025}, } @article{20251, abstract = {The Lane–Emden inequality controls (math. formular) in terms of the L^1 and L^p norms of p. We provide a remainder estimate for this inequality in terms of a suitable distance of p to the manifold of optimizers.}, author = {Carlen, Eric and Lewin, Mathieu and Lieb, Elliott H. and Seiringer, Robert}, issn = {1432-0835}, journal = {Calculus of Variations and Partial Differential Equations}, number = {7}, publisher = {Springer Nature}, title = {{Stability estimate for the Lane–Emden inequality}}, doi = {10.1007/s00526-025-03062-x}, volume = {64}, year = {2025}, } @article{20252, abstract = {Zirconia nanocrystals (ZrO2 NCs) are a stable host material for lanthanides, but their performance lags behind that of the leading NaYF4 nanomaterials. Here, we leverage surface chemistry and core/shell architectures to uncover the contribution of dopants at the nanocrystal surface and of dopants in the nanocrystal bulk. We first assess the doping efficiency by ICP and find that, while Eu is almost quantitatively incorporated, the other lanthanides (La, Ce, Tb, Tm, Er, Yb) have about 50% incorporation efficiency over the studied doping range of 1–10%. We then determine the nanocrystal surface chemistry using NMR spectroscopy, despite the additional spectral line broadening caused by the paramagnetic lanthanide dopants. By varying the surface ligands and measuring the photoluminescence, we resolve the spectroscopic signals that are sensitive to a change in surface chemistry. Time-resolved emission spectra further reinforce the notion of a bulk component with a long luminescent lifetime and a surface component with a fast lifetime. Upon shelling Eu- or Tb-doped zirconia NCs with pure zirconia, the surface component disappears, and the photoluminescence quantum yield increases. We further functionalized the surface of the core/shell particles with oleylphosphonic acid ligands to obtain excellent dispersibility. These results show that lanthanide-doped zirconia NCs can be engineered to eliminate deactivation pathways.}, author = {Reichholf, Nico and Horta, Sharona and Van Der Heggen, David and Seno, Carlotta and Pulparayil Mathew, Jikson and Ibáñez, Maria and Smet, Philippe F. and De Roo, Jonathan}, issn = {1936-086X}, journal = {ACS Nano}, number = {33}, pages = {30371--30382}, publisher = {American Chemical Society}, title = {{Identification and elimination of surface emission in lanthanide (Co)doped zirconia nanocrystals}}, doi = {10.1021/acsnano.5c09137}, volume = {19}, year = {2025}, } @inproceedings{20253, abstract = {A quantitative word automaton (QWA) defines a function from infinite words to values. For example, every infinite run of a limit-average QWA 𝒜 obtains a mean payoff, and every word w ∈ Σ^ω is assigned the maximal mean payoff obtained by nondeterministic runs of 𝒜 over w. We introduce quantitative language automata (QLAs) that define functions from language generators (i.e., implementations) to values, where a language generator can be nonprobabilistic, defining a set of infinite words, or probabilistic, defining a probability measure over infinite words. A QLA consists of a QWA and an aggregator function. For example, given a QWA 𝒜, the infimum aggregator maps each language L ⊆ Σ^ω to the greatest lower bound assigned by 𝒜 to any word in L. For boolean value sets, QWAs define boolean properties of traces, and QLAs define boolean properties of sets of traces, i.e., hyperproperties. For more general value sets, QLAs serve as a specification language for a generalization of hyperproperties, called quantitative hyperproperties. A nonprobabilistic (resp. probabilistic) quantitative hyperproperty assigns a value to each set (resp. distribution) G of traces, e.g., the minimal (resp. expected) average response time exhibited by the traces in G. We give several examples of quantitative hyperproperties and investigate three paradigmatic problems for QLAs: evaluation, nonemptiness, and universality. In the evaluation problem, given a QLA 𝔸 and an implementation G, we ask for the value that 𝔸 assigns to G. In the nonemptiness (resp. universality) problem, given a QLA 𝔸 and a value k, we ask whether 𝔸 assigns at least k to some (resp. every) language. We provide a comprehensive picture of decidability for these problems for QLAs with common aggregators as well as their restrictions to ω-regular languages and trace distributions generated by finite-state Markov chains.}, author = {Henzinger, Thomas A and Kebis, Pavol and Mazzocchi, Nicolas Adrien and Sarac, Naci E}, booktitle = {36th International Conference on Concurrency Theory}, isbn = {9783959773898}, issn = {1868-8969}, location = {Aarhus, Denmark}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Quantitative language automata}}, doi = {10.4230/LIPIcs.CONCUR.2025.21}, volume = {348}, year = {2025}, } @article{20255, abstract = {With stunning clarity, the JWST has revealed the Universe’s first billion years. The scientific community is analysing a wealth of JWST imaging and spectroscopic data from that era, and is in the process of rewriting the astronomy textbooks. Here, as a result of the 2024 ISSI Breakthrough Workshop, we provide a snapshot of the great progress made towards understanding the initial chapters of our cosmic history 1.5 years into the JWST science mission. We present the current census of early galaxies, their luminosities, appearance, chemical composition, masses and formation histories as revealed by JWST. We relate the discovery of massive black holes in early galaxies and discuss their demographics and implications for their formations and growth. We conclude by describing the potential sources of reionization and our current understanding of how the Universe became fully ionized. Throughout the Perspective, we highlight discoveries and breakthroughs, topics and issues that are not yet understood, and questions that will be addressed in the coming years, as JWST continues its revolutionary observations of the early Universe.}, author = {Adamo, Angela and Atek, Hakim and Bagley, Micaela B. and Bañados, Eduardo and Barrow, Kirk S.S. and Berg, Danielle A. and Bezanson, Rachel and Bradač, Maruša and Brammer, Gabriel and Carnall, Adam C. and Chisholm, John and Coe, Dan and Dayal, Pratika and Eisenstein, Daniel J. and Eldridge, Jan J. and Ferrara, Andrea and Fujimoto, Seiji and Graaff, Anna De and Habouzit, Melanie and Hutchison, Taylor A. and Kartaltepe, Jeyhan S. and Kassin, Susan A. and Kriek, Mariska and Labbé, Ivo and Maiolino, Roberto and Marques-Chaves, Rui and Maseda, Michael V. and Mason, Charlotte and Matthee, Jorryt J and Mcquinn, Kristen B.W. and Meynet, Georges and Naidu, Rohan P. and Oesch, Pascal A. and Pentericci, Laura and Pérez-González, Pablo G. and Rigby, Jane R. and Roberts-Borsani, Guido and Schaerer, Daniel and Shapley, Alice E. and Stark, Daniel P. and Stiavelli, Massimo and Strom, Allison L. and Vanzella, Eros and Wang, Feige and Wilkins, Stephen M. and Williams, Christina C. and Willott, Chris J. and Wylezalek, Dominika and Nota, Antonella}, issn = {2397-3366}, journal = {Nature Astronomy}, number = {8}, pages = {1134--1147}, publisher = {Springer Nature}, title = {{The first billion years according to JWST}}, doi = {10.1038/s41550-025-02624-5}, volume = {9}, year = {2025}, } @inproceedings{20256, abstract = {We study the problem of predictive runtime monitoring of black-box dynamical systems with quantitative safety properties. The black-box setting stipulates that the exact semantics of the dynamical system and the controller are unknown, and that we are only able to observe the state of the controlled (aka, closed-loop) system at finitely many time points. We present a novel framework for predicting future states of the system based on the states observed in the past. The numbers of past states and of predicted future states are parameters provided by the user. Our method is based on a combination of Taylor’s expansion and the backward difference operator for numerical differentiation. We also derive an upper bound on the prediction error under the assumption that the system dynamics and the controller are smooth. The predicted states are then used to predict safety violations ahead in time. Our experiments demonstrate practical applicability of our method for complex black-box systems, showing that it is computationally lightweight and yet significantly more accurate than the state-of-the-art predictive safety monitoring techniques.}, author = {Henzinger, Thomas A and Kresse, Fabian and Mallik, Kaushik and Yu, Zhengqi and Zikelic, Dorde}, booktitle = {7th Annual Learning for Dynamics & Control Conference}, issn = {2640-3498}, location = {Ann Arbor, MI, United States}, pages = {804--816}, publisher = {ML Research Press}, title = {{Predictive monitoring of black-box dynamical systems}}, volume = {283}, year = {2025}, } @article{20259, abstract = {Cell migration in narrow microenvironments occurs in numerous physiological processes. It involves successive cycles of confinement and release that drive important morphological changes. However, it remains unclear whether migrating cells can retain a memory of their past morphological states that could potentially facilitate their navigation through confined spaces. We demonstrate that local geometry governs a switch between two cell morphologies, thereby facilitating cell passage through long and narrow gaps. We combined cell migration assays on standardized microsystems with biophysical modelling and biochemical perturbations to show that migrating cells have a long-term memory of past confinement events. The morphological cell states correlate across transitions through actin cortex remodelling. These findings indicate that mechanical memory in migrating cells plays an active role in their migratory potential in confined environments.}, author = {Kalukula, Yohalie and Luciano, Marine and Simanov, Gleb and Charras, Guillaume and Brückner, David and Gabriele, Sylvain}, issn = {1745-2481}, journal = {Nature Physics}, pages = {1451--1461}, publisher = {Springer Nature}, title = {{The actin cortex acts as a mechanical memory of morphology in confined migrating cells}}, doi = {10.1038/s41567-025-02980-z}, volume = {21}, year = {2025}, } @inproceedings{20290, abstract = {We consider equilibria in multiplayer stochastic graph games with terminal-node rewards. In such games, Nash equilibria are defined assuming that each player seeks to maximise their expected payoff, ignoring their aversion or tolerance to risk. We therefore study risk-sensitive equilibria (RSEs), where the expected payoff is replaced by a risk measure. A classical risk measure in the literature is the entropic risk measure, where each player has a real valued parameter capturing their risk-averseness. We introduce the extreme risk measure, which corresponds to extreme cases of entropic risk measure, where players are either extreme optimists or extreme pessimists. Under extreme risk measure, every player is an extremist: an extreme optimist perceives their reward as the maximum payoff that can be achieved with positive probability, while an extreme pessimist expects the minimum payoff achievable with positive probability. We argue that the extreme risk measure, especially in multi-player graph based settings, is particularly relevant as they can model several real life instances such as interactions between secure systems and potential security threats, or distributed controls for safety critical systems. We prove that RSEs defined with the extreme risk measure are guaranteed to exist when all rewards are non-negative. Furthermore, we prove that the problem of deciding whether a given game contains an RSE that generates risk measures within specified intervals is decidable and NP-complete for our extreme risk measure, and even PTIME-complete when all players are extreme optimists, while that same problem is undecidable using the entropic risk measure or even the classical expected payoff. This establishes, to our knowledge, the first decidable fragment for equilibria in simple stochastic games without restrictions on strategy types or number of players.}, author = {Brice, Léonard and Henzinger, Thomas A and Thejaswini, K. S.}, booktitle = {50th International Symposium on Mathematical Foundations of Computer Science}, isbn = {9783959773881}, issn = {1868-8969}, location = {Warsaw, Poland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Finding equilibria: Simpler for pessimists, simplest for optimists}}, doi = {10.4230/LIPIcs.MFCS.2025.30}, volume = {345}, year = {2025}, } @inproceedings{20291, abstract = {We define and study classes of ω-regular automata for which the nondeterminism can be resolved by a policy that uses a combination of memory and randomness on any input word, based solely on the prefix read so far. We examine two settings for providing the input word to an automaton. In the first setting, called adversarial resolvability, the input word is constructed letter-by-letter by an adversary, dependent on the resolver’s previous decisions. In the second setting, called stochastic resolvability, the adversary pre-commits to an infinite word and reveals it letter-by-letter. In each setting, we require the existence of an almost-sure resolver, i.e., a policy that ensures that as long as the adversary provides a word in the language of the underlying nondeterministic automaton, the run constructed by the policy is accepting with probability 1. The class of automata that are adversarially resolvable is the well-studied class of history-deterministic automata. The case of stochastically resolvable automata, on the other hand, defines a novel class. Restricting the class of resolvers in both settings to stochastic policies without memory introduces two additional new classes of automata. We show that the new automata classes offer interesting trade-offs between succinctness, expressivity, and computational complexity, providing a fine gradation between deterministic automata and nondeterministic automata.}, author = {Henzinger, Thomas A and Prakash, Aditya and Thejaswini, K. S.}, booktitle = {50th International Symposium on Mathematical Foundations of Computer Science}, isbn = {9783959773881}, issn = {1868-8969}, location = {Warsaw, Poland}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Resolving nondeterminism with randomness}}, doi = {10.4230/LIPIcs.MFCS.2025.57}, volume = {345}, year = {2025}, } @inproceedings{20292, abstract = {In automated decision-making, it is desirable that outputs of decision-makers be robust to slight perturbations in their inputs, a property that may be called input-output robustness. Input-output robustness appears in various different forms in the literature, such as robustness of AI models to adversarial or semantic perturbations and individual fairness of AI models that make decisions about humans. We propose runtime monitoring of input-output robustness of deployed, black-box AI models, where the goal is to design monitors that would observe one long execution sequence of the model, and would raise an alarm whenever it is detected that two similar inputs from the past led to dissimilar outputs. This way, monitoring will complement existing offline ''robustification'' approaches to increase the trustworthiness of AI decision-makers. We show that the monitoring problem can be cast as the fixed-radius nearest neighbor (FRNN) search problem, which, despite being well-studied, lacks suitable online solutions. We present our tool Clemont, which offers a number of lightweight monitors, some of which use upgraded online variants of existing FRNN algorithms, and one uses a novel algorithm based on binary decision diagrams--a data-structure commonly used in software and hardware verification. We have also developed an efficient parallelization technique that can substantially cut down the computation time of monitors for which the distance between input-output pairs is measured using the L∞norm. Using standard benchmarks from the literature of adversarial and semantic robustness and individual fairness, we perform a comparative study of different monitors in Clemont, and demonstrate their effectiveness in correctly detecting robustness violations at runtime.}, author = {Gupta, Ashutosh and Henzinger, Thomas A and Kueffner, Konstantin and Mallik, Kaushik and Pape, David}, booktitle = {Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining}, isbn = {9798400714542}, issn = {2154-817X}, location = {Toronto, Canada}, pages = {790--801}, publisher = {Association for Computing Machinery}, title = {{Monitoring robustness and individual fairness}}, doi = {10.1145/3711896.3737054}, volume = {2}, year = {2025}, } @article{20293, abstract = {Motivated by questions arising at the intersection of information theory and geometry, we compare two dissimilarity measures between finite categorical distributions. One is the well-known Jensen–Shannon divergence, which is easy to compute and whose square root is a proper metric. The other is what we call the minmax divergence, which is harder to compute. Just like the Jensen–Shannon divergence, it arises naturally from the Kullback–Leibler divergence. The main contribution of this paper is a proof showing that the minmax divergence can be tightly approximated by the Jensen–Shannon divergence. The bounds suggest that the square root of the minmax divergence is a metric, and we prove that this is indeed true in the one-dimensional case. The general case remains open. Finally, we consider analogous questions in the context of another Bregman divergence and the corresponding Burbea–Rao (Jensen–Bregman) divergence.}, author = {Akopyan, Arseniy and Edelsbrunner, Herbert and Virk, Ziga and Wagner, Hubert}, issn = {1099-4300}, journal = {Entropy}, number = {8}, publisher = {MDPI}, title = {{Tight bounds between the Jensen–Shannon divergence and the minmax divergence}}, doi = {10.3390/e27080854}, volume = {27}, year = {2025}, }