@article{22160, abstract = {Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed and large with respect to , what is the minimum possible degree of a polynomial with such that has zeroes of multiplicity at least at all points in ? For , a classical theorem of Alon and Füredi states that the minimum possible degree of such a polynomial equals . In this paper, we solve the problem for all , proving that the answer is . As an application, we improve a result of Clifton and Huang on configurations of hyperplanes in such that each point in is covered by at least hyperplanes, but the point is uncovered. Surprisingly, the proof of our result involves Catalan numbers and arguments from enumerative combinatorics.}, author = {Sauermann, Lisa and Wigderson, Yuval}, issn = {1469-7750}, journal = {Journal of the London Mathematical Society}, number = {3}, pages = {2379--2402}, publisher = {Wiley}, title = {{Polynomials that vanish to high order on most of the hypercube}}, doi = {10.1112/jlms.12637}, volume = {106}, year = {2022}, } @article{12573, abstract = {Supraglacial debris strongly modulates glacier melt rates and can be decisive for ice dynamics and mountain hydrology. It is ubiquitous in High-Mountain Asia, yet because its thickness and supply rate from local topography are poorly known, our ability to forecast regional glacier change and streamflow is limited. Here we combined remote sensing and numerical modelling to resolve supraglacial debris thickness by altitude for 4689 glaciers in High-Mountain Asia, and debris-supply rate to 4141 of those glaciers. Our results reveal extensively thin supraglacial debris and high spatial variability in both debris thickness and supply rate. Debris-supply rate increases with the temperature and slope of debris-supply slopes regionally, and debris thickness increases as ice flow decreases locally. Our centennial-scale estimates of debris-supply rate are typically an order of magnitude or more lower than millennial-scale estimates of headwall-erosion rate from Beryllium-10 cosmogenic nuclides, potentially reflecting episodic debris supply to the region’s glaciers.}, author = {McCarthy, Michael and Miles, Evan and Kneib, Marin and Buri, Pascal and Fugger, Stefan and Pellicciotti, Francesca}, issn = {2662-4435}, journal = {Communications Earth and Environment}, keywords = {General Earth and Planetary Sciences, General Environmental Science}, publisher = {Springer Nature}, title = {{Supraglacial debris thickness and supply rate in High-Mountain Asia}}, doi = {10.1038/s43247-022-00588-2}, volume = {3}, year = {2022}, } @article{22174, abstract = {The book graph B (k) n consists of n copies of Kk+1 joined along a common Kk. The Ramsey numbers of B (k) n are known to have strong connections to the classical Ramsey numbers of cliques. Recently, the first author determined the asymptotic order of these Ramsey numbers for fixed k, thus answering an old question of Erd˝os, Faudree, Rousseau, and Schelp. In this paper, we first provide a simpler proof of this theorem. Next, answering a question of the first author, we present a different proof that avoids the use of Szemer´edi’s regularity lemma, thus providing much tighter control on the error term. Finally, we prove a conjecture of Nikiforov, Rousseau, and Schelp by showing that all extremal colorings for this Ramsey problem are quasirandom}, author = {Conlon, David and Fox, Jacob and Wigderson, Yuval}, issn = {1439-6912}, journal = {Combinatorica}, number = {3}, pages = {309--363}, publisher = {Springer Nature}, title = {{Ramsey numbers of books and quasirandomness}}, doi = {10.1007/s00493-021-4409-9}, volume = {42}, year = {2022}, } @article{22193, abstract = {Gross and Smith have put forward generalizations of Hardy–Littlewood twin prime conjectures for algebraic number fields. We estimate the behaviour of sums of a singular series that arises in these conjectures, up to lower-order terms. More exactly, where S(η) is the singular series, we find asymptotic formulas for smoothed sums of S(η)−1. Based upon Gross and Smith’s conjectures, we use our result to suggest that for large enough ‘short intervals’ in an algebraic number field K, the variance of counts of prime elements in a random short interval deviates from a Cramér model prediction by a universal factor, independent of K. The conjecture over number fields generalizes a classical conjecture of Goldston and Montgomery over the integers. Numerical data are provided supporting the conjecture.}, author = {Kuperberg, Vivian Zieve and Rodgers, Brad and Roditty-Gershon, Edva}, issn = {1572-9303}, journal = {The Ramanujan Journal}, keywords = {Primes, Short intervals, Ramanujan sums, Singular series, Number fields}, number = {2}, pages = {291--317}, publisher = {Springer Nature}, title = {{Sums of singular series and primes in short intervals in algebraic number fields}}, doi = {10.1007/s11139-022-00561-9}, volume = {58}, year = {2022}, } @article{22194, abstract = {In [J. P. Keating, B. Rodgers, E. Roditty-Gershon and Z. Rudnick, Sums of divisor functions in 𝔽𝑞⁢[𝑡] and matrix integrals, Math. Z. 288 2018, 1–2, 167–198], the authors established relationships of the mean-square of sums of the divisor function 𝑑𝑘⁢(𝑓) over short intervals and over arithmetic progressions for the function field 𝔽𝑞⁢[𝑇] to certain integrals over the ensemble of unitary matrices. We consider similar problems leading to distributions over the ensemble of symplectic matrices. We also consider analogous questions involving convolutions of the von Mangoldt function.}, author = {Kuperberg, Vivian Zieve and Lalín, Matilde}, issn = {1435-5337}, journal = {Forum Mathematicum}, number = {3}, pages = {711--747}, publisher = {De Gruyter}, title = {{Sums of divisor functions and von Mangoldt convolutions in 𝔽q[T] leading to symplectic distributions}}, doi = {10.1515/forum-2021-0171}, volume = {34}, year = {2022}, } @article{22196, abstract = {We explore two questions about pseudo-polynomials, which are functions f : N → Z such that k divides f(n + k) − f(n) for all n, k. First, for certain arbitrarily sparse sets R, we construct pseudo-polynomials f with p|f(n) for some n only if p ∈ R. This implies that not all pseudo-polynomials satisfy an assumption of a recent paper of Kowalski and Soundararajan. We also consider α-primary pseudo-polynomials, where the pseudo-polynomial condition is only required for k lying in a set of primes of density α. We show that if an α-primary pseudo-polynomial is O(e(β−)n), where β = √7 3 − 1 6 ≈ 0.715, then it is a polynomial.}, author = {Kuperberg, Vivian Zieve}, issn = {0022-314X}, journal = {Journal of Number Theory}, keywords = {Pseudo-polynomials, Chinese remainder theorem, Ruzsa’s conjecture}, pages = {531--541}, publisher = {Elsevier}, title = {{On pseudo-polynomials divisible only by a sparse set of primes and α-primary pseudo-polynomials}}, doi = {10.1016/j.jnt.2022.04.006}, volume = {241}, year = {2022}, } @article{22221, author = {Fernández-Rico, Carla}, issn = {1945-0699}, journal = {Physics Today}, number = {5}, pages = {10--11}, publisher = {AIP Publishing}, title = {{Commentary: Researching around Europe: A personal reflection}}, doi = {10.1063/pt.3.4991}, volume = {75}, year = {2022}, } @inproceedings{22374, abstract = {We study the broadcast problem on dynamic networks with n processes. The processes communicate in synchronous rounds along an arbitrary rooted tree. The sequence of trees is given by an adversary whose goal is to maximize the number of rounds until at least one process reaches all other processes. Previous research has shown a ⌈(3n-1)/(2)⌉-2 lower bound and an O(n log log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1 + √2) n-1⌉ ~2.4n. Our result follows from a detailed analysis of the evolution of the adjacency matrix of the network over time.}, author = {El-Hayek, Antoine and Henzinger, Monika H and Schmid, Stefan}, booktitle = {Proceedings of the ACM Symposium on Principles of Distributed Computing}, isbn = {9781450392624}, location = {Salerno, Italy}, pages = {54--56}, publisher = {Association for Computing Machinery}, title = {{Brief announcement: Broadcasting time in dynamic rooted trees is linear}}, doi = {10.1145/3519270.3538460}, year = {2022}, } @inproceedings{11839, abstract = {It is a highly desirable property for deep networks to be robust against small input changes. One popular way to achieve this property is by designing networks with a small Lipschitz constant. In this work, we propose a new technique for constructing such Lipschitz networks that has a number of desirable properties: it can be applied to any linear network layer (fully-connected or convolutional), it provides formal guarantees on the Lipschitz constant, it is easy to implement and efficient to run, and it can be combined with any training objective and optimization method. In fact, our technique is the first one in the literature that achieves all of these properties simultaneously. Our main contribution is a rescaling-based weight matrix parametrization that guarantees each network layer to have a Lipschitz constant of at most 1 and results in the learned weight matrices to be close to orthogonal. Hence we call such layers almost-orthogonal Lipschitz (AOL). Experiments and ablation studies in the context of image classification with certified robust accuracy confirm that AOL layers achieve results that are on par with most existing methods. Yet, they are simpler to implement and more broadly applicable, because they do not require computationally expensive matrix orthogonalization or inversion steps as part of the network architecture. We provide code at https://github.com/berndprach/AOL.}, author = {Prach, Bernd and Lampert, Christoph}, booktitle = {Computer Vision – ECCV 2022}, isbn = {9783031198021}, location = {Tel Aviv, Israel}, pages = {350--365}, publisher = {Springer Nature}, title = {{Almost-orthogonal layers for efficient general-purpose Lipschitz networks}}, doi = {10.1007/978-3-031-19803-8_21}, volume = {13681}, year = {2022}, } @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{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}, }