@inproceedings{11775, abstract = {Quantitative monitoring can be universal and approximate: For every finite sequence of observations, the specification provides a value and the monitor outputs a best-effort approximation of it. The quality of the approximation may depend on the resources that are available to the monitor. By taking to the limit the sequences of specification values and monitor outputs, we obtain precision-resource trade-offs also for limit monitoring. This paper provides a formal framework for studying such trade-offs using an abstract interpretation for monitors: For each natural number n, the aggregate semantics of a monitor at time n is an equivalence relation over all sequences of at most n observations so that two equivalent sequences are indistinguishable to the monitor and thus mapped to the same output. This abstract interpretation of quantitative monitors allows us to measure the number of equivalence classes (or “resource use”) that is necessary for a certain precision up to a certain time, or at any time. Our framework offers several insights. For example, we identify a family of specifications for which any resource-optimal exact limit monitor is independent of any error permitted over finite traces. Moreover, we present a specification for which any resource-optimal approximate limit monitor does not minimize its resource use at any time. }, author = {Henzinger, Thomas A and Mazzocchi, Nicolas Adrien and Sarac, Naci E}, booktitle = {22nd International Conference on Runtime Verification}, issn = {0302-9743}, location = {Tbilisi, Georgia}, pages = {200--220}, publisher = {Springer Nature}, title = {{Abstract monitors for quantitative specifications}}, doi = {10.1007/978-3-031-17196-3_11}, volume = {13498}, year = {2022}, } @inproceedings{12101, abstract = {Spatial games form a widely-studied class of games from biology and physics modeling the evolution of social behavior. Formally, such a game is defined by a square (d by d) payoff matrix M and an undirected graph G. Each vertex of G represents an individual, that initially follows some strategy i ∈ {1,2,…,d}. In each round of the game, every individual plays the matrix game with each of its neighbors: An individual following strategy i meeting a neighbor following strategy j receives a payoff equal to the entry (i,j) of M. Then, each individual updates its strategy to its neighbors' strategy with the highest sum of payoffs, and the next round starts. The basic computational problems consist of reachability between configurations and the average frequency of a strategy. For general spatial games and graphs, these problems are in PSPACE. In this paper, we examine restricted setting: the game is a prisoner’s dilemma; and G is a subgraph of grid. We prove that basic computational problems for spatial games with prisoner’s dilemma on a subgraph of a grid are PSPACE-hard.}, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Jecker, Ismael R and Svoboda, Jakub}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, isbn = {9783959772617}, issn = {1868-8969}, location = {Madras, India}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Complexity of spatial games}}, doi = {10.4230/LIPIcs.FSTTCS.2022.11}, volume = {250}, year = {2022}, } @article{12257, abstract = {Structural balance theory is an established framework for studying social relationships of friendship and enmity. These relationships are modeled by a signed network whose energy potential measures the level of imbalance, while stochastic dynamics drives the network toward a state of minimum energy that captures social balance. It is known that this energy landscape has local minima that can trap socially aware dynamics, preventing it from reaching balance. Here we first study the robustness and attractor properties of these local minima. We show that a stochastic process can reach them from an abundance of initial states and that some local minima cannot be escaped by mild perturbations of the network. Motivated by these anomalies, we introduce best-edge dynamics (BED), a new plausible stochastic process. We prove that BED always reaches balance and that it does so fast in various interesting settings.}, author = {Chatterjee, Krishnendu and Svoboda, Jakub and Zikelic, Dorde and Pavlogiannis, Andreas and Tkadlec, Josef}, issn = {2470-0053}, journal = {Physical Review E}, number = {3}, publisher = {American Physical Society}, title = {{Social balance on networks: Local minima and best-edge dynamics}}, doi = {10.1103/physreve.106.034321}, volume = {106}, year = {2022}, } @article{10583, abstract = {The synthetic strigolactone (SL) analog, rac-GR24, has been instrumental in studying the role of SLs as well as karrikins because it activates the receptors DWARF14 (D14) and KARRIKIN INSENSITIVE 2 (KAI2) of their signaling pathways, respectively. Treatment with rac-GR24 modifies the root architecture at different levels, such as decreasing the lateral root density (LRD), while promoting root hair elongation or flavonol accumulation. Previously, we have shown that the flavonol biosynthesis is transcriptionally activated in the root by rac-GR24 treatment, but, thus far, the molecular players involved in that response have remained unknown. To get an in-depth insight into the changes that occur after the compound is perceived by the roots, we compared the root transcriptomes of the wild type and the more axillary growth2 (max2) mutant, affected in both SL and karrikin signaling pathways, with and without rac-GR24 treatment. Quantitative reverse transcription (qRT)-PCR, reporter line analysis and mutant phenotyping indicated that the flavonol response and the root hair elongation are controlled by the ELONGATED HYPOCOTYL 5 (HY5) and MYB12 transcription factors, but HY5, in contrast to MYB12, affects the LRD as well. Furthermore, we identified the transcription factors TARGET OF MONOPTEROS 5 (TMO5) and TMO5 LIKE1 as negative and the Mediator complex as positive regulators of the rac-GR24 effect on LRD. Altogether, hereby, we get closer toward understanding the molecular mechanisms that underlay the rac-GR24 responses in the root.}, author = {Struk, Sylwia and Braem, Lukas and Matthys, Cedrick and Walton, Alan and Vangheluwe, Nick and Van Praet, Stan and Jiang, Lingxiang and Baster, Pawel and De Cuyper, Carolien and Boyer, Francois-Didier and Stes, Elisabeth and Beeckman, Tom and Friml, Jiří and Gevaert, Kris and Goormachtig, Sofie}, issn = {1471-9053}, journal = {Plant & Cell Physiology}, keywords = {flavonols, MAX2, rac-Gr24, RNA-seq, root development, transcriptional regulation}, number = {1}, pages = {104--119}, publisher = {Oxford University Press}, title = {{Transcriptional analysis in the Arabidopsis roots reveals new regulators that link rac-GR24 treatment with changes in flavonol accumulation, root hair elongation and lateral root density}}, doi = {10.1093/pcp/pcab149}, volume = {63}, year = {2022}, } @article{10282, abstract = {Advanced transcriptome sequencing has revealed that the majority of eukaryotic genes undergo alternative splicing (AS). Nonetheless, little effort has been dedicated to investigating the functional relevance of particular splicing events, even those in the key developmental and hormonal regulators. Combining approaches of genetics, biochemistry and advanced confocal microscopy, we describe the impact of alternative splicing on the PIN7 gene in the model plant Arabidopsis thaliana. PIN7 encodes a polarly localized transporter for the phytohormone auxin and produces two evolutionarily conserved transcripts, PIN7a and PIN7b. PIN7a and PIN7b, differing in a four amino acid stretch, exhibit almost identical expression patterns and subcellular localization. We reveal that they are closely associated and mutually influence each other's mobility within the plasma membrane. Phenotypic complementation tests indicate that the functional contribution of PIN7b per se is minor, but it markedly reduces the prominent PIN7a activity, which is required for correct seedling apical hook formation and auxin-mediated tropic responses. Our results establish alternative splicing of the PIN family as a conserved, functionally relevant mechanism, revealing an additional regulatory level of auxin-mediated plant development.}, author = {Kashkan, Ivan and Hrtyan, Mónika and Retzer, Katarzyna and Humpolíčková, Jana and Jayasree, Aswathy and Filepová, Roberta and Vondráková, Zuzana and Simon, Sibu and Rombaut, Debbie and Jacobs, Thomas B. and Frilander, Mikko J. and Hejátko, Jan and Friml, Jiří and Petrášek, Jan and Růžička, Kamil}, issn = {1469-8137}, journal = {New Phytologist}, number = {1}, pages = {329--343}, publisher = {Wiley}, title = {{Mutually opposing activity of PIN7 splicing isoforms is required for auxin-mediated tropic responses in Arabidopsis thaliana}}, doi = {10.1111/nph.17792}, volume = {233}, year = {2022}, } @article{10656, abstract = {Idealized simulations of the tropical atmosphere have predicted that clouds can spontaneously clump together in space, despite perfectly homogeneous settings. This phenomenon has been called self-aggregation, and it results in a state where a moist cloudy region with intense deep convective storms is surrounded by extremely dry subsiding air devoid of deep clouds. We review here the main findings from theoretical work and idealized models of this phenomenon, highlighting the physical processes believed to play a key role in convective self-aggregation. We also review the growing literature on the importance and implications of this phenomenon for the tropical atmosphere, notably, for the hydrological cycle and for precipitation extremes, in our current and in a warming climate.}, author = {Muller, Caroline J and Yang, Da and Craig, George and Cronin, Timothy and Fildier, Benjamin and Haerter, Jan O. and Hohenegger, Cathy and Mapes, Brian and Randall, David and Shamekh, Sara and Sherwood, Steven C.}, issn = {1545-4479}, journal = {Annual Review of Fluid Mechanics}, pages = {133--157}, publisher = {Annual Reviews}, title = {{Spontaneous aggregation of convective storms}}, doi = {10.1146/annurev-fluid-022421-011319}, volume = {54}, year = {2022}, } @article{10846, abstract = {The Golgi apparatus regulates the process of modification and subcellular localization of macromolecules, including proteins and lipids. Aberrant protein sorting caused by defects in the Golgi leads to various diseases in mammals. However, the role of the Golgi apparatus in organismal longevity remained largely unknown. By employing a quantitative proteomic approach, we demonstrated that MON-2, an evolutionarily conserved Arf-GEF protein implicated in Golgi-to-endosome trafficking, promotes longevity via upregulating macroautophagy/autophagy in C. elegans. Our data using cultured mammalian cells indicate that MON2 translocates from the Golgi to the endosome under starvation conditions, subsequently increasing autophagic flux by binding LGG-1/GABARAPL2. Thus, Golgi-to-endosome trafficking appears to be an evolutionarily conserved process for the upregulation of autophagy, which contributes to organismal longevity.}, author = {Artan, Murat and Sohn, Jooyeon and Lee, Cheolju and Park, Seung Yeol and Lee, Seung Jae V.}, issn = {1554-8635}, journal = {Autophagy}, number = {5}, pages = {1208--1210}, publisher = {Taylor & Francis}, title = {{MON-2, a Golgi protein, promotes longevity by upregulating autophagy through mediating inter-organelle communications}}, doi = {10.1080/15548627.2022.2039523}, volume = {18}, year = {2022}, } @article{11636, abstract = {In [3], Poonen and Slavov recently developed a novel approach to Bertini irreducibility theorems over an arbitrary field, based on random hyperplane slicing. In this paper, we extend their work by proving an analogous bound for the dimension of the exceptional locus in the setting of linear subspaces of higher codimensions.}, author = {Kmentt, Philip and Shute, Alec L}, issn = {1090-2465}, journal = {Finite Fields and their Applications}, number = {10}, publisher = {Elsevier}, title = {{The Bertini irreducibility theorem for higher codimensional slices}}, doi = {10.1016/j.ffa.2022.102085}, volume = {83}, year = {2022}, } @article{12684, abstract = {Given a place ω of a global function field K over a finite field, with associated affine function ring Rω and completion Kω , the aim of this paper is to give an effective joint equidistribution result for renormalized primitive lattice points (a,b)∈Rω2 in the plane Kω2 , and for renormalized solutions to the gcd equation ax+by=1 . The main tools are techniques of Goronik and Nevo for counting lattice points in well-rounded families of subsets. This gives a sharper analog in positive characteristic of a result of Nevo and the first author for the equidistribution of the primitive lattice points in \ZZ2 .}, author = {Horesh, Tal and Paulin, Frédéric}, issn = {2118-8572}, journal = {Journal de Theorie des Nombres de Bordeaux}, number = {3}, pages = {679--703}, publisher = {Université de Bordeaux}, title = {{Effective equidistribution of lattice points in positive characteristic}}, doi = {10.5802/JTNB.1222}, volume = {34}, year = {2022}, } @article{12065, abstract = {Capacity, rate performance, and cycle life of aprotic Li–O2 batteries critically depend on reversible electrodeposition of Li2O2. Current understanding states surface-adsorbed versus solvated LiO2 controls Li2O2 growth as surface film or as large particles. Herein, we show that Li2O2 forms across a wide range of electrolytes, carbons, and current densities as particles via solution-mediated LiO2 disproportionation, bringing into question the prevalence of any surface growth under practical conditions. We describe a unified O2 reduction mechanism, which can explain all found capacity relations and Li2O2 morphologies with exclusive solution discharge. Determining particle morphology and achievable capacities are species mobilities, true areal rate, and the degree of LiO2 association in solution. Capacity is conclusively limited by mass transport through the tortuous Li2O2 rather than electron transport through a passivating Li2O2 film. Provided that species mobilities and surface growth are high, high capacities are also achieved with weakly solvating electrolytes, which were previously considered prototypical for low capacity via surface growth.}, author = {Prehal, Christian and Mondal, Soumyadip and Lovicar, Ludek and Freunberger, Stefan Alexander}, issn = {2380-8195}, journal = {ACS Energy Letters}, number = {9}, pages = {3112--3119}, publisher = {American Chemical Society}, title = {{Exclusive solution discharge in Li-O₂ batteries?}}, doi = {10.1021/acsenergylett.2c01711}, volume = {7}, year = {2022}, } @article{12109, abstract = {Kelvin probe force microscopy (KPFM) is a powerful tool for studying contact electrification (CE) at the nanoscale, but converting KPFM voltage maps to charge density maps is nontrivial due to long-range forces and complex system geometry. Here we present a strategy using finite-element method (FEM) simulations to determine the Green's function of the KPFM probe/insulator/ground system, which allows us to quantitatively extract surface charge. Testing our approach with synthetic data, we find that accounting for the atomic force microscope (AFM) tip, cone, and cantilever is necessary to recover a known input and that existing methods lead to gross miscalculation or even the incorrect sign of the underlying charge. Applying it to experimental data, we demonstrate its capacity to extract realistic surface charge densities and fine details from contact-charged surfaces. Our method gives a straightforward recipe to convert qualitative KPFM voltage data into quantitative charge data over a range of experimental conditions, enabling quantitative CE at the nanoscale.}, author = {Pertl, Felix and Sobarzo Ponce, Juan Carlos A and Shafeek, Lubuna B and Cramer, Tobias and Waitukaitis, Scott R}, issn = {2475-9953}, journal = {Physical Review Materials}, number = {12}, publisher = {American Physical Society}, title = {{Quantifying nanoscale charge density features of contact-charged surfaces with an FEM/KPFM-hybrid approach}}, doi = {10.1103/PhysRevMaterials.6.125605}, volume = {6}, year = {2022}, } @article{9311, abstract = {Partially observable Markov decision processes (POMDPs) are standard models for dynamic systems with probabilistic and nondeterministic behaviour in uncertain environments. We prove that in POMDPs with long-run average objective, the decision maker has approximately optimal strategies with finite memory. This implies notably that approximating the long-run value is recursively enumerable, as well as a weak continuity property of the value with respect to the transition function. }, author = {Chatterjee, Krishnendu and Saona Urmeneta, Raimundo J and Ziliotto, Bruno}, issn = {1526-5471}, journal = {Mathematics of Operations Research}, keywords = {Management Science and Operations Research, General Mathematics, Computer Science Applications}, number = {1}, pages = {100--119}, publisher = {Institute for Operations Research and the Management Sciences}, title = {{Finite-memory strategies in POMDPs with long-run average objectives}}, doi = {10.1287/moor.2020.1116}, volume = {47}, year = {2022}, } @article{11732, abstract = {We study the BCS energy gap Ξ in the high–density limit and derive an asymptotic formula, which strongly depends on the strength of the interaction potential V on the Fermi surface. In combination with the recent result by one of us (Math. Phys. Anal. Geom. 25, 3, 2022) on the critical temperature Tc at high densities, we prove the universality of the ratio of the energy gap and the critical temperature.}, author = {Henheik, Sven Joscha and Lauritsen, Asbjørn Bækgaard}, issn = {1572-9613}, journal = {Journal of Statistical Physics}, keywords = {Mathematical Physics, Statistical and Nonlinear Physics}, publisher = {Springer Nature}, title = {{The BCS energy gap at high density}}, doi = {10.1007/s10955-022-02965-9}, volume = {189}, year = {2022}, } @article{10642, abstract = {Based on a result by Yarotsky (J Stat Phys 118, 2005), we prove that localized but otherwise arbitrary perturbations of weakly interacting quantum spin systems with uniformly gapped on-site terms change the ground state of such a system only locally, even if they close the spectral gap. We call this a strong version of the local perturbations perturb locally (LPPL) principle which is known to hold for much more general gapped systems, but only for perturbations that do not close the spectral gap of the Hamiltonian. We also extend this strong LPPL-principle to Hamiltonians that have the appropriate structure of gapped on-site terms and weak interactions only locally in some region of space. While our results are technically corollaries to a theorem of Yarotsky, we expect that the paradigm of systems with a locally gapped ground state that is completely insensitive to the form of the Hamiltonian elsewhere extends to other situations and has important physical consequences.}, author = {Henheik, Sven Joscha and Teufel, Stefan and Wessel, Tom}, issn = {1573-0530}, journal = {Letters in Mathematical Physics}, keywords = {mathematical physics, statistical and nonlinear physics}, number = {1}, publisher = {Springer Nature}, title = {{Local stability of ground states in locally gapped and weakly interacting quantum spin systems}}, doi = {10.1007/s11005-021-01494-y}, volume = {112}, year = {2022}, } @article{10623, abstract = {We investigate the BCS critical temperature Tc in the high-density limit and derive an asymptotic formula, which strongly depends on the behavior of the interaction potential V on the Fermi-surface. Our results include a rigorous confirmation for the behavior of Tc at high densities proposed by Langmann et al. (Phys Rev Lett 122:157001, 2019) and identify precise conditions under which superconducting domes arise in BCS theory.}, author = {Henheik, Sven Joscha}, issn = {1572-9656}, journal = {Mathematical Physics, Analysis and Geometry}, keywords = {geometry and topology, mathematical physics}, number = {1}, publisher = {Springer Nature}, title = {{The BCS critical temperature at high density}}, doi = {10.1007/s11040-021-09415-0}, volume = {25}, year = {2022}, } @article{12184, abstract = {We review recent results on adiabatic theory for ground states of extended gapped fermionic lattice systems under several different assumptions. More precisely, we present generalized super-adiabatic theorems for extended but finite and infinite systems, assuming either a uniform gap or a gap in the bulk above the unperturbed ground state. The goal of this Review is to provide an overview of these adiabatic theorems and briefly outline the main ideas and techniques required in their proofs.}, author = {Henheik, Sven Joscha and Wessel, Tom}, issn = {0022-2488}, journal = {Journal of Mathematical Physics}, number = {12}, publisher = {AIP Publishing}, title = {{On adiabatic theory for extended fermionic lattice systems}}, doi = {10.1063/5.0123441}, volume = {63}, year = {2022}, } @inproceedings{17087, abstract = {We consider the problem of model compression for deep neural networks (DNNs) in the challenging one-shot/post-training setting, in which we are given an accurate trained model, and must compress it without any retraining, based only on a small amount of calibration input data. This problem has become popular in view of the emerging software and hardware support for executing models compressed via pruning and/or quantization with speedup, and well-performing solutions have been proposed independently for both compression approaches.In this paper, we introduce a new compression framework which covers both weight pruning and quantization in a unified setting, is time- and space-efficient, and considerably improves upon the practical performance of existing post-training methods. At the technical level, our approach is based on an exact and efficient realization of the classical Optimal Brain Surgeon (OBS) framework of [LeCun, Denker, and Solla, 1990] extended to also cover weight quantization at the scale of modern DNNs. From the practical perspective, our experimental results show that it can improve significantly upon the compression-accuracy trade-offs of existing post-training methods, and that it can enable the accurate compound application of both pruning and quantization in a post-training setting.}, author = {Frantar, Elias and Singh, Sidak Pal and Alistarh, Dan-Adrian}, booktitle = {36th Conference on Neural Information Processing Systems}, isbn = {9781713871088}, location = {New Orleans, LA, United States}, publisher = {ML Research Press}, title = {{Optimal brain compression: A framework for accurate post-training quantization and pruning}}, volume = {35}, year = {2022}, } @article{12286, abstract = {Inspired by the study of loose cycles in hypergraphs, we define the loose core in hypergraphs as a structurewhich mirrors the close relationship between cycles and $2$-cores in graphs. We prove that in the $r$-uniform binomial random hypergraph $H^r(n,p)$, the order of the loose core undergoes a phase transition at a certain critical threshold and determine this order, as well as the number of edges, asymptotically in the subcritical and supercritical regimes. Our main tool is an algorithm called CoreConstruct, which enables us to analyse a peeling process for the loose core. By analysing this algorithm we determine the asymptotic degree distribution of vertices in the loose core and in particular how many vertices and edges the loose core contains. As a corollary we obtain an improved upper bound on the length of the longest loose cycle in $H^r(n,p)$.}, author = {Cooley, Oliver and Kang, Mihyun and Zalla, Julian}, issn = {1077-8926}, journal = {The Electronic Journal of Combinatorics}, keywords = {Computational Theory and Mathematics, Geometry and Topology, Theoretical Computer Science, Applied Mathematics, Discrete Mathematics and Combinatorics}, number = {4}, publisher = {Electronic Journal of Combinatorics}, title = {{Loose cores and cycles in random hypergraphs}}, doi = {10.37236/10794}, volume = {29}, year = {2022}, } @article{10765, abstract = {We establish the Hardy-Littlewood property (à la Borovoi-Rudnick) for Zariski open subsets in affine quadrics of the form q(x1,...,xn)=m, where q is a non-degenerate integral quadratic form in n>3 variables and m is a non-zero integer. This gives asymptotic formulas for the density of integral points taking coprime polynomial values, which is a quantitative version of the arithmetic purity of strong approximation property off infinity for affine quadrics.}, author = {Cao, Yang and Huang, Zhizhong}, issn = {1090-2082}, journal = {Advances in Mathematics}, number = {3}, publisher = {Elsevier}, title = {{Arithmetic purity of the Hardy-Littlewood property and geometric sieve for affine quadrics}}, doi = {10.1016/j.aim.2022.108236}, volume = {398}, year = {2022}, } @unpublished{10788, abstract = {We determine an asymptotic formula for the number of integral points of bounded height on a certain toric variety, which is incompatible with part of a preprint by Chambert-Loir and Tschinkel. We provide an alternative interpretation of the asymptotic formula we get. To do so, we construct an analogue of Peyre's constant $\alpha$ and describe its relation to a new obstruction to the Zariski density of integral points in certain regions of varieties.}, author = {Wilsch, Florian Alexander}, booktitle = {arXiv}, keywords = {Integral point, toric variety, Manin's conjecture}, title = {{Integral points of bounded height on a certain toric variety}}, doi = {10.48550/arXiv.2202.10909}, year = {2022}, }