@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{20254,
  abstract     = {We examine population structures for their ability to maintain diversity in neutral evolution. We use the general framework of evolutionary graph theory and consider birth–death (bd) and death–birth (db) updating. The population is of size N. Initially all individuals represent different types. The basic question is: what is the time TN until one type takes over the population? This time is known as consensus time in computer science and as total coalescent time in evolutionary biology. For the complete graph, it is known that TN is quadratic in N for db and bd. For the cycle, we prove that TN is cubic in N for db and bd. For the star, we prove that TN is cubic for bd and quasilinear (N log N) for db. For the double star, we show that TN is quartic for bd. We derive upper and lower bounds for all undirected graphs for bd and db. We also show the Pareto front of graphs (of size N = 8) that maintain diversity the longest for bd and db. Further, we show that some graphs that quickly homogenize can maintain high levels of diversity longer than graphs that slowly homogenize. For directed graphs, we give simple contracting star-like structures that have superexponential time scales for maintaining diversity.},
  author       = {Brewster, David A. and Svoboda, Jakub and Roscow, Dylan and Chatterjee, Krishnendu and Tkadlec, Josef and Nowak, Martin A.},
  issn         = {2752-6542},
  journal      = {PNAS Nexus},
  number       = {8},
  publisher    = {Oxford University Press},
  title        = {{Maintaining diversity in structured populations}},
  doi          = {10.1093/pnasnexus/pgaf252},
  volume       = {4},
  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{20258,
  abstract     = {The specific introduction of ^1H-^13C or ^1H-^15N moieties into otherwise deuterated proteins holds great potential for high-resolution solution and magic-angle spinning (MAS) NMR studies of protein structure and dynamics. Arginine residues play key roles for example at active sites of enzymes. Taking advantage of a chemically synthesized Arg with a ^13C-^1H2 group in an otherwise deuterated backbone, we demonstrate here the usefulness of proton-detected MAS NMR approaches to probe arginine dynamics. In experiments with crystalline ubiquitin and the 134 kDa tetrameric enzyme malate dehydrogenase we detected a wide range of motions, from sites that are rigid on time scales of at least tens of milliseconds to residues undergoing predominantly nanosecond motions. Spin-relaxation and dipolar-coupling measurements enabled quantitative determination of these dynamics. We observed microsecond dynamics of residue Arg54 in crystalline ubiquitin, whose backbone is known to sample different β-turn conformations on this time scale. The labeling scheme and experiments presented here expand the toolkit for high-resolution proton-detected MAS NMR.},
  author       = {Rohden, Darja and Napoli, Federico and Kapitonova, Anna and Tatman, Benjamin and Lichtenecker, Roman J. and Schanda, Paul},
  issn         = {1089-8638},
  journal      = {Journal of Molecular Biology},
  number       = {23},
  publisher    = {Elsevier},
  title        = {{Arginine dynamics probed by magic-angle spinning NMR with a specific isotope-labeling scheme}},
  doi          = {10.1016/j.jmb.2025.169379},
  volume       = {437},
  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},
}

@article{20289,
  abstract     = {Cell and tissue movement in development, cancer invasion, and immune response relies on chemical or mechanical guidance cues. In many systems, this behavior is locally directed by self-generated signaling gradients rather than long-range, prepatterned cues. However, how heterogeneous mixtures of cells interact nonreciprocally and navigate through self-generated gradients remains largely unexplored. Here, we introduce a theoretical framework for the self-organized chemotaxis of heterogeneous cell populations. We find that the relative chemotactic sensitivities of different cell populations control their long-time coupling and comigration dynamics, with boundary conditions such as external cell and attractant reservoirs substantially influencing the migration patterns. Our model predicts an optimal parameter regime that enables robust and colocalized migration. We test our theoretical predictions with in vitro experiments demonstrating the comigration of distinct immune cell populations, and quantitatively reproduce observed migration patterns under wild-type and perturbed conditions. Interestingly, immune cell comigration occurs close to the predicted optimal regime. Finally, we incorporate mechanical interactions into our framework, revealing a nontrivial interplay between chemotactic and mechanical nonreciprocity in driving collective migration. Together, our findings suggest that self-generated chemotaxis is a robust strategy for the navigation of mixed cell populations.},
  author       = {Ucar, Mehmet C and Zane, Alsberga and Alanko, Jonna H and Sixt, Michael K and Hannezo, Edouard B},
  issn         = {1091-6490},
  journal      = {Proceedings of the National Academy of Sciences},
  number       = {34},
  publisher    = {National Academy of Sciences},
  title        = {{Self-generated chemotaxis of mixed cell populations}},
  doi          = {10.1073/pnas.2504064122},
  volume       = {122},
  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},
}

@article{20294,
  abstract     = {Little Red Dots (LRDs) are compact, point-like sources characterized by their red color and broad Balmer lines; it is a matter of debate whether they are dominated by active galactic nuclei (AGNs) or dusty star-forming galaxies (DSFGs). Here we report two LRDs (ID9094 and ID2756) at zspec > 7 recently discovered in the JWST FRESCO GOODS-North field. Both satisfy the “v-shaped” color and compactness criteria for LRDs and are identified as Type-I AGN candidates based on their broad Hβ emission lines (full width at half maximum: 2280 ± 490 km s−1 for ID9094 and 1070 ± 240 km s−1 for ID2756) and narrow [O III] lines (≃300 − 400 km s−1). To investigate their nature, we conducted deep NOEMA follow-up observations targeting the [C II] 158 μm emission line and the 1.3 mm dust continuum. We do not detect [C II] or 1.3 mm continuum emission for either source. If the two LRDs were DSFGs, we would expect significant detections: > 16σ for [C II] and > 3σ for the 1.3 mm continuum of ID9094, and > 5σ for the [C II] of ID2756. Using the 3σ upper limits of [C II] and 1.3 mm, we performed two analyses: (1) UV-to-far-infrared spectral energy distribution fitting with and without AGN components, and (2) comparison of their properties with the L[C II]–SFRtot empirical relation. Both analyses are consistent with a scenario in which AGN activity contributes to the observed properties, though a dusty star-forming origin cannot be fully ruled out. Our results highlight the importance of far-infrared observations for studying LRDs, a regime that remains largely unexplored.},
  author       = {Xiao, Mengyuan and Oesch, Pascal A. and Bing, Longji and Elbaz, David and Matthee, Jorryt J and Fudamoto, Yoshinobu and Fujimoto, Seiji and Marques-Chaves, Rui and Williams, Christina C. and Dessauges-Zavadsky, Miroslava and Valentino, Francesco and Brammer, Gabriel and Covelo-Paz, Alba and Daddi, Emanuele and Fynbo, Johan P.U. and Gillman, Steven and Ginolfi, Michele and Giovinazzo, Emma and Greene, Jenny E. and Gu, Qiusheng and Illingworth, Garth and Inayoshi, Kohei and Kokorev, Vasily and Meyer, Romain A. and Naidu, Rohan P. and Reddy, Naveen A. and Schaerer, Daniel and Shapley, Alice and Stefanon, Mauro and Steinhardt, Charles L. and Setton, David J. and Vestergaard, Marianne and Wang, Tao},
  issn         = {1432-0746},
  journal      = {Astronomy & Astrophysics},
  publisher    = {EDP Sciences},
  title        = {{No [C II] or dust detection in two Little Red Dots at zspec > 7}},
  doi          = {10.1051/0004-6361/202554361},
  volume       = {700},
  year         = {2025},
}

@article{20295,
  abstract     = {Scanning Kelvin probe microscopy (SKPM) is a powerful technique for macroscopic imaging of the electrostatic potential above a surface. Though most often used to image work-function variations of conductive surfaces, it can also be used to probe the surface charge on insulating surfaces. In both cases, relating the measured potential to the underlying signal is non-trivial. Here, general relationships are derived between the measured SKPM voltage and the underlying source, revealing either can be cast as a convolution with an appropriately scaled point spread function (PSF). For charge that exists on a thin insulating layer above a conductor, the PSF has the same shape as what would occur from a work-function variation alone, differing by a simple scaling factor. This relationship is confirmed by: (1) backing it out from finite-element simulations of work-function and charge signals, and (2) experimentally comparing the measured PSF from a small work-function target to that from a small charge spot. This scaling factor is further validated by comparing SKPM charge measurements with Faraday cup measurements for highly charged samples from contact-charging experiments. These results highlight a heretofore unappreciated connection between SKPM voltage and charge signals, offering a rigorous recipe to extract either from experimental data.},
  author       = {Lenton, Isaac C and Pertl, Felix and Shafeek, Lubuna B and Waitukaitis, Scott R},
  issn         = {2196-7350},
  journal      = {Advanced Materials Interfaces},
  number       = {19},
  publisher    = {Wiley},
  title        = {{A duality between surface charge and work function in scanning Kelvin probe microscopy}},
  doi          = {10.1002/admi.202500521},
  volume       = {12},
  year         = {2025},
}

@inproceedings{20296,
  abstract     = {Learning-based systems are increasingly deployed across various domains, yet the complexity of traditional neural networks poses significant challenges for formal verification. Unlike conventional neural networks, learned Logic Gate Networks (LGNs) replace multiplications with Boolean logic gates, yielding a sparse, netlist-like architecture that is inherently more amenable to symbolic verification, while still delivering promising performance. In this paper, we introduce a SAT encoding for verifying global robustness and fairness in LGNs. We evaluate our method on five benchmark datasets, including a newly constructed 5-class variant, and find that LGNs are both verification-friendly and maintain strong predictive performance.},
  author       = {Kresse, Fabian and Yu, Zhengqi and Lampert, Christoph and Henzinger, Thomas A},
  booktitle    = {2nd International Conferenceon Neuro-Symbolic Systems},
  issn         = {2640-3498},
  location     = {Philadephia, PA, United States},
  publisher    = {ML Research Press},
  title        = {{Logic gate neural networks are good for verification}},
  volume       = {288},
  year         = {2025},
}

@inproceedings{20297,
  abstract     = {A standard model that arises in several applications in sequential decision-making is partially observable Markov decision processes (POMDPs) where a decision-making agent interacts with an uncertain environment. A basic objective in POMDPs is the reachability objective, where given a target set of states, the goal is to eventually arrive at one of them.

The limit-sure problem asks whether reachability can be ensured with probability arbitrarily close to 1. In general, the limit-sure reachability problem for POMDPs is undecidable. However, in many practical cases, the most relevant question is the existence of policies with a small amount of memory. In this work, we study the limit-sure reachability problem for POMDPs with a fixed amount of memory. We establish that the computational complexity of the problem is NP-complete.},
  author       = {Asadi, Ali and Chatterjee, Krishnendu and Saona Urmeneta, Raimundo J and Shafiee, Ali},
  booktitle    = {The 41st Conference on Uncertainty in Artificial Intelligence},
  issn         = {2640-3498},
  location     = {Rio de Janeiro, Brazil},
  pages        = {238--247},
  publisher    = {ML Research Press},
  title        = {{Limit-sure reachability for small memory policies in POMDPs is NP-complete}},
  volume       = {286},
  year         = {2025},
}

@inproceedings{20298,
  abstract     = {In this paper, we study the problem of estimating the unknown mean θ of a unit variance Gaussian distribution in a locally differentially private (LDP) way. In the high-privacy regime (ϵ≤1
), we identify an optimal privacy mechanism that minimizes the variance of the estimator asymptotically. Our main technical contribution is the maximization of the Fisher-Information of the sanitized data with respect to the local privacy mechanism Q. We find that the exact solution Qθ,ϵ of this maximization is the sign mechanism that applies randomized response to the sign of Xi−θ, where X1,…,Xn are the confidential iid original samples. However, since this optimal local mechanism depends on the unknown mean θ, we employ a two-stage LDP parameter estimation procedure which requires splitting agents into two groups. The first n1 observations are used to consistently but not necessarily efficiently estimate the parameter θ by θn1~
. Then this estimate is updated by applying the sign mechanism with θ~n1 instead of θ
 to the remaining n−n1 observations, to obtain an LDP and efficient estimator of the unknown mean.},
  author       = {Kalinin, Nikita and Steinberger, Lukas},
  booktitle    = {Proceedings of the 28th International Conference on Artificial Intelligence and Statistics},
  issn         = {2640-3498},
  location     = {Mai Khao, Thailand},
  pages        = {118--126},
  publisher    = {ML Research Press},
  title        = {{Efficient estimation of a Gaussian mean with local differential privacy}},
  volume       = {258},
  year         = {2025},
}

@inproceedings{20299,
  abstract     = {Deterministic Markov Decision Processes (DMDPs) are a mathematical framework for decision-making where the outcomes and future possible actions are deterministically determined by the current action taken. DMDPs can be viewed as a finite directed weighted graph, where in each step, the controller chooses an outgoing edge. An objective is a measurable function on runs (or infinite trajectories) of the DMDP, and the value for an objective is the maximal cumulative reward (or weight) that the controller can guarantee. We consider the classical mean-payoff (aka limit-average) objective, which is a basic and fundamental objective.

Howard's policy iteration algorithm is a popular method for solving DMDPs with mean-payoff objectives. Although Howard's algorithm performs well in practice, as experimental studies suggested, the best known upper bound is exponential and the current known lower bound is as follows: For the input size I, the algorithm requires (math formular) iterations, where (math formular) hides the poly-logarithmic factors, i.e., the current lower bound on iterations is sub-linear with respect to the input size. Our main result is an improved lower bound for this fundamental algorithm where we show that for the input size I, the algorithm requires (math formular) iterations.},
  author       = {Asadi, Ali and Chatterjee, Krishnendu and De Raaij, Jakob},
  booktitle    = {The 41st Conference on Uncertainty in Artificial Intelligence},
  issn         = {2640-3498},
  location     = {Rio de Janeiro, Brazil},
  pages        = {223--232},
  publisher    = {ML Research Press},
  title        = {{Lower bound on Howard policy iteration for deterministic Markov Decision Processes}},
  volume       = {286},
  year         = {2025},
}

@inproceedings{20300,
  abstract     = {Simultaneously addressing multiple objectives is becoming increasingly important in modern machine learning. At the same time, data is often high-dimensional and costly to label. For a single objective such as prediction risk, conventional regularization techniques are known to improve generalization when the data exhibits low-dimensional structure like sparsity. However, it is largely unexplored how to leverage this structure in the context of multi-objective learning (MOL) with multiple competing objectives. In this work, we discuss how the application of vanilla regularization approaches can fail, and propose a two-stage MOL framework that can successfully leverage low-dimensional structure. We demonstrate its effectiveness experimentally for multi-distribution learning and fairness-risk trade-offs.},
  author       = {Wegel, Tobias and Kovačević, Filip and Ţifrea, Alexandru and Yang, Fanny},
  booktitle    = {The 28th International Conference on Artificial Intelligence and Statistics},
  issn         = {2640-3498},
  location     = {Mai Khao, Thailand},
  pages        = {4591--4599},
  publisher    = {ML Research Press},
  title        = {{Learning Pareto manifolds in high dimensions: How can regularization help?}},
  volume       = {258},
  year         = {2025},
}

@inproceedings{20301,
  abstract     = {We study privately releasing column sums of a d-dimensional table with entries from a universe χ undergoing T row updates, called histogram under continual release. Our mechanisms give better additive ℓ∞-error than existing mechanisms for a large class of queries and input streams. Our first contribution is an output-sensitive mechanism in the insertions-only model (χ = {0, 1}) for maintaining (i) the histogram or (ii) queries that do not require maintaining the entire histogram, such as the maximum or minimum column sum, the median, or any quantiles. The mechanism has an additive error of O(d log2 (dq∗) + log T) whp, where q∗ is the maximum output value over all time steps on this dataset. The mechanism does not require q∗ as input. This breaks the Ω(d log T) bound of prior work when q∗ ≪ T. Our second contribution is a mechanism for the turnstile model that admits negative entry updates (χ = {−1, 0, 1}). This mechanism has an additive error of O(d log2(dK) + log T) whp, where K is the number of times two consecutive data rows differ, and the mechanism does not require K as input. This is useful when monitoring inputs that only vary under unusual circumstances. For d = 1 this gives the first
private mechanism with error O(log2 K + log T) for continual counting in the turnstile model, improving on the O(log2 n + log T) error bound by Dwork et al. (2015), where n is the number of ones in the stream, as well as allowing negative entries, while Dwork et al. (2015) can only handle nonnegative entries (χ = {0, 1}). },
  author       = {Henzinger, Monika H and Sricharan, A. R. and Steiner, Teresa Anna},
  booktitle    = {The 28th International Conference on Artificial Intelligence and Statistics},
  issn         = {2640-3498},
  location     = {Mai Khao, Thailand},
  pages        = {1990--1998},
  publisher    = {ML Research Press},
  title        = {{Differentially private continual release of histograms and related queries}},
  volume       = {258},
  year         = {2025},
}

@inproceedings{20302,
  abstract     = {LocalSGD and SCAFFOLD are widely used methods in distributed stochastic optimization, with numerous applications in machine learning, large-scale data processing, and federated learning. However, rigorously establishing their theoretical advantages over simpler methods, such as minibatch SGD (MbSGD), has proven challenging, as existing analyses often rely on strong assumptions, unrealistic premises, or overly restrictive scenarios.

In this work, we revisit the convergence properties of LocalSGD and SCAFFOLD under a variety of existing or weaker conditions, including gradient similarity, Hessian similarity, weak convexity, and Lipschitz continuity of the Hessian. Our analysis shows that (i) LocalSGD achieves faster convergence compared to MbSGD for weakly convex functions without requiring stronger gradient similarity assumptions; (ii) LocalSGD benefits significantly from higher-order similarity and smoothness; and (iii) SCAFFOLD demonstrates faster convergence than MbSGD for a broader class of non-quadratic functions. These theoretical insights provide a clearer understanding of the conditions under which LocalSGD and SCAFFOLD outperform MbSGD.},
  author       = {Luo, Ruichen and Stich, Sebastian U. and Horváth, Samuel and Takáč, Martin},
  booktitle    = {The 28th International Conference on Artificial Intelligence and Statistics},
  issn         = {2640-3498},
  location     = {Mai Khao, Thailand},
  pages        = {2539--2547},
  publisher    = {ML Research Press},
  title        = {{Revisiting LocalSGD and SCAFFOLD: Improved rates and missing analysis}},
  volume       = {258},
  year         = {2025},
}