@inproceedings{14243, abstract = {Two-player zero-sum "graph games" are central in logic, verification, and multi-agent systems. The game proceeds by placing a token on a vertex of a graph, and allowing the players to move it to produce an infinite path, which determines the winner or payoff of the game. Traditionally, the players alternate turns in moving the token. In "bidding games", however, the players have budgets and in each turn, an auction (bidding) determines which player moves the token. So far, bidding games have only been studied as full-information games. In this work we initiate the study of partial-information bidding games: we study bidding games in which a player's initial budget is drawn from a known probability distribution. We show that while for some bidding mechanisms and objectives, it is straightforward to adapt the results from the full-information setting to the partial-information setting, for others, the analysis is significantly more challenging, requires new techniques, and gives rise to interesting results. Specifically, we study games with "mean-payoff" objectives in combination with "poorman" bidding. We construct optimal strategies for a partially-informed player who plays against a fully-informed adversary. We show that, somewhat surprisingly, the "value" under pure strategies does not necessarily exist in such games.}, author = {Avni, Guy and Jecker, Ismael R and Zikelic, Dorde}, booktitle = {Proceedings of the 37th AAAI Conference on Artificial Intelligence}, isbn = {9781577358800}, location = {Washington, DC, United States}, number = {5}, pages = {5464--5471}, title = {{Bidding graph games with partially-observable budgets}}, doi = {10.1609/aaai.v37i5.25679}, volume = {37}, year = {2023}, } @article{14244, abstract = {In this paper, we determine the motivic class — in particular, the weight polynomial and conjecturally the Poincaré polynomial — of the open de Rham space, defined and studied by Boalch, of certain moduli spaces of irregular meromorphic connections on the trivial rank bundle on P1. The computation is by motivic Fourier transform. We show that the result satisfies the purity conjecture, that is, it agrees with the pure part of the conjectured mixed Hodge polynomial of the corresponding wild character variety. We also identify the open de Rham spaces with quiver varieties with multiplicities of Yamakawa and Geiss–Leclerc–Schröer. We finish with constructing natural complete hyperkähler metrics on them, which in the four-dimensional cases are expected to be of type ALF.}, author = {Hausel, Tamás and Wong, Michael Lennox and Wyss, Dimitri}, issn = {1460-244X}, journal = {Proceedings of the London Mathematical Society}, number = {4}, pages = {958--1027}, publisher = {Wiley}, title = {{Arithmetic and metric aspects of open de Rham spaces}}, doi = {10.1112/plms.12555}, volume = {127}, year = {2023}, } @article{14245, abstract = {We establish effective counting results for lattice points in families of domains in real, complex and quaternionic hyperbolic spaces of any dimension. The domains we focus on are defined as product sets with respect to an Iwasawa decomposition. Several natural diophantine problems can be reduced to counting lattice points in such domains. These include equidistribution of the ratio of the length of the shortest solution (x,y) to the gcd equation bx−ay=1 relative to the length of (a,b), where (a,b) ranges over primitive vectors in a disc whose radius increases, the natural analog of this problem in imaginary quadratic number fields, as well as equidistribution of integral solutions to the diophantine equation defined by an integral Lorentz form in three or more variables. We establish an effective rate of convergence for these equidistribution problems, depending on the size of the spectral gap associated with a suitable lattice subgroup in the isometry group of the relevant hyperbolic space. The main result underlying our discussion amounts to establishing effective joint equidistribution for the horospherical component and the radial component in the Iwasawa decomposition of lattice elements.}, author = {Horesh, Tal and Nevo, Amos}, issn = {1945-5844}, journal = {Pacific Journal of Mathematics}, number = {2}, pages = {265--294}, publisher = {Mathematical Sciences Publishers}, title = {{Horospherical coordinates of lattice points in hyperbolic spaces: Effective counting and equidistribution}}, doi = {10.2140/pjm.2023.324.265}, volume = {324}, year = {2023}, } @article{14246, abstract = {The model of a ring threaded by the Aharonov-Bohm flux underlies our understanding of a coupling between gauge potentials and matter. The typical formulation of the model is based upon a single particle picture, and should be extended when interactions with other particles become relevant. Here, we illustrate such an extension for a particle in an Aharonov-Bohm ring subject to interactions with a weakly interacting Bose gas. We show that the ground state of the system can be described using the Bose-polaron concept—a particle dressed by interactions with a bosonic environment. We connect the energy spectrum to the effective mass of the polaron, and demonstrate how to change currents in the system by tuning boson-particle interactions. Our results suggest the Aharonov-Bohm ring as a platform for studying coherence and few- to many-body crossover of quasi-particles that arise from an impurity immersed in a medium.}, author = {Brauneis, Fabian and Ghazaryan, Areg and Hammer, Hans-Werner and Volosniev, Artem}, issn = {2399-3650}, journal = {Communications Physics}, keywords = {General Physics and Astronomy}, publisher = {Springer Nature}, title = {{Emergence of a Bose polaron in a small ring threaded by the Aharonov-Bohm flux}}, doi = {10.1038/s42005-023-01281-2}, volume = {6}, year = {2023}, } @article{14253, abstract = {Junctions between the endoplasmic reticulum (ER) and the plasma membrane (PM) are specialized membrane contacts ubiquitous in eukaryotic cells. Concentration of intracellular signaling machinery near ER-PM junctions allows these domains to serve critical roles in lipid and Ca2+ signaling and homeostasis. Subcellular compartmentalization of protein kinase A (PKA) signaling also regulates essential cellular functions, however, no specific association between PKA and ER-PM junctional domains is known. Here, we show that in brain neurons type I PKA is directed to Kv2.1 channel-dependent ER-PM junctional domains via SPHKAP, a type I PKA-specific anchoring protein. SPHKAP association with type I PKA regulatory subunit RI and ER-resident VAP proteins results in the concentration of type I PKA between stacked ER cisternae associated with ER-PM junctions. This ER-associated PKA signalosome enables reciprocal regulation between PKA and Ca2+ signaling machinery to support Ca2+ influx and excitation-transcription coupling. These data reveal that neuronal ER-PM junctions support a receptor-independent form of PKA signaling driven by membrane depolarization and intracellular Ca2+, allowing conversion of information encoded in electrical signals into biochemical changes universally recognized throughout the cell.}, author = {Vierra, Nicholas C. and Ribeiro-Silva, Luisa and Kirmiz, Michael and Van Der List, Deborah and Bhandari, Pradeep and Mack, Olivia A. and Carroll, James and Le Monnier, Elodie and Aicher, Sue A. and Shigemoto, Ryuichi and Trimmer, James S.}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Neuronal ER-plasma membrane junctions couple excitation to Ca2+-activated PKA signaling}}, doi = {10.1038/s41467-023-40930-6}, volume = {14}, year = {2023}, } @article{14254, abstract = {In [10] Nam proved a Lieb–Thirring Inequality for the kinetic energy of a fermionic quantum system, with almost optimal (semi-classical) constant and a gradient correction term. We present a stronger version of this inequality, with a much simplified proof. As a corollary we obtain a simple proof of the original Lieb–Thirring inequality.}, author = {Seiringer, Robert and Solovej, Jan Philip}, issn = {1096-0783}, journal = {Journal of Functional Analysis}, number = {10}, publisher = {Elsevier}, title = {{A simple approach to Lieb-Thirring type inequalities}}, doi = {10.1016/j.jfa.2023.110129}, volume = {285}, year = {2023}, } @article{14255, abstract = {Toscana virus is a major cause of arboviral disease in humans in the Mediterranean basin during summer. However, early virus-host cell interactions and entry mechanisms remain poorly characterized. Investigating iPSC-derived human neurons and cell lines, we found that virus binding to the cell surface was specific, and 50% of bound virions were endocytosed within 10 min. Virions entered Rab5a+ early endosomes and, subsequently, Rab7a+ and LAMP-1+ late endosomal compartments. Penetration required intact late endosomes and occurred within 30 min following internalization. Virus entry relied on vacuolar acidification, with an optimal pH for viral membrane fusion at pH 5.5. The pH threshold increased to 5.8 with longer pre-exposure of virions to the slightly acidic pH in early endosomes. Strikingly, the particles remained infectious after entering late endosomes with a pH below the fusion threshold. Overall, our study establishes Toscana virus as a late-penetrating virus and reveals an atypical use of vacuolar acidity by this virus to enter host cells.}, author = {Koch, Jana and Xin, Qilin and Obr, Martin and Schäfer, Alicia and Rolfs, Nina and Anagho, Holda A. and Kudulyte, Aiste and Woltereck, Lea and Kummer, Susann and Campos, Joaquin and Uckeley, Zina M. and Bell-Sakyi, Lesley and Kräusslich, Hans Georg and Schur, Florian Km and Acuna, Claudio and Lozach, Pierre Yves}, issn = {1553-7374}, journal = {PLoS Pathogens}, number = {8}, publisher = {Public Library of Science}, title = {{The phenuivirus Toscana virus makes an atypical use of vacuolar acidity to enter host cells}}, doi = {10.1371/journal.ppat.1011562}, volume = {19}, year = {2023}, } @article{14256, abstract = {Context. Space asteroseismology is revolutionizing our knowledge of the internal structure and dynamics of stars. A breakthrough is ongoing with the recent discoveries of signatures of strong magnetic fields in the core of red giant stars. The key signature for such a detection is the asymmetry these fields induce in the frequency splittings of observed dipolar mixed gravito-acoustic modes. Aims. We investigate the ability of the observed asymmetries of the frequency splittings of dipolar mixed modes to constrain the geometrical properties of deep magnetic fields. Methods. We used the powerful analytical Racah-Wigner algebra used in quantum mechanics to characterize the geometrical couplings of dipolar mixed oscillation modes with various realistically plausible topologies of fossil magnetic fields. We also computed the induced perturbation of their frequencies. Results. First, in the case of an oblique magnetic dipole, we provide the exact analytical expression of the asymmetry as a function of the angle between the rotation and magnetic axes. Its value provides a direct measure of this angle. Second, considering a combination of axisymmetric dipolar and quadrupolar fields, we show how the asymmetry is blind to the unraveling of the relative strength and sign of each component. Finally, in the case of a given multipole, we show that a negative asymmetry is a signature of non-axisymmetric topologies. Conclusions. Asymmetries of dipolar mixed modes provide a key bit of information on the geometrical topology of deep fossil magnetic fields, but this is insufficient on its own. Asteroseismic constraints should therefore be combined with spectropolarimetric observations and numerical simulations, which aim to predict the more probable stable large-scale geometries.}, author = {Mathis, S. and Bugnet, Lisa Annabelle}, issn = {1432-0746}, journal = {Astronomy and Astrophysics}, publisher = {EDP Sciences}, title = {{Asymmetries of frequency splittings of dipolar mixed modes: A window on the topology of deep magnetic fields}}, doi = {10.1051/0004-6361/202346832}, volume = {676}, year = {2023}, } @article{14258, abstract = {There is currently little evidence that the genetic basis of human phenotype varies significantly across the lifespan. However, time-to-event phenotypes are understudied and can be thought of as reflecting an underlying hazard, which is unlikely to be constant through life when values take a broad range. Here, we find that 74% of 245 genome-wide significant genetic associations with age at natural menopause (ANM) in the UK Biobank show a form of age-specific effect. Nineteen of these replicated discoveries are identified only by our modeling framework, which determines the time dependency of DNA-variant age-at-onset associations without a significant multiple-testing burden. Across the range of early to late menopause, we find evidence for significantly different underlying biological pathways, changes in the signs of genetic correlations of ANM to health indicators and outcomes, and differences in inferred causal relationships. We find that DNA damage response processes only act to shape ovarian reserve and depletion for women of early ANM. Genetically mediated delays in ANM were associated with increased relative risk of breast cancer and leiomyoma at all ages and with high cholesterol and heart failure for late-ANM women. These findings suggest that a better understanding of the age dependency of genetic risk factor relationships among health indicators and outcomes is achievable through appropriate statistical modeling of large-scale biobank data.}, author = {Ojavee, Sven E. and Darrous, Liza and Patxot, Marion and Läll, Kristi and Fischer, Krista and Mägi, Reedik and Kutalik, Zoltan and Robinson, Matthew Richard}, issn = {1537-6605}, journal = {American Journal of Human Genetics}, number = {9}, pages = {1549--1563}, publisher = {Elsevier}, title = {{Genetic insights into the age-specific biological mechanisms governing human ovarian aging}}, doi = {10.1016/j.ajhg.2023.07.006}, volume = {110}, year = {2023}, } @inproceedings{14259, abstract = {We provide a learning-based technique for guessing a winning strategy in a parity game originating from an LTL synthesis problem. A cheaply obtained guess can be useful in several applications. Not only can the guessed strategy be applied as best-effort in cases where the game’s huge size prohibits rigorous approaches, but it can also increase the scalability of rigorous LTL synthesis in several ways. Firstly, checking whether a guessed strategy is winning is easier than constructing one. Secondly, even if the guess is wrong in some places, it can be fixed by strategy iteration faster than constructing one from scratch. Thirdly, the guess can be used in on-the-fly approaches to prioritize exploration in the most fruitful directions. In contrast to previous works, we (i) reflect the highly structured logical information in game’s states, the so-called semantic labelling, coming from the recent LTL-to-automata translations, and (ii) learn to reflect it properly by learning from previously solved games, bringing the solving process closer to human-like reasoning.}, author = {Kretinsky, Jan and Meggendorfer, Tobias and Prokop, Maximilian and Rieder, Sabine}, booktitle = {35th International Conference on Computer Aided Verification }, isbn = {9783031377051}, issn = {1611-3349}, location = {Paris, France}, pages = {390--414}, publisher = {Springer Nature}, title = {{Guessing winning policies in LTL synthesis by semantic learning}}, doi = {10.1007/978-3-031-37706-8_20}, volume = {13964}, year = {2023}, } @inproceedings{14260, abstract = {This paper presents Lincheck, a new practical and user-friendly framework for testing concurrent algorithms on the Java Virtual Machine (JVM). Lincheck provides a simple and declarative way to write concurrent tests: instead of describing how to perform the test, users specify what to test by declaring all the operations to examine; the framework automatically handles the rest. As a result, tests written with Lincheck are concise and easy to understand. The framework automatically generates a set of concurrent scenarios, examines them using stress-testing or bounded model checking, and verifies that the results of each invocation are correct. Notably, if an error is detected via model checking, Lincheck provides an easy-to-follow trace to reproduce it, significantly simplifying the bug investigation. To the best of our knowledge, Lincheck is the first production-ready tool on the JVM that offers such a simple way of writing concurrent tests, without requiring special skills or expertise. We successfully integrated Lincheck in the development process of several large projects, such as Kotlin Coroutines, and identified new bugs in popular concurrency libraries, such as a race in Java’s standard ConcurrentLinkedDeque and a liveliness bug in Java’s AbstractQueuedSynchronizer framework, which is used in most of the synchronization primitives. We believe that Lincheck can significantly improve the quality and productivity of concurrent algorithms research and development and become the state-of-the-art tool for checking their correctness.}, author = {Koval, Nikita and Fedorov, Alexander and Sokolova, Maria and Tsitelov, Dmitry and Alistarh, Dan-Adrian}, booktitle = {35th International Conference on Computer Aided Verification }, isbn = {9783031377051}, issn = {1611-3349}, location = {Paris, France}, pages = {156--169}, publisher = {Springer Nature}, title = {{Lincheck: A practical framework for testing concurrent data structures on JVM}}, doi = {10.1007/978-3-031-37706-8_8}, volume = {13964}, year = {2023}, } @article{14261, abstract = {In this work, a generalized, adapted Numerov implementation capable of determining band structures of periodic quantum systems is outlined. Based on the input potential, the presented approach numerically solves the Schrödinger equation in position space at each momentum space point. Thus, in addition to the band structure, the method inherently provides information about the state functions and probability densities in position space at each momentum space point considered. The generalized, adapted Numerov framework provided reliable estimates for a variety of increasingly complex test suites in one, two, and three dimensions. The accuracy of the proposed methodology was benchmarked against results obtained for the analytically solvable Kronig-Penney model. Furthermore, the presented numerical solver was applied to a model potential representing a 2D optical lattice being a challenging application relevant, for example, in the field of quantum computing.}, author = {Gamper, Jakob and Kluibenschedl, Florian and Weiss, Alexander K.H. and Hofer, Thomas S.}, issn = {1948-7185}, journal = {Journal of Physical Chemistry Letters}, number = {33}, pages = {7395--7403}, publisher = {American Chemical Society}, title = {{Accessing position space wave functions in band structure calculations of periodic systems - a generalized, adapted numerov implementation for one-, two-, and three-dimensional quantum problems}}, doi = {10.1021/acs.jpclett.3c01707}, volume = {14}, year = {2023}, } @article{14277, abstract = {Living tissues are characterized by an intrinsically mechanochemical interplay of active physical forces and complex biochemical signaling pathways. Either feature alone can give rise to complex emergent phenomena, for example, mechanically driven glassy dynamics and rigidity transitions, or chemically driven reaction-diffusion instabilities. An important question is how to quantitatively assess the contribution of these different cues to the large-scale dynamics of biological materials. We address this in Madin-Darby canine kidney (MDCK) monolayers, considering both mechanochemical feedback between extracellular signal-regulated kinase (ERK) signaling activity and cellular density as well as a mechanically active tissue rheology via a self-propelled vertex model. We show that the relative strength of active migration forces to mechanochemical couplings controls a transition from a uniform active glass to periodic spatiotemporal waves. We parametrize the model from published experimental data sets on MDCK monolayers and use it to make new predictions on the correlation functions of cellular dynamics and the dynamics of topological defects associated with the oscillatory phase of cells. Interestingly, MDCK monolayers are best described by an intermediary parameter region in which both mechanochemical couplings and noisy active propulsion have a strong influence on the dynamics. Finally, we study how tissue rheology and ERK waves produce feedback on one another and uncover a mechanism via which tissue fluidity can be controlled by mechanochemical waves at both the local and global levels.}, author = {Boocock, Daniel R and Hirashima, Tsuyoshi and Hannezo, Edouard B}, issn = {2835-8279}, journal = {PRX Life}, number = {1}, publisher = {American Physical Society}, title = {{Interplay between mechanochemical patterning and glassy dynamics in cellular monolayers}}, doi = {10.1103/prxlife.1.013001}, volume = {1}, year = {2023}, } @misc{14279, abstract = {The zip file includes source data used in the manuscript "CCR7 acts as both a sensor and a sink for CCL19 to coordinate collective leukocyte migration", as well as a representative Jupyter notebook to reproduce the main figures. Please see the preprint on bioRxiv and the DOI link there to access the final published version. Note the title change between the preprint and the published manuscript. A sample script for particle-based simulations of collective chemotaxis by self-generated gradients is also included (see Self-generated_chemotaxis_sample_script.ipynb) to generate exemplary cell trajectories. A detailed description of the simulation setup is provided in the supplementary information of the manuscipt.}, author = {Ucar, Mehmet C}, publisher = {Zenodo}, title = {{Source data for the manuscript "CCR7 acts as both a sensor and a sink for CCL19 to coordinate collective leukocyte migration"}}, doi = {10.5281/ZENODO.8133960}, year = {2023}, } @article{14313, abstract = {To respond to auxin, the chief orchestrator of their multicellularity, plants evolved multiple receptor systems and signal transduction cascades. Despite decades of research, however, we are still lacking a satisfactory synthesis of various auxin signaling mechanisms. The chief discrepancy and historical controversy of the field is that of rapid and slow auxin effects on plant physiology and development. How is it possible that ions begin to trickle across the plasma membrane as soon as auxin enters the cell, even though the best-characterized transcriptional auxin pathway can take effect only after tens of minutes? Recently, unexpected progress has been made in understanding this and other unknowns of auxin signaling. We provide a perspective on these exciting developments and concepts whose general applicability might have ramifications beyond auxin signaling.}, author = {Fiedler, Lukas and Friml, Jiří}, issn = {1369-5266}, journal = {Current Opinion in Plant Biology}, number = {10}, publisher = {Elsevier}, title = {{Rapid auxin signaling: Unknowns old and new}}, doi = {10.1016/j.pbi.2023.102443}, volume = {75}, year = {2023}, } @article{14314, abstract = {The execution of cognitive functions requires coordinated circuit activity across different brain areas that involves the associated firing of neuronal assemblies. Here, we tested the circuit mechanism behind assembly interactions between the hippocampus and the medial prefrontal cortex (mPFC) of adult rats by recording neuronal populations during a rule-switching task. We identified functionally coupled CA1-mPFC cells that synchronized their activity beyond that expected from common spatial coding or oscillatory firing. When such cell pairs fired together, the mPFC cell strongly phase locked to CA1 theta oscillations and maintained consistent theta firing phases, independent of the theta timing of their CA1 counterpart. These functionally connected CA1-mPFC cells formed interconnected assemblies. While firing together with their CA1 assembly partners, mPFC cells fired along specific theta sequences. Our results suggest that upregulated theta oscillatory firing of mPFC cells can signal transient interactions with specific CA1 assemblies, thus enabling distributed computations.}, author = {Nardin, Michele and Käfer, Karola and Stella, Federico and Csicsvari, Jozsef L}, issn = {2211-1247}, journal = {Cell Reports}, number = {9}, publisher = {Elsevier}, title = {{Theta oscillations as a substrate for medial prefrontal-hippocampal assembly interactions}}, doi = {10.1016/j.celrep.2023.113015}, volume = {42}, year = {2023}, } @article{14315, abstract = {During apoptosis, caspases degrade 8 out of ~30 nucleoporins to irreversibly demolish the nuclear pore complex. However, for poorly understood reasons, caspases are also activated during cell differentiation. Here, we show that sublethal activation of caspases during myogenesis results in the transient proteolysis of four peripheral Nups and one transmembrane Nup. ‘Trimmed’ NPCs become nuclear export-defective, and we identified in an unbiased manner several classes of cytoplasmic, plasma membrane, and mitochondrial proteins that rapidly accumulate in the nucleus. NPC trimming by non-apoptotic caspases was also observed in neurogenesis and endoplasmic reticulum stress. Our results suggest that caspases can reversibly modulate nuclear transport activity, which allows them to function as agents of cell differentiation and adaptation at sublethal levels.}, author = {Cho, Ukrae H. and Hetzer, Martin W}, issn = {2050-084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{Caspase-mediated nuclear pore complex trimming in cell differentiation and endoplasmic reticulum stress}}, doi = {10.7554/eLife.89066}, volume = {12}, year = {2023}, } @article{14316, abstract = {Clathrin-mediated vesicle trafficking plays central roles in post-Golgi transport. In yeast (Saccharomyces cerevisiae), the AP-1 complex and GGA adaptors are predicted to generate distinct transport vesicles at the trans-Golgi network (TGN), and the epsin-related proteins Ent3p and Ent5p (collectively Ent3p/5p) act as accessories for these adaptors. Recently, we showed that vesicle transport from the TGN is crucial for yeast Rab5 (Vps21p)-mediated endosome formation, and that Ent3p/5p are crucial for this process, whereas AP-1 and GGA adaptors are dispensable. However, these observations were incompatible with previous studies showing that these adaptors are required for Ent3p/5p recruitment to the TGN, and thus the overall mechanism responsible for regulation of Vps21p activity remains ambiguous. Here, we investigated the functional relationships between clathrin adaptors in post-Golgi-mediated Vps21p activation. We show that AP-1 disruption in the ent3Δ5Δ mutant impaired transport of the Vps21p guanine nucleotide exchange factor Vps9p transport to the Vps21p compartment and severely reduced Vps21p activity. Additionally, GGA adaptors, the phosphatidylinositol-4-kinase Pik1p and Rab11 GTPases Ypt31p and Ypt32p were found to have partially overlapping functions for recruitment of AP-1 and Ent3p/5p to the TGN. These findings suggest a distinct role of clathrin adaptors for Vps21p activation in the TGN–endosome trafficking pathway.}, author = {Nagano, Makoto and Aoshima, Kaito and Shimamura, Hiroki and Siekhaus, Daria E and Toshima, Junko Y. and Toshima, Jiro}, issn = {1477-9137}, journal = {Journal of Cell Science}, number = {17}, publisher = {The Company of Biologists}, title = {{Distinct role of TGN-resident clathrin adaptors for Vps21p activation in the TGN-endosome trafficking pathway}}, doi = {10.1242/jcs.261448}, volume = {136}, year = {2023}, } @inproceedings{14317, abstract = {Markov decision processes can be viewed as transformers of probability distributions. While this view is useful from a practical standpoint to reason about trajectories of distributions, basic reachability and safety problems are known to be computationally intractable (i.e., Skolem-hard) to solve in such models. Further, we show that even for simple examples of MDPs, strategies for safety objectives over distributions can require infinite memory and randomization. In light of this, we present a novel overapproximation approach to synthesize strategies in an MDP, such that a safety objective over the distributions is met. More precisely, we develop a new framework for template-based synthesis of certificates as affine distributional and inductive invariants for safety objectives in MDPs. We provide two algorithms within this framework. One can only synthesize memoryless strategies, but has relative completeness guarantees, while the other can synthesize general strategies. The runtime complexity of both algorithms is in PSPACE. We implement these algorithms and show that they can solve several non-trivial examples.}, author = {Akshay, S. and Chatterjee, Krishnendu and Meggendorfer, Tobias and Zikelic, Dorde}, booktitle = {International Conference on Computer Aided Verification}, isbn = {9783031377082}, issn = {1611-3349}, location = {Paris, France}, pages = {86--112}, publisher = {Springer Nature}, title = {{MDPs as distribution transformers: Affine invariant synthesis for safety objectives}}, doi = {10.1007/978-3-031-37709-9_5}, volume = {13966}, year = {2023}, } @inproceedings{14318, abstract = {Probabilistic recurrence relations (PRRs) are a standard formalism for describing the runtime of a randomized algorithm. Given a PRR and a time limit κ, we consider the tail probability Pr[T≥κ], i.e., the probability that the randomized runtime T of the PRR exceeds κ. Our focus is the formal analysis of tail bounds that aims at finding a tight asymptotic upper bound u≥Pr[T≥κ]. To address this problem, the classical and most well-known approach is the cookbook method by Karp (JACM 1994), while other approaches are mostly limited to deriving tail bounds of specific PRRs via involved custom analysis. In this work, we propose a novel approach for deriving the common exponentially-decreasing tail bounds for PRRs whose preprocessing time and random passed sizes observe discrete or (piecewise) uniform distribution and whose recursive call is either a single procedure call or a divide-and-conquer. We first establish a theoretical approach via Markov’s inequality, and then instantiate the theoretical approach with a template-based algorithmic approach via a refined treatment of exponentiation. Experimental evaluation shows that our algorithmic approach is capable of deriving tail bounds that are (i) asymptotically tighter than Karp’s method, (ii) match the best-known manually-derived asymptotic tail bound for QuickSelect, and (iii) is only slightly worse (with a loglogn factor) than the manually-proven optimal asymptotic tail bound for QuickSort. Moreover, our algorithmic approach handles all examples (including realistic PRRs such as QuickSort, QuickSelect, DiameterComputation, etc.) in less than 0.1 s, showing that our approach is efficient in practice.}, author = {Sun, Yican and Fu, Hongfei and Chatterjee, Krishnendu and Goharshady, Amir Kafshdar}, booktitle = {Computer Aided Verification}, isbn = {9783031377082}, issn = {1611-3349}, location = {Paris, France}, pages = {16--39}, publisher = {Springer Nature}, title = {{Automated tail bound analysis for probabilistic recurrence relations}}, doi = {10.1007/978-3-031-37709-9_2}, volume = {13966}, year = {2023}, }