@article{10023, abstract = {We study the temporal dissipation of variance and relative entropy for ergodic Markov Chains in continuous time, and compute explicitly the corresponding dissipation rates. These are identified, as is well known, in the case of the variance in terms of an appropriate Hilbertian norm; and in the case of the relative entropy, in terms of a Dirichlet form which morphs into a version of the familiar Fisher information under conditions of detailed balance. Here we obtain trajectorial versions of these results, valid along almost every path of the random motion and most transparent in the backwards direction of time. Martingale arguments and time reversal play crucial roles, as in the recent work of Karatzas, Schachermayer and Tschiderer for conservative diffusions. Extensions are developed to general “convex divergences” and to countable state-spaces. The steepest descent and gradient flow properties for the variance, the relative entropy, and appropriate generalizations, are studied along with their respective geometries under conditions of detailed balance, leading to a very direct proof for the HWI inequality of Otto and Villani in the present context.}, author = {Karatzas, Ioannis and Maas, Jan and Schachermayer, Walter}, issn = {1526-7555}, journal = {Communications in Information and Systems}, keywords = {Markov Chain, relative entropy, time reversal, steepest descent, gradient flow}, number = {4}, pages = {481--536}, publisher = {International Press}, title = {{Trajectorial dissipation and gradient flow for the relative entropy in Markov chains}}, doi = {10.4310/CIS.2021.v21.n4.a1}, volume = {21}, year = {2021}, } @inproceedings{10052, abstract = {A deterministic finite automaton (DFA) 𝒜 is composite if its language L(𝒜) can be decomposed into an intersection ⋂_{i = 1}^k L(𝒜_i) of languages of smaller DFAs. Otherwise, 𝒜 is prime. This notion of primality was introduced by Kupferman and Mosheiff in 2013, and while they proved that we can decide whether a DFA is composite, the precise complexity of this problem is still open, with a doubly-exponential gap between the upper and lower bounds. In this work, we focus on permutation DFAs, i.e., those for which the transition monoid is a group. We provide an NP algorithm to decide whether a permutation DFA is composite, and show that the difficulty of this problem comes from the number of non-accepting states of the instance: we give a fixed-parameter tractable algorithm with the number of rejecting states as the parameter. Moreover, we investigate the class of commutative permutation DFAs. Their structural properties allow us to decide compositionality in NL, and even in LOGSPACE if the alphabet size is fixed. Despite this low complexity, we show that complex behaviors still arise in this class: we provide a family of composite DFAs each requiring polynomially many factors with respect to its size. We also consider the variant of the problem that asks whether a DFA is k-factor composite, that is, decomposable into k smaller DFAs, for some given integer k ∈ ℕ. We show that, for commutative permutation DFAs, restricting the number of factors makes the decision computationally harder, and yields a problem with tight bounds: it is NP-complete. Finally, we show that in general, this problem is in PSPACE, and it is in LOGSPACE for DFAs with a singleton alphabet.}, author = {Jecker, Ismael R and Mazzocchi, Nicolas and Wolf, Petra}, booktitle = {32nd International Conference on Concurrency Theory}, isbn = {978-3-9597-7203-7}, issn = {1868-8969}, location = {Paris, France}, publisher = {Schloss Dagstuhl - Leibniz Zentrum für Informatik}, title = {{Decomposing permutation automata}}, doi = {10.4230/LIPIcs.CONCUR.2021.18}, volume = {203}, year = {2021}, } @inproceedings{10054, abstract = {Graphs and games on graphs are fundamental models for the analysis of reactive systems, in particular, for model-checking and the synthesis of reactive systems. The class of ω-regular languages provides a robust specification formalism for the desired properties of reactive systems. In the classical infinitary formulation of the liveness part of an ω-regular specification, a "good" event must happen eventually without any bound between the good events. A stronger notion of liveness is bounded liveness, which requires that good events happen within d transitions. Given a graph or a game graph with n vertices, m edges, and a bounded liveness objective, the previous best-known algorithmic bounds are as follows: (i) O(dm) for graphs, which in the worst-case is O(n³); and (ii) O(n² d²) for games on graphs. Our main contributions improve these long-standing algorithmic bounds. For graphs we present: (i) a randomized algorithm with one-sided error with running time O(n^{2.5} log n) for the bounded liveness objectives; and (ii) a deterministic linear-time algorithm for the complement of bounded liveness objectives. For games on graphs, we present an O(n² d) time algorithm for the bounded liveness objectives.}, author = {Chatterjee, Krishnendu and Henzinger, Monika H and Kale, Sagar Sudhir and Svozil, Alexander}, booktitle = {48th International Colloquium on Automata, Languages, and Programming}, isbn = {978-3-95977-195-5}, issn = {1868-8969}, location = {Glasgow, Scotland}, publisher = {Schloss Dagstuhl - Leibniz Zentrum für Informatik}, title = {{Faster algorithms for bounded liveness in graphs and game graphs}}, doi = {10.4230/LIPIcs.ICALP.2021.124}, volume = {198}, year = {2021}, } @article{10071, author = {Adams, Henry and Kourimska, Hana and Heiss, Teresa and Percival, Sarah and Ziegelmeier, Lori}, issn = {1088-9477}, journal = {Notices of the American Mathematical Society}, number = {9}, pages = {1511--1514}, publisher = {American Mathematical Society}, title = {{How to tutorial-a-thon}}, doi = {10.1090/noti2349}, volume = {68}, year = {2021}, } @inproceedings{10072, abstract = {The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthrough paper of Moser and Tardos and follow-up works revealed that the LLL has intimate connections with a class of stochastic local search algorithms for finding such desirable objects. In particular, it can be seen as a sufficient condition for this type of algorithms to converge fast. Besides conditions for existence of and fast convergence to desirable objects, one may naturally ask further questions regarding properties of these algorithms. For instance, "are they parallelizable?", "how many solutions can they output?", "what is the expected "weight" of a solution?", etc. These questions and more have been answered for a class of LLL-inspired algorithms called commutative. In this paper we introduce a new, very natural and more general notion of commutativity (essentially matrix commutativity) which allows us to show a number of new refined properties of LLL-inspired local search algorithms with significantly simpler proofs.}, author = {Harris, David G. and Iliopoulos, Fotis and Kolmogorov, Vladimir}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques}, isbn = {978-3-9597-7207-5}, issn = {1868-8969}, location = {Virtual}, publisher = {Schloss Dagstuhl - Leibniz Zentrum für Informatik}, title = {{A new notion of commutativity for the algorithmic Lovász Local Lemma}}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.31}, volume = {207}, year = {2021}, } @inproceedings{10075, abstract = {We study the expressiveness and succinctness of good-for-games pushdown automata (GFG-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved based on the run constructed so far, but independently of the remainder of the input word. We prove that GFG-PDA recognise more languages than deterministic PDA (DPDA) but not all context-free languages (CFL). This class is orthogonal to unambiguous CFL. We further show that GFG-PDA can be exponentially more succinct than DPDA, while PDA can be double-exponentially more succinct than GFG-PDA. We also study GFGness in visibly pushdown automata (VPA), which enjoy better closure properties than PDA, and for which we show GFGness to be ExpTime-complete. GFG-VPA can be exponentially more succinct than deterministic VPA, while VPA can be exponentially more succinct than GFG-VPA. Both of these lower bounds are tight. Finally, we study the complexity of resolving nondeterminism in GFG-PDA. Every GFG-PDA has a positional resolver, a function that resolves nondeterminism and that is only dependant on the current configuration. Pushdown transducers are sufficient to implement the resolvers of GFG-VPA, but not those of GFG-PDA. GFG-PDA with finite-state resolvers are determinisable.}, author = {Guha, Shibashis and Jecker, Ismael R and Lehtinen, Karoliina and Zimmermann, Martin}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science}, isbn = {978-3-9597-7201-3}, issn = {1868-8969}, location = {Tallinn, Estonia}, publisher = {Schloss Dagstuhl - Leibniz Zentrum für Informatik}, title = {{A bit of nondeterminism makes pushdown automata expressive and succinct}}, doi = {10.4230/LIPIcs.MFCS.2021.53}, volume = {202}, year = {2021}, } @unpublished{10080, abstract = {Hippocampal and neocortical neural activity is modulated by the position of the individual in space. While hippocampal neurons provide the basis for a spatial map, prefrontal cortical neurons generalize over environmental features. Whether these generalized representations result from a bidirectional interaction with, or are mainly derived from hippocampal spatial representations is not known. By examining simultaneously recorded hippocampal and medial prefrontal neurons, we observed that prefrontal spatial representations show a delayed coherence with hippocampal ones. We also identified subpopulations of cells in the hippocampus and medial prefrontal cortex that formed functional cross-area couplings; these resembled the optimal connections predicted by a probabilistic model of spatial information transfer and generalization. Moreover, cross-area couplings were strongest and had the shortest delay preceding spatial decision-making. Our results suggest that generalized spatial coding in the medial prefrontal cortex is inherited from spatial representations in the hippocampus, and that the routing of information can change dynamically with behavioral demands.}, author = {Nardin, Michele and Käfer, Karola and Csicsvari, Jozsef L}, booktitle = {bioRxiv}, publisher = {Cold Spring Harbor Laboratory}, title = {{The generalized spatial representation in the prefrontal cortex is inherited from the hippocampus}}, doi = {10.1101/2021.09.30.462269}, year = {2021}, } @article{10124, abstract = {The transport of macromolecules and nanoscopic particles to a target cellular site is a crucial aspect in many physiological processes. This directional motion is generally controlled via active mechanical and chemical processes. Here we show, by means of molecular dynamics simulations and an analytical theory, that completely passive nanoparticles can exhibit directional motion when embedded in non-uniform mechanical environments. Specifically, we study the motion of a passive nanoparticle adhering to a mechanically non-uniform elastic membrane. We observe a non-monotonic affinity of the particle to the membrane as a function of the membrane’s rigidity, which results in the particle transport. This transport can be both up or down the rigidity gradient, depending on the absolute values of the rigidities that the gradient spans across. We conclude that rigidity gradients can be used to direct average motion of passive macromolecules and nanoparticles on deformable membranes, resulting in the preferential accumulation of the macromolecules in regions of certain mechanical properties.}, author = {Palaia, Ivan and Paraschiv, Alexandru and Debets, Vincent and Storm, Cornelis and Šarić, Anđela}, journal = {ACS Nano}, publisher = {American Chemical Society}, title = {{Durotaxis of passive nanoparticles on elastic membranes}}, doi = {10.1021/acsnano.1c02777 }, year = {2021}, } @unpublished{10125, abstract = {Living systems propagate by undergoing rounds of cell growth and division. Cell division is at heart a physical process that requires mechanical forces, usually exerted by protein assemblies. Here we developed the first physical model for the division of archaeal cells, which despite their structural simplicity share machinery and evolutionary origins with eukaryotes. We show how active geometry changes of elastic ESCRT-III filaments, coupled to filament disassembly, are sufficient to efficiently split the cell. We explore how the non-equilibrium processes that govern the filament behaviour impact the resulting cell division. We show how a quantitative comparison between our simulations and dynamic data for ESCRTIII-mediated division in Sulfolobus acidocaldarius, the closest archaeal relative to eukaryotic cells that can currently be cultured in the lab, and reveal the most likely physical mechanism behind its division.}, author = {Harker-Kirschneck, L. and Hafner, A. E. and Yao, T. and Pulschen, A. and Hurtig, F. and Vanhille-Campos, C. and Hryniuk, D. and Culley, S. and Henriques, R. and Baum, B. and Šarić, Anđela}, booktitle = {bioRxiv}, publisher = {Cold Spring Harbor Laboratory}, title = {{Physical mechanisms of ESCRT-III-driven cell division in archaea}}, doi = {10.1101/2021.03.23.436559}, year = {2021}, } @article{10144, abstract = {FGFs and their high-affinity receptors (FGFRs) play key roles in development, tissue repair, and disease. Because FGFRs bind overlapping sets of ligands, their individual functions cannot be determined using ligand stimulation. Here, we generated a light-activated FGFR2 variant (OptoR2) to selectively activate signaling by the major FGFR in keratinocytes. Illumination of OptoR2-expressing HEK 293T cells activated FGFR signaling with remarkable temporal precision and promoted cell migration and proliferation. In murine and human keratinocytes, OptoR2 activation rapidly induced the classical FGFR signaling pathways and expression of FGF target genes. Surprisingly, multi-level counter-regulation occurred in keratinocytes in vitro and in transgenic mice in vivo, including OptoR2 down-regulation and loss of responsiveness to light activation. These results demonstrate unexpected cell type-specific limitations of optogenetic FGFRs in long-term in vitro and in vivo settings and highlight the complex consequences of transferring optogenetic cell signaling tools into their relevant cellular contexts.}, author = {Rauschendorfer, Theresa and Gurri, Selina and Heggli, Irina and Maddaluno, Luigi and Meyer, Michael and Inglés Prieto, Álvaro and Janovjak, Harald L and Werner, Sabine}, issn = {2575-1077}, journal = {Life Science Alliance}, number = {11}, publisher = {Life Science Alliance}, title = {{Acute and chronic effects of a light-activated FGF receptor in keratinocytes in vitro and in mice}}, doi = {10.26508/lsa.202101100}, volume = {4}, year = {2021}, } @article{10153, abstract = {Gradual typing is a principled means for mixing typed and untyped code. But typed and untyped code often exhibit different programming patterns. There is already substantial research investigating gradually giving types to code exhibiting typical untyped patterns, and some research investigating gradually removing types from code exhibiting typical typed patterns. This paper investigates how to extend these established gradual-typing concepts to give formal guarantees not only about how to change types as code evolves but also about how to change such programming patterns as well. In particular, we explore mixing untyped "structural" code with typed "nominal" code in an object-oriented language. But whereas previous work only allowed "nominal" objects to be treated as "structural" objects, we also allow "structural" objects to dynamically acquire certain nominal types, namely interfaces. We present a calculus that supports such "cross-paradigm" code migration and interoperation in a manner satisfying both the static and dynamic gradual guarantees, and demonstrate that the calculus can be implemented efficiently.}, author = {Mühlböck, Fabian and Tate, Ross}, issn = {2475-1421}, journal = {Proceedings of the ACM on Programming Languages}, keywords = {gradual typing, gradual guarantee, nominal, structural, call tags}, location = {Chicago, IL, United States}, publisher = {Association for Computing Machinery}, title = {{Transitioning from structural to nominal code with efficient gradual typing}}, doi = {10.1145/3485504}, volume = {5}, year = {2021}, } @inproceedings{10148, abstract = {Tactile feedback of an object’s surface enables us to discern its material properties and affordances. This understanding is used in digital fabrication processes by creating objects with high-resolution surface variations to influence a user’s tactile perception. As the design of such surface haptics commonly relies on knowledge from real-life experiences, it is unclear how to adapt this information for digital design methods. In this work, we investigate replicating the haptics of real materials. Using an existing process for capturing an object’s microgeometry, we digitize and reproduce the stable surface information of a set of 15 fabric samples. In a psychophysical experiment, we evaluate the tactile qualities of our set of original samples and their replicas. From our results, we see that direct reproduction of surface variations is able to influence different psychophysical dimensions of the tactile perception of surface textures. While the fabrication process did not preserve all properties, our approach underlines that replication of surface microgeometries benefits fabrication methods in terms of haptic perception by covering a large range of tactile variations. Moreover, by changing the surface structure of a single fabricated material, its material perception can be influenced. We conclude by proposing strategies for capturing and reproducing digitized textures to better resemble the perceived haptics of the originals.}, author = {Degraen, Donald and Piovarci, Michael and Bickel, Bernd and Kruger, Antonio}, booktitle = {34th Annual ACM Symposium}, isbn = {978-1-4503-8635-7}, location = {Virtual}, pages = {954--971}, publisher = {Association for Computing Machinery}, title = {{Capturing tactile properties of real surfaces for haptic reproduction}}, doi = {10.1145/3472749.3474798}, year = {2021}, } @unpublished{10174, abstract = {Quantitative stochastic homogenization of linear elliptic operators is by now well-understood. In this contribution we move forward to the nonlinear setting of monotone operators with p-growth. This first work is dedicated to a quantitative two-scale expansion result. Fluctuations will be addressed in companion articles. By treating the range of exponents 2≤p<∞ in dimensions d≤3, we are able to consider genuinely nonlinear elliptic equations and systems such as −∇⋅A(x)(1+|∇u|p−2)∇u=f (with A random, non-necessarily symmetric) for the first time. When going from p=2 to p>2, the main difficulty is to analyze the associated linearized operator, whose coefficients are degenerate, unbounded, and depend on the random input A via the solution of a nonlinear equation. One of our main achievements is the control of this intricate nonlinear dependence, leading to annealed Meyers' estimates for the linearized operator, which are key to the quantitative two-scale expansion result.}, author = {Clozeau, Nicolas and Gloria, Antoine}, booktitle = {arXiv}, title = {{Quantitative nonlinear homogenization: control of oscillations}}, year = {2021}, } @article{10180, abstract = {The growing energy and performance costs of deep learning have driven the community to reduce the size of neural networks by selectively pruning components. Similarly to their biological counterparts, sparse networks generalize just as well, sometimes even better than, the original dense networks. Sparsity promises to reduce the memory footprint of regular networks to fit mobile devices, as well as shorten training time for ever growing networks. In this paper, we survey prior work on sparsity in deep learning and provide an extensive tutorial of sparsification for both inference and training. We describe approaches to remove and add elements of neural networks, different training strategies to achieve model sparsity, and mechanisms to exploit sparsity in practice. Our work distills ideas from more than 300 research papers and provides guidance to practitioners who wish to utilize sparsity today, as well as to researchers whose goal is to push the frontier forward. We include the necessary background on mathematical methods in sparsification, describe phenomena such as early structure adaptation, the intricate relations between sparsity and the training process, and show techniques for achieving acceleration on real hardware. We also define a metric of pruned parameter efficiency that could serve as a baseline for comparison of different sparse networks. We close by speculating on how sparsity can improve future workloads and outline major open problems in the field.}, author = {Hoefler, Torsten and Alistarh, Dan-Adrian and Ben-Nun, Tal and Dryden, Nikoli and Peste, Elena-Alexandra}, issn = {1533-7928}, journal = {Journal of Machine Learning Research}, number = {241}, pages = {1--124}, publisher = {Journal of Machine Learning Research}, title = {{Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks}}, volume = {22}, year = {2021}, } @inproceedings{10218, abstract = {Let G be a graph on n nodes. In the stochastic population protocol model, a collection of n indistinguishable, resource-limited nodes collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbors first read each other’s states, and then update their local states. A rich line of research has established tight upper and lower bounds on the complexity of fundamental tasks, such as majority and leader election, in this model, when G is a clique. Specifically, in the clique, these tasks can be solved fast, i.e., in n polylog n pairwise interactions, with high probability, using at most polylog n states per node. In this work, we consider the more general setting where G is an arbitrary graph, and present a technique for simulating protocols designed for fully-connected networks in any connected regular graph. Our main result is a simulation that is efficient on many interesting graph families: roughly, the simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. As an example, this implies that, in any regular graph with conductance φ, both leader election and exact majority can be solved in φ^{-2} ⋅ n polylog n pairwise interactions, with high probability, using at most φ^{-2} ⋅ polylog n states per node. This shows that there are fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties.}, author = {Alistarh, Dan-Adrian and Gelashvili, Rati and Rybicki, Joel}, booktitle = {35th International Symposium on Distributed Computing}, isbn = {9-783-9597-7210-5}, issn = {1868-8969}, location = {Freiburg, Germany}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Brief announcement: Fast graphical population protocols}}, doi = {10.4230/LIPIcs.DISC.2021.43}, volume = {209}, year = {2021}, } @inproceedings{10217, abstract = {This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registers, for both deterministic and randomized obstruction-free algorithms. The approach extends to lower bounds for deterministic and randomized obstruction-free algorithms using multi-writer registers under bounded write concurrency, showing a trade-off between the solo step complexity of a leader election algorithm, and the worst-case number of stalls incurred by a processor in an execution.}, author = {Alistarh, Dan-Adrian and Gelashvili, Rati and Nadiradze, Giorgi}, booktitle = {35th International Symposium on Distributed Computing}, isbn = {9-783-9597-7210-5}, issn = {1868-8969}, location = {Freiburg, Germany}, publisher = {Schloss Dagstuhl - Leibniz Zentrum für Informatik}, title = {{Lower bounds for shared-memory leader election under bounded write contention}}, doi = {10.4230/LIPIcs.DISC.2021.4}, volume = {209}, year = {2021}, } @inproceedings{10216, abstract = {This paper reports a new concurrent graph data structure that supports updates of both edges and vertices and queries: Breadth-first search, Single-source shortest-path, and Betweenness centrality. The operations are provably linearizable and non-blocking.}, author = {Chatterjee, Bapi and Peri, Sathya and Sa, Muktikanta}, booktitle = {35th International Symposium on Distributed Computing}, isbn = {9-783-9597-7210-5}, issn = {1868-8969}, location = {Freiburg, Germany}, publisher = {Schloss Dagstuhl - Leibniz Zentrum für Informatik}, title = {{Brief announcement: Non-blocking dynamic unbounded graphs with worst-case amortized bounds}}, doi = {10.4230/LIPIcs.DISC.2021.52}, volume = {209}, year = {2021}, } @inproceedings{10219, abstract = {We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires Ω(log n) rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is Ω(log n).}, author = {Korhonen, Janne and Paz, Ami and Rybicki, Joel and Schmid, Stefan and Suomela, Jukka}, booktitle = {35th International Symposium on Distributed Computing}, isbn = {9-783-9597-7210-5}, issn = {1868-8969}, location = {Freiburg, Germany}, publisher = {Schloss Dagstuhl - Leibniz Zentrum für Informatik}, title = {{Brief announcement: Sinkless orientation is hard also in the supported LOCAL model}}, doi = {10.4230/LIPIcs.DISC.2021.58}, volume = {209}, year = {2021}, } @inbook{10267, abstract = {Tropisms are among the most important growth responses for plant adaptation to the surrounding environment. One of the most common tropisms is root gravitropism. Root gravitropism enables the plant to anchor securely to the soil enabling the absorption of water and nutrients. Most of the knowledge related to the plant gravitropism has been acquired from the flowering plants, due to limited research in non-seed plants. Limited research on non-seed plants is due in large part to the lack of standard research methods. Here, we describe the experimental methods to evaluate gravitropism in representative non-seed plant species, including the non-vascular plant moss Physcomitrium patens, the early diverging extant vascular plant lycophyte Selaginella moellendorffii and fern Ceratopteris richardii. In addition, we introduce the methods used for statistical analysis of the root gravitropism in non-seed plant species.}, author = {Zhang, Yuzhou and Li, Lanxin and Friml, Jiří}, booktitle = {Plant Gravitropism}, editor = {Blancaflor, Elison B}, isbn = {978-1-0716-1676-5}, pages = {43--51}, publisher = {Springer Nature}, title = {{Evaluation of gravitropism in non-seed plants}}, doi = {10.1007/978-1-0716-1677-2_2}, volume = {2368}, year = {2021}, } @inbook{10268, abstract = {The analysis of dynamic cellular processes such as plant cytokinesis stands and falls with live-cell time-lapse confocal imaging. Conventional approaches to time-lapse imaging of cell division in Arabidopsis root tips are tedious and have low throughput. Here, we describe a protocol for long-term time-lapse simultaneous imaging of multiple root tips on a vertical-stage confocal microscope with automated root tracking. We also provide modifications of the basic protocol to implement this imaging method in the analysis of genetic, pharmacological or laser ablation wounding-mediated experimental manipulations. Our method dramatically improves the efficiency of cell division time-lapse imaging by increasing the throughput, while reducing the person-hour requirements of such experiments.}, author = {Hörmayer, Lukas and Friml, Jiří and Glanc, Matous}, booktitle = {Plant Cell Division}, isbn = {978-1-0716-1743-4}, issn = {1940-6029}, pages = {105--114}, publisher = {Humana Press}, title = {{Automated time-lapse imaging and manipulation of cell divisions in Arabidopsis roots by vertical-stage confocal microscopy}}, doi = {10.1007/978-1-0716-1744-1_6}, volume = {2382}, year = {2021}, } @article{10285, abstract = {We study the overlaps between right and left eigenvectors for random matrices of the spherical ensemble, as well as truncated unitary ensembles in the regime where half of the matrix at least is truncated. These two integrable models exhibit a form of duality, and the essential steps of our investigation can therefore be performed in parallel. In every case, conditionally on all eigenvalues, diagonal overlaps are shown to be distributed as a product of independent random variables with explicit distributions. This enables us to prove that the scaled diagonal overlaps, conditionally on one eigenvalue, converge in distribution to a heavy-tail limit, namely, the inverse of a γ2 distribution. We also provide formulae for the conditional expectation of diagonal and off-diagonal overlaps, either with respect to one eigenvalue, or with respect to the whole spectrum. These results, analogous to what is known for the complex Ginibre ensemble, can be obtained in these cases thanks to integration techniques inspired from a previous work by Forrester & Krishnapur.}, author = {Dubach, Guillaume}, issn = {1083-6489}, journal = {Electronic Journal of Probability}, publisher = {Institute of Mathematical Statistics}, title = {{On eigenvector statistics in the spherical and truncated unitary ensembles}}, doi = {10.1214/21-EJP686}, volume = {26}, year = {2021}, } @article{10340, abstract = {The cell membrane is an inhomogeneous system composed of phospholipids, sterols, carbohydrates, and proteins that can be directly attached to underlying cytoskeleton. The protein linkers between the membrane and the cytoskeleton are believed to have a profound effect on the mechanical properties of the cell membrane and its ability to reshape. Here, we investigate the role of membrane-cortex linkers on the extrusion of membrane tubes using computer simulations and experiments. In simulations, we find that the force for tube extrusion has a nonlinear dependence on the density of membrane-cortex attachments: at a range of low and intermediate linker densities, the force is not significantly influenced by the presence of the membrane-cortex attachments and resembles that of the bare membrane. For large concentrations of linkers, however, the force substantially increases compared with the bare membrane. In both cases, the linkers provided membrane tubes with increased stability against coalescence. We then pulled tubes from HEK cells using optical tweezers for varying expression levels of the membrane-cortex attachment protein Ezrin. In line with simulations, we observed that overexpression of Ezrin led to an increased extrusion force, while Ezrin depletion had a negligible effect on the force. Our results shed light on the importance of local protein rearrangements for membrane reshaping at nanoscopic scales.}, author = {Paraschiv, Alexandru and Lagny, Thibaut J. and Campos, Christian Vanhille and Coudrier, Evelyne and Bassereau, Patricia and Šarić, Anđela}, issn = {0006-3495}, journal = {Biophysical Journal}, keywords = {biophysics}, number = {4}, pages = {598--606}, publisher = {Cell Press}, title = {{Influence of membrane-cortex linkers on the extrusion of membrane tubes}}, doi = {10.1016/j.bpj.2020.12.028}, volume = {120}, year = {2021}, } @article{10338, abstract = {In the nuclear pore complex, intrinsically disordered proteins (FG Nups), along with their interactions with more globular proteins called nuclear transport receptors (NTRs), are vital to the selectivity of transport into and out of the cell nucleus. Although such interactions can be modeled at different levels of coarse graining, in vitro experimental data have been quantitatively described by minimal models that describe FG Nups as cohesive homogeneous polymers and NTRs as uniformly cohesive spheres, in which the heterogeneous effects have been smeared out. By definition, these minimal models do not account for the explicit heterogeneities in FG Nup sequences, essentially a string of cohesive and noncohesive polymer units, and at the NTR surface. Here, we develop computational and analytical models that do take into account such heterogeneity in a minimal fashion and compare them with experimental data on single-molecule interactions between FG Nups and NTRs. Overall, we find that the heterogeneous nature of FG Nups and NTRs does play a role in determining equilibrium binding properties but is of much greater significance when it comes to unbinding and binding kinetics. Using our models, we predict how binding equilibria and kinetics depend on the distribution of cohesive blocks in the FG Nup sequences and of the binding pockets at the NTR surface, with multivalency playing a key role. Finally, we observe that single-molecule binding kinetics has a rather minor influence on the diffusion of NTRs in polymer melts consisting of FG-Nup-like sequences.}, author = {Davis, Luke K. and Šarić, Anđela and Hoogenboom, Bart W. and Zilman, Anton}, issn = {0006-3495}, journal = {Biophysical Journal}, keywords = {biophysics}, number = {9}, pages = {1565--1577}, publisher = {Elsevier}, title = {{Physical modeling of multivalent interactions in the nuclear pore complex}}, doi = {10.1016/j.bpj.2021.01.039}, volume = {120}, year = {2021}, } @article{10337, abstract = {The T cell receptor (TCR) pathway receives, processes, and amplifies the signal from pathogenic antigens to the activation of T cells. Although major components in this pathway have been identified, the knowledge on how individual components cooperate to effectively transduce signals remains limited. Phase separation emerges as a biophysical principle in organizing signaling molecules into liquid-like condensates. Here, we report that phospholipase Cγ1 (PLCγ1) promotes phase separation of LAT, a key adaptor protein in the TCR pathway. PLCγ1 directly cross-links LAT through its two SH2 domains. PLCγ1 also protects LAT from dephosphorylation by the phosphatase CD45 and promotes LAT-dependent ERK activation and SLP76 phosphorylation. Intriguingly, a nonmonotonic effect of PLCγ1 on LAT clustering was discovered. Computer simulations, based on patchy particles, revealed how the cluster size is regulated by protein compositions. Together, these results define a critical function of PLCγ1 in promoting phase separation of the LAT complex and TCR signal transduction.}, author = {Zeng, Longhui and Palaia, Ivan and Šarić, Anđela and Su, Xiaolei}, issn = {1540-8140}, journal = {Journal of Cell Biology}, keywords = {cell biology}, number = {6}, publisher = {Rockefeller University Press}, title = {{PLCγ1 promotes phase separation of T cell signaling components}}, doi = {10.1083/jcb.202009154}, volume = {220}, year = {2021}, } @article{10339, abstract = {We study the effects of osmotic shocks on lipid vesicles via coarse-grained molecular dynamics simulations by explicitly considering the solute in the system. We find that depending on their nature (hypo- or hypertonic) such shocks can lead to bursting events or engulfing of external material into inner compartments, among other morphology transformations. We characterize the dynamics of these processes and observe a separation of time scales between the osmotic shock absorption and the shape relaxation. Our work consequently provides an insight into the dynamics of compartmentalization in vesicular systems as a result of osmotic shocks, which can be of interest in the context of early proto-cell development and proto-cell compartmentalisation.}, author = {Vanhille-Campos, Christian and Šarić, Anđela}, issn = {1744-6848}, journal = {Soft Matter}, keywords = {condensed matter physics, general chemistry}, number = {14}, pages = {3798--3806}, publisher = {Royal Society of Chemistry}, title = {{Modelling the dynamics of vesicle reshaping and scission under osmotic shocks}}, doi = {10.1039/d0sm02012e}, volume = {17}, year = {2021}, } @inproceedings{10367, abstract = {How information is created, shared and consumed has changed rapidly in recent decades, in part thanks to new social platforms and technologies on the web. With ever-larger amounts of unstructured and limited labels, organizing and reconciling information from different sources and modalities is a central challenge in machine learning. This cutting-edge tutorial aims to introduce the multimodal entailment task, which can be useful for detecting semantic alignments when a single modality alone does not suffice for a whole content understanding. Starting with a brief overview of natural language processing, computer vision, structured data and neural graph learning, we lay the foundations for the multimodal sections to follow. We then discuss recent multimodal learning literature covering visual, audio and language streams, and explore case studies focusing on tasks which require fine-grained understanding of visual and linguistic semantics question answering, veracity and hatred classification. Finally, we introduce a new dataset for recognizing multimodal entailment, exploring it in a hands-on collaborative section. Overall, this tutorial gives an overview of multimodal learning, introduces a multimodal entailment dataset, and encourages future research in the topic.}, author = {Ilharco, Cesar and Shirazi, Afsaneh and Gopalan, Arjun and Nagrani, Arsha and Bratanič, Blaž and Bregler, Chris and Liu, Christina and Ferreira, Felipe and Barcik, Gabriek and Ilharco, Gabriel and Osang, Georg F and Bulian, Jannis and Frank, Jared and Smaira, Lucas and Cao, Qin and Marino, Ricardo and Patel, Roma and Leung, Thomas and Imbrasaite, Vaiva}, booktitle = {59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, Tutorial Abstracts}, isbn = {9-781-9540-8557-2}, location = {Bangkok, Thailand}, pages = {29--30}, publisher = {Association for Computational Linguistics}, title = {{Recognizing multimodal entailment}}, doi = {10.18653/v1/2021.acl-tutorials.6}, year = {2021}, } @book{10415, abstract = {The Hardy–Littlewood circle method was invented over a century ago to study integer solutions to special Diophantine equations, but it has since proven to be one of the most successful all-purpose tools available to number theorists. Not only is it capable of handling remarkably general systems of polynomial equations defined over arbitrary global fields, but it can also shed light on the space of rational curves that lie on algebraic varieties. This book, in which the arithmetic of cubic polynomials takes centre stage, is aimed at bringing beginning graduate students into contact with some of the many facets of the circle method, both classical and modern. This monograph is the winner of the 2021 Ferran Sunyer i Balaguer Prize, a prestigious award for books of expository nature presenting the latest developments in an active area of research in mathematics.}, author = {Browning, Timothy D}, isbn = {978-3-030-86871-0}, issn = {2296-505X}, pages = {XIV, 166}, publisher = {Springer Nature}, title = {{Cubic Forms and the Circle Method}}, doi = {10.1007/978-3-030-86872-7}, volume = {343}, year = {2021}, } @article{10535, abstract = {Realistic models of biological processes typically involve interacting components on multiple scales, driven by changing environment and inherent stochasticity. Such models are often analytically and numerically intractable. We revisit a dynamic maximum entropy method that combines a static maximum entropy with a quasi-stationary approximation. This allows us to reduce stochastic non-equilibrium dynamics expressed by the Fokker-Planck equation to a simpler low-dimensional deterministic dynamics, without the need to track microscopic details. Although the method has been previously applied to a few (rather complicated) applications in population genetics, our main goal here is to explain and to better understand how the method works. We demonstrate the usefulness of the method for two widely studied stochastic problems, highlighting its accuracy in capturing important macroscopic quantities even in rapidly changing non-stationary conditions. For the Ornstein-Uhlenbeck process, the method recovers the exact dynamics whilst for a stochastic island model with migration from other habitats, the approximation retains high macroscopic accuracy under a wide range of scenarios in a dynamic environment.}, author = {Bod'ová, Katarína and Szep, Eniko and Barton, Nicholas H}, issn = {1553-7358}, journal = {PLoS Computational Biology}, number = {12}, publisher = {Public Library of Science}, title = {{Dynamic maximum entropy provides accurate approximation of structured population dynamics}}, doi = {10.1371/journal.pcbi.1009661}, volume = {17}, year = {2021}, } @inproceedings{10552, abstract = {We study a class of convex-concave saddle-point problems of the form minxmaxy⟨Kx,y⟩+fP(x)−h∗(y) where K is a linear operator, fP is the sum of a convex function f with a Lipschitz-continuous gradient and the indicator function of a bounded convex polytope P, and h∗ is a convex (possibly nonsmooth) function. Such problem arises, for example, as a Lagrangian relaxation of various discrete optimization problems. Our main assumptions are the existence of an efficient linear minimization oracle (lmo) for fP and an efficient proximal map for h∗ which motivate the solution via a blend of proximal primal-dual algorithms and Frank-Wolfe algorithms. In case h∗ is the indicator function of a linear constraint and function f is quadratic, we show a O(1/n2) convergence rate on the dual objective, requiring O(nlogn) calls of lmo. If the problem comes from the constrained optimization problem minx∈Rd{fP(x)|Ax−b=0} then we additionally get bound O(1/n2) both on the primal gap and on the infeasibility gap. In the most general case, we show a O(1/n) convergence rate of the primal-dual gap again requiring O(nlogn) calls of lmo. To the best of our knowledge, this improves on the known convergence rates for the considered class of saddle-point problems. We show applications to labeling problems frequently appearing in machine learning and computer vision.}, author = {Kolmogorov, Vladimir and Pock, Thomas}, booktitle = {38th International Conference on Machine Learning}, location = {Virtual}, title = {{One-sided Frank-Wolfe algorithms for saddle problems}}, year = {2021}, } @inproceedings{10595, abstract = {A recent line of work has analyzed the theoretical properties of deep neural networks via the Neural Tangent Kernel (NTK). In particular, the smallest eigenvalue of the NTK has been related to the memorization capacity, the global convergence of gradient descent algorithms and the generalization of deep nets. However, existing results either provide bounds in the two-layer setting or assume that the spectrum of the NTK matrices is bounded away from 0 for multi-layer networks. In this paper, we provide tight bounds on the smallest eigenvalue of NTK matrices for deep ReLU nets, both in the limiting case of infinite widths and for finite widths. In the finite-width setting, the network architectures we consider are fairly general: we require the existence of a wide layer with roughly order of $N$ neurons, $N$ being the number of data samples; and the scaling of the remaining layer widths is arbitrary (up to logarithmic factors). To obtain our results, we analyze various quantities of independent interest: we give lower bounds on the smallest singular value of hidden feature matrices, and upper bounds on the Lipschitz constant of input-output feature maps.}, author = {Nguyen, Quynh and Mondelli, Marco and Montufar, Guido F}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, editor = {Meila, Marina and Zhang, Tong}, location = {Virtual}, pages = {8119--8129}, publisher = {ML Research Press}, title = {{Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep ReLU networks}}, volume = {139}, year = {2021}, } @inproceedings{10599, abstract = {A two-part successive syndrome-check decoding of polar codes is proposed with the first part successively refining the received codeword and the second part checking its syndrome. A new formulation of the successive-cancellation (SC) decoding algorithm is presented that allows for successively refining the received codeword by comparing the log-likelihood ratio value of a frozen bit with its predefined value. The syndrome of the refined received codeword is then checked for possible errors. In case there are no errors, the decoding process is terminated. Otherwise, the decoder continues to refine the received codeword. The proposed method is extended to the case of SC list (SCL) decoding by terminating the decoding process when the syndrome of the best candidate in the list indicates no errors. Simulation results show that the proposed method reduces the time-complexity of SC and SCL decoders and their fast variants, especially at high signal-to-noise ratios.}, author = {Hashemi, Seyyed Ali and Mondelli, Marco and Cioffi, John and Goldsmith, Andrea}, booktitle = {Proceedings of the 55th Asilomar Conference on Signals, Systems, and Computers}, isbn = {9781665458283}, issn = {1058-6393}, location = {Virtual, Pacific Grove, CA, United States}, pages = {943--947}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Successive syndrome-check decoding of polar codes}}, doi = {10.1109/IEEECONF53345.2021.9723394}, volume = {2021-October}, year = {2021}, } @article{10608, abstract = {We consider infinite-dimensional properties in coarse geometry for hyperspaces consisting of finite subsets of metric spaces with the Hausdorff metric. We see that several infinite-dimensional properties are preserved by taking the hyperspace of subsets with at most n points. On the other hand, we prove that, if a metric space contains a sequence of long intervals coarsely, then its hyperspace of finite subsets is not coarsely embeddable into any uniformly convex Banach space. As a corollary, the hyperspace of finite subsets of the real line is not coarsely embeddable into any uniformly convex Banach space. It is also shown that every (not necessarily bounded geometry) metric space with straight finite decomposition complexity has metric sparsification property.}, author = {Weighill, Thomas and Yamauchi, Takamitsu and Zava, Nicolò}, issn = {2199-6768}, journal = {European Journal of Mathematics}, publisher = {Springer Nature}, title = {{Coarse infinite-dimensionality of hyperspaces of finite subsets}}, doi = {10.1007/s40879-021-00515-3}, year = {2021}, } @article{10613, abstract = {Motivated by the recent preprint [\emph{arXiv:2004.08412}] by Ayala, Carinci, and Redig, we first provide a general framework for the study of scaling limits of higher-order fields. Then, by considering the same class of infinite interacting particle systems as in [\emph{arXiv:2004.08412}], namely symmetric simple exclusion and inclusion processes in the d-dimensional Euclidean lattice, we prove the hydrodynamic limit, and convergence for the equilibrium fluctuations, of higher-order fields. In particular, the limit fields exhibit a tensor structure. Our fluctuation result differs from that in [\emph{arXiv:2004.08412}], since we considered-dimensional Euclidean lattice, we prove the hydrodynamic limit, and convergence for the equilibrium fluctuations, of higher-order fields. In particular, the limit fields exhibit a tensor structure. Our fluctuation result differs from that in [\emph{arXiv:2004.08412}], since we consider a different notion of higher-order fluctuation fields.}, author = {Chen, Joe P. and Sau, Federico}, issn = {1024-2953}, journal = {Markov Processes And Related Fields}, keywords = {interacting particle systems, higher-order fields, hydrodynamic limit, equilibrium fluctuations, duality}, number = {3}, pages = {339--380}, publisher = {Polymat Publishing}, title = {{Higher-order hydrodynamics and equilibrium fluctuations of interacting particle systems}}, volume = {27}, year = {2021}, } @article{10616, abstract = {Electrons in moiré flat band systems can spontaneously break time-reversal symmetry, giving rise to a quantized anomalous Hall effect. In this study, we use a superconducting quantum interference device to image stray magnetic fields in twisted bilayer graphene aligned to hexagonal boron nitride. We find a magnetization of several Bohr magnetons per charge carrier, demonstrating that the magnetism is primarily orbital in nature. Our measurements reveal a large change in the magnetization as the chemical potential is swept across the quantum anomalous Hall gap, consistent with the expected contribution of chiral edge states to the magnetization of an orbital Chern insulator. Mapping the spatial evolution of field-driven magnetic reversal, we find a series of reproducible micrometer-scale domains pinned to structural disorder.}, author = {Tschirhart, C. L. and Serlin, M. and Polshyn, Hryhoriy and Shragai, A. and Xia, Z. and Zhu, J. and Zhang, Y. and Watanabe, K. and Taniguchi, T. and Huber, M. E. and Young, A. F.}, issn = {1095-9203}, journal = {Science}, keywords = {multidisciplinary}, number = {6548}, pages = {1323--1327}, publisher = {American Association for the Advancement of Science}, title = {{Imaging orbital ferromagnetism in a moiré Chern insulator}}, doi = {10.1126/science.abd3190}, volume = {372}, year = {2021}, } @article{10617, abstract = {When a flat band is partially filled with electrons, strong Coulomb interactions between them may lead to the emergence of topological gapped states with quantized Hall conductivity. Such emergent topological states have been found in partially filled Landau levels1 and Hofstadter bands2,3; however, in both cases, a large magnetic field is required to produce the underlying flat band. The recent observation of quantum anomalous Hall effects in narrow-band moiré materials4,5,6,7 has led to the theoretical prediction that such phases could be realized at zero magnetic field8,9,10,11,12. Here we report the observation of insulators with Chern number C = 1 in the zero-magnetic-field limit at half-integer filling of the moiré superlattice unit cell in twisted monolayer–bilayer graphene7,13,14,15. Chern insulators in a half-filled band suggest the spontaneous doubling of the superlattice unit cell2,3,16, and our calculations find a ground state of the topological charge density wave at half-filling of the underlying band. The discovery of these topological phases at fractional superlattice filling enables the further pursuit of zero-magnetic-field phases that have fractional statistics that exist either as elementary excitations or bound to lattice dislocations.}, author = {Polshyn, Hryhoriy and Zhang, Y. and Kumar, M. A. and Soejima, T. and Ledwith, P. and Watanabe, K. and Taniguchi, T. and Vishwanath, A. and Zaletel, M. P. and Young, A. F.}, issn = {1745-2481}, journal = {Nature Physics}, keywords = {general physics, astronomy}, publisher = {Springer Nature}, title = {{Topological charge density waves at half-integer filling of a moiré superlattice}}, doi = {10.1038/s41567-021-01418-6}, year = {2021}, } @inproceedings{10630, abstract = {In the Intersection Non-emptiness problem, we are given a list of finite automata A_1, A_2,… , A_m over a common alphabet Σ as input, and the goal is to determine whether some string w ∈ Σ^* lies in the intersection of the languages accepted by the automata in the list. We analyze the complexity of the Intersection Non-emptiness problem under the promise that all input automata accept a language in some level of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy. Automata accepting languages from the lowest levels of these hierarchies arise naturally in the context of model checking. We identify a dichotomy in the dot-depth hierarchy by showing that the problem is already NP-complete when all input automata accept languages of the levels B_0 or B_{1/2} and already PSPACE-hard when all automata accept a language from the level B_1. Conversely, we identify a tetrachotomy in the Straubing-Thérien hierarchy. More precisely, we show that the problem is in AC^0 when restricted to level L_0; complete for L or NL, depending on the input representation, when restricted to languages in the level L_{1/2}; NP-complete when the input is given as DFAs accepting a language in L_1 or L_{3/2}; and finally, PSPACE-complete when the input automata accept languages in level L_2 or higher. Moreover, we show that the proof technique used to show containment in NP for DFAs accepting languages in L_1 or L_{3/2} does not generalize to the context of NFAs. To prove this, we identify a family of languages that provide an exponential separation between the state complexity of general NFAs and that of partially ordered NFAs. To the best of our knowledge, this is the first superpolynomial separation between these two models of computation.}, author = {Arrighi, Emmanuel and Fernau, Henning and Hoffmann, Stefan and Holzer, Markus and Jecker, Ismael R and De Oliveira Oliveira, Mateus and Wolf, Petra}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, isbn = {978-3-9597-7215-0}, issn = {1868-8969}, location = {Virtual}, publisher = {Schloss Dagstuhl - Leibniz Zentrum für Informatik}, title = {{On the complexity of intersection non-emptiness for star-free language classes}}, doi = {10.4230/LIPIcs.FSTTCS.2021.34}, volume = {213}, year = {2021}, } @inproceedings{10629, abstract = {Product graphs arise naturally in formal verification and program analysis. For example, the analysis of two concurrent threads requires the product of two component control-flow graphs, and for language inclusion of deterministic automata the product of two automata is constructed. In many cases, the component graphs have constant treewidth, e.g., when the input contains control-flow graphs of programs. We consider the algorithmic analysis of products of two constant-treewidth graphs with respect to three classic specification languages, namely, (a) algebraic properties, (b) mean-payoff properties, and (c) initial credit for energy properties. Our main contributions are as follows. Consider a graph G that is the product of two constant-treewidth graphs of size n each. First, given an idempotent semiring, we present an algorithm that computes the semiring transitive closure of G in time Õ(n⁴). Since the output has size Θ(n⁴), our algorithm is optimal (up to polylog factors). Second, given a mean-payoff objective, we present an O(n³)-time algorithm for deciding whether the value of a starting state is non-negative, improving the previously known O(n⁴) bound. Third, given an initial credit for energy objective, we present an O(n⁵)-time algorithm for computing the minimum initial credit for all nodes of G, improving the previously known O(n⁸) bound. At the heart of our approach lies an algorithm for the efficient construction of strongly-balanced tree decompositions of constant-treewidth graphs. Given a constant-treewidth graph G' of n nodes and a positive integer λ, our algorithm constructs a binary tree decomposition of G' of width O(λ) with the property that the size of each subtree decreases geometrically with rate (1/2 + 2^{-λ}).}, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, isbn = {978-3-9597-7215-0}, issn = {1868-8969}, location = {Virtual}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Quantitative verification on product graphs of small treewidth}}, doi = {10.4230/LIPIcs.FSTTCS.2021.42}, volume = {213}, year = {2021}, } @article{10635, abstract = {The brain efficiently performs nonlinear computations through its intricate networks of spiking neurons, but how this is done remains elusive. While nonlinear computations can be implemented successfully in spiking neural networks, this requires supervised training and the resulting connectivity can be hard to interpret. In contrast, the required connectivity for any computation in the form of a linear dynamical system can be directly derived and understood with the spike coding network (SCN) framework. These networks also have biologically realistic activity patterns and are highly robust to cell death. Here we extend the SCN framework to directly implement any polynomial dynamical system, without the need for training. This results in networks requiring a mix of synapse types (fast, slow, and multiplicative), which we term multiplicative spike coding networks (mSCNs). Using mSCNs, we demonstrate how to directly derive the required connectivity for several nonlinear dynamical systems. We also show how to carry out higher-order polynomials with coupled networks that use only pair-wise multiplicative synapses, and provide expected numbers of connections for each synapse type. Overall, our work demonstrates a novel method for implementing nonlinear computations in spiking neural networks, while keeping the attractive features of standard SCNs (robustness, realistic activity patterns, and interpretable connectivity). Finally, we discuss the biological plausibility of our approach, and how the high accuracy and robustness of the approach may be of interest for neuromorphic computing.}, author = {Nardin, Michele and Phillips, James W. and Podlaski, William F. and Keemink, Sander W.}, issn = {2804-3871}, journal = {Peer Community Journal}, publisher = {Centre Mersenne ; Peer Community In}, title = {{Nonlinear computations in spiking neural networks through multiplicative synapses}}, doi = {10.24072/pcjournal.69}, volume = {1}, year = {2021}, } @inproceedings{10651, abstract = {Electrons in the moiré flat bands of magic angle twisted bilayer graphene aligned to hexagonal boron nitride can break time reversal symmetry and open an interaction-driven, topological gap. The resulting magnetic order and associated quantized anomalous Hall effect have properties that diverge substantially from quantized anomalous Hall effects observed in other systems. I will present transport data and scanning probe magnetometry data acquired using a nanoSQUID-on-tip microscope. A quantitative analysis of the magnitude of the magnetization of the Chern magnet shows that the magnetic moment per moiré unit cell substantially exceeds 1 μB and grows rapidly in the topological gap, consistent with an orbital origin for the magnetic order. We find that the Barkhausen jumps observed in transport measurements can be mapped directly to microscopic motion of ferromagnetic domain walls. These domain walls are strongly pinned to disorder in the device and are reproducible across thermal cycles, suggesting coupling between the magnetic degrees of freedom and structural inhomogeneity.}, author = {Tschirhart, Charles and Serlin, Marec and Polshyn, Hryhoriy and Shragai, Avi G. and Xia, Zhengchao and Zhu, Jiacheng and Zhang, Yuxuan and Watanabe, Kenji and Taniguchi, Takashi and Huber, Martin E. and Young, Andrea}, booktitle = {APS March Meeting 2021}, issn = {0003-0503}, location = {Virtual, United States}, number = {1}, publisher = {American Physical Society}, title = {{Probing orbital Chern ferromagnet phase in twisted bilayer graphene}}, volume = {66}, year = {2021}, } @article{10649, abstract = {Harnessing the properties of vortices in superconductors is crucial for fundamental science and technological applications; thus, it has been an ongoing goal to locally probe and control vortices. Here, we use a scanning probe technique that enables studies of vortex dynamics in superconducting systems by leveraging the resonant behavior of a raster-scanned, magnetic-tipped cantilever. This experimental setup allows us to image and control vortices, as well as extract key energy scales of the vortex interactions. Applying this technique to lattices of superconductor island arrays on a metal, we obtain a variety of striking spatial patterns that encode information about the energy landscape for vortices in the system. We interpret these patterns in terms of local vortex dynamics and extract the relative strengths of the characteristic energy scales in the system, such as the vortex-magnetic field and vortex-vortex interaction strengths, as well as the vortex chemical potential. We also demonstrate that the relative strengths of the interactions can be tuned and show how these interactions shift with an applied bias. The high degree of tunability and local nature of such vortex imaging and control not only enable new understanding of vortex interactions, but also have potential applications in more complex systems such as those relevant to quantum computing.}, author = {Naibert, Tyler R. and Polshyn, Hryhoriy and Garrido-Menacho, Rita and Durkin, Malcolm and Wolin, Brian and Chua, Victor and Mondragon-Shem, Ian and Hughes, Taylor and Mason, Nadya and Budakian, Raffi}, issn = {2469-9969}, journal = {Physical Review B}, number = {22}, publisher = {American Physical Society}, title = {{Imaging and controlling vortex dynamics in mesoscopic superconductor-normal-metal-superconductor arrays}}, doi = {10.1103/physrevb.103.224526}, volume = {103}, year = {2021}, } @misc{10645, abstract = {Superconducting qubits have emerged as a highly versatile and useful platform for quantum technological applications [1]. Bluefors and Zurich Instruments have supported the growth of this field from the 2010s onwards by providing well-engineered and reliable measurement infrastructure [2]– [6]. Having a long and stable qubit lifetime is a critical system property. Therefore, considerable effort has already gone into measuring qubit energy-relaxation timescales and their fluctuations, see Refs. [7]–[10] among others. Accurately extracting the statistics of a quantum device requires users to perform time consuming measurements. One measurement challenge is that the detection of the state-dependent response of a superconducting resonator due to a dispersively-coupled qubit requires an inherently low signal level. Consequently, measurements must be performed using a microwave probe that contains only a few microwave photons. Improving the signal-to-noise ratio (SNR) by using near-quantum limited parametric amplifiers as well as the use of optimized signal processing enabled by efficient room temperature instrumentation help to reduce measurement time. An empirical observation for fixed frequency transmons from recent literature is that as the energy-relaxation time 𝑇𝑇1 increases, so do its natural temporal fluctuations [7], [10]. This necessitates many repeated measurements to understand the statistics (see for example, Ref. [10]). In addition, as state-of-the-art qubits increase in lifetime, longer measurement times are expected to obtain accurate statistics. As described below, the scaling of the widths of the qubit energy-relaxation distributions also reveal clues about the origin of the energy-relaxation.}, author = {Simbierowicz, Slawomir and Shi, Chunyan and Collodo, Michele and Kirste, Moritz and Hassani, Farid and Fink, Johannes M and Bylander, Jonas and Perez Lozano, Daniel and Lake, Russell}, keywords = {Application note}, pages = {8}, publisher = {Bluefors Oy}, title = {{Qubit energy-relaxation statistics in the Bluefors quantum measurement system}}, year = {2021}, } @misc{10644, abstract = {The purpose of this application note is to demonstrate a working example of a superconducting qubit measurement in a Bluefors cryostat using the Keysight quantum control hardware. Our motivation is twofold. First, we provide pre-qualification data that the Bluefors cryostat, including filtering and wiring, can support long-lived qubits. Second, we demonstrate that the Keysight system (controlled using Labber) provides a straightforward solution to perform these characterization measurements. This document is intended as a brief guide for starting an experimental platform for testing superconducting qubits. The setup described here is an immediate jumping off point for a suite of applications including testing quantum logical gates, quantum optics with microwaves, or even using the qubit itself as a sensitive probe of local electromagnetic fields. Qubit measurements rely on high performance of both the physical sample environment and the measurement electronics. An overview of the cryogenic system is shown in Figure 1, and an overview of the integration between the electronics and cryostat (including wiring details) is shown in Figure 2.}, author = {Lake, Russell and Simbierowicz, Slawomir and Krantz, Philip and Hassani, Farid and Fink, Johannes M}, keywords = {Application note}, pages = {9}, publisher = {Bluefors Oy}, title = {{The Bluefors dilution refrigerator as an integrated quantum measurement system}}, year = {2021}, } @inproceedings{10669, abstract = {We show that Neural ODEs, an emerging class of timecontinuous neural networks, can be verified by solving a set of global-optimization problems. For this purpose, we introduce Stochastic Lagrangian Reachability (SLR), an abstraction-based technique for constructing a tight Reachtube (an over-approximation of the set of reachable states over a given time-horizon), and provide stochastic guarantees in the form of confidence intervals for the Reachtube bounds. SLR inherently avoids the infamous wrapping effect (accumulation of over-approximation errors) by performing local optimization steps to expand safe regions instead of repeatedly forward-propagating them as is done by deterministic reachability methods. To enable fast local optimizations, we introduce a novel forward-mode adjoint sensitivity method to compute gradients without the need for backpropagation. Finally, we establish asymptotic and non-asymptotic convergence rates for SLR.}, author = {Grunbacher, Sophie and Hasani, Ramin and Lechner, Mathias and Cyranka, Jacek and Smolka, Scott A and Grosu, Radu}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, isbn = {978-1-57735-866-4}, issn = {2374-3468}, location = {Virtual}, number = {13}, pages = {11525--11535}, publisher = {AAAI Press}, title = {{On the verification of neural ODEs with stochastic guarantees}}, volume = {35}, year = {2021}, } @inproceedings{10671, abstract = {We introduce a new class of time-continuous recurrent neural network models. Instead of declaring a learning system’s dynamics by implicit nonlinearities, we construct networks of linear first-order dynamical systems modulated via nonlinear interlinked gates. The resulting models represent dynamical systems with varying (i.e., liquid) time-constants coupled to their hidden state, with outputs being computed by numerical differential equation solvers. These neural networks exhibit stable and bounded behavior, yield superior expressivity within the family of neural ordinary differential equations, and give rise to improved performance on time-series prediction tasks. To demonstrate these properties, we first take a theoretical approach to find bounds over their dynamics, and compute their expressive power by the trajectory length measure in a latent trajectory space. We then conduct a series of time-series prediction experiments to manifest the approximation capability of Liquid Time-Constant Networks (LTCs) compared to classical and modern RNNs.}, author = {Hasani, Ramin and Lechner, Mathias and Amini, Alexander and Rus, Daniela and Grosu, Radu}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, isbn = {978-1-57735-866-4}, issn = {2374-3468}, location = {Virtual}, number = {9}, pages = {7657--7666}, publisher = {AAAI Press}, title = {{Liquid time-constant networks}}, volume = {35}, year = {2021}, } @inproceedings{10668, abstract = {Robustness to variations in lighting conditions is a key objective for any deep vision system. To this end, our paper extends the receptive field of convolutional neural networks with two residual components, ubiquitous in the visual processing system of vertebrates: On-center and off-center pathways, with an excitatory center and inhibitory surround; OOCS for short. The On-center pathway is excited by the presence of a light stimulus in its center, but not in its surround, whereas the Off-center pathway is excited by the absence of a light stimulus in its center, but not in its surround. We design OOCS pathways via a difference of Gaussians, with their variance computed analytically from the size of the receptive fields. OOCS pathways complement each other in their response to light stimuli, ensuring this way a strong edge-detection capability, and as a result an accurate and robust inference under challenging lighting conditions. We provide extensive empirical evidence showing that networks supplied with OOCS pathways gain accuracy and illumination-robustness from the novel edge representation, compared to other baselines.}, author = {Babaiee, Zahra and Hasani, Ramin and Lechner, Mathias and Rus, Daniela and Grosu, Radu}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, issn = {2640-3498}, location = {Virtual}, pages = {478--489}, publisher = {ML Research Press}, title = {{On-off center-surround receptive fields for accurate and robust image classification}}, volume = {139}, year = {2021}, } @inproceedings{10670, abstract = {Imitation learning enables high-fidelity, vision-based learning of policies within rich, photorealistic environments. However, such techniques often rely on traditional discrete-time neural models and face difficulties in generalizing to domain shifts by failing to account for the causal relationships between the agent and the environment. In this paper, we propose a theoretical and experimental framework for learning causal representations using continuous-time neural networks, specifically over their discrete-time counterparts. We evaluate our method in the context of visual-control learning of drones over a series of complex tasks, ranging from short- and long-term navigation, to chasing static and dynamic objects through photorealistic environments. Our results demonstrate that causal continuous-time deep models can perform robust navigation tasks, where advanced recurrent models fail. These models learn complex causal control representations directly from raw visual inputs and scale to solve a variety of tasks using imitation learning.}, author = {Vorbach, Charles J and Hasani, Ramin and Amini, Alexander and Lechner, Mathias and Rus, Daniela}, booktitle = {35th Conference on Neural Information Processing Systems}, location = {Virtual}, title = {{Causal navigation by continuous-time neural networks}}, year = {2021}, } @inproceedings{10688, abstract = {Civl is a static verifier for concurrent programs designed around the conceptual framework of layered refinement, which views the task of verifying a program as a sequence of program simplification steps each justified by its own invariant. Civl verifies a layered concurrent program that compactly expresses all the programs in this sequence and the supporting invariants. This paper presents the design and implementation of the Civl verifier.}, author = {Kragl, Bernhard and Qadeer, Shaz}, booktitle = {Proceedings of the 21st Conference on Formal Methods in Computer-Aided Design}, editor = {Ruzica, Piskac and Whalen, Michael W.}, isbn = {978-3-85448-046-4}, location = {Virtual}, pages = {143–152}, publisher = {TU Wien Academic Press}, title = {{The Civl verifier}}, doi = {10.34727/2021/isbn.978-3-85448-046-4_23}, volume = {2}, year = {2021}, } @inproceedings{10692, abstract = {We experimentally investigate narrow and topologically nontrivial moiré minibands hosted by van der Waals heterostructures consisting of a graphene monolayer rotationally faulted with respect to a Bernal-stacked bilayer. At fillings ν= 1 and 3 electrons per moiré unit cell within these bands, we observe quantized anomalous Hall effects with Rxy≈h/2e2, indicative of spontaneous polarization of the system into a single valley-projected band with Chern number C= 2. Remarkably, we also observe the evidence of symmetry broken Chern insulator states at ν= 1.5 and 3.5. At ν= 3 we find that the sign of the quantum anomalous Hall effect can be reversed via field-effect control of the chemical potential. This curious effect arises from the magnetization contribution due to topological edge states, which drive a reversal of the total magnetization and thus a switch of the favored magnetic state. Remarkably, we find that this switch is hysteretic, which we use to demonstrate non-volatile electric-field-induced reversal of the magnetic state. Voltage control of magnetic states can be used to electrically pattern nonvolatile magnetic domain structures hosting chiral edge states, with applications ranging from reconfigurable microwave circuit elements to ultra-low-power magnetic memory.}, author = {Polshyn, Hryhoriy and Zhu, Jihang and Kumar, Manish and Zhang, Yuxuan and Yang, Fangyuan and Tschirhart, Charles and Serlin, Marec and Watanabe, Kenji and Tanaguchi, Takashi and MacDonald, Allan and Young, Andrea}, booktitle = {APS March Meeting 2021}, issn = {0003-0503}, location = {Virtual}, number = {1}, publisher = {American Physical Society}, title = {{Orbital Chern insulator states in twisted monolayer-bilayer graphene and electrical switching of topological and magnetic order}}, volume = {66}, year = {2021}, } @inproceedings{10694, abstract = {In a two-player zero-sum graph game the players move a token throughout a graph 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, we hold an “auction” (bidding) to determine which player moves the token: both players simultaneously submit bids and the higher bidder moves the token. The bidding mechanisms differ in their payment schemes. Bidding games were largely studied with variants of first-price bidding in which only the higher bidder pays his bid. We focus on all-pay bidding, where both players pay their bids. Finite-duration all-pay bidding games were studied and shown to be technically more challenging than their first-price counterparts. We study for the first time, infinite-duration all-pay bidding games. Our most interesting results are for mean-payoff objectives: we portray a complete picture for games played on strongly-connected graphs. We study both pure (deterministic) and mixed (probabilistic) strategies and completely characterize the optimal and almost-sure (with probability 1) payoffs the players can respectively guarantee. We show that mean-payoff games under all-pay bidding exhibit the intriguing mathematical properties of their first-price counterparts; namely, an equivalence with random-turn games in which in each turn, the player who moves is selected according to a (biased) coin toss. The equivalences for all-pay bidding are more intricate and unexpected than for first-price bidding.}, author = {Avni, Guy and Jecker, Ismael R and Zikelic, Dorde}, booktitle = {Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms}, editor = {Marx, Dániel}, isbn = {978-1-61197-646-5}, location = {Virtual}, pages = {617--636}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Infinite-duration all-pay bidding games}}, doi = {10.1137/1.9781611976465.38}, year = {2021}, } @inproceedings{10847, abstract = {We study the two-player zero-sum extension of the partially observable stochastic shortest-path problem where one agent has only partial information about the environment. We formulate this problem as a partially observable stochastic game (POSG): given a set of target states and negative rewards for each transition, the player with imperfect information maximizes the expected undiscounted total reward until a target state is reached. The second player with the perfect information aims for the opposite. We base our formalism on POSGs with one-sided observability (OS-POSGs) and give the following contributions: (1) we introduce a novel heuristic search value iteration algorithm that iteratively solves depth-limited variants of the game, (2) we derive the bound on the depth guaranteeing an arbitrary precision, (3) we propose a novel upper-bound estimation that allows early terminations, and (4) we experimentally evaluate the algorithm on a pursuit-evasion game.}, author = {Tomášek, Petr and Horák, Karel and Aradhye, Aditya and Bošanský, Branislav and Chatterjee, Krishnendu}, booktitle = {30th International Joint Conference on Artificial Intelligence}, isbn = {9780999241196}, issn = {1045-0823}, location = {Virtual, Online}, pages = {4182--4189}, publisher = {International Joint Conferences on Artificial Intelligence}, title = {{Solving partially observable stochastic shortest-path games}}, doi = {10.24963/ijcai.2021/575}, year = {2021}, } @inproceedings{10853, abstract = {Dynamic Connectivity is a fundamental algorithmic graph problem, motivated by a wide range of applications to social and communication networks and used as a building block in various other algorithms, such as the bi-connectivity and the dynamic minimal spanning tree problems. In brief, we wish to maintain the connected components of the graph under dynamic edge insertions and deletions. In the sequential case, the problem has been well-studied from both theoretical and practical perspectives. However, much less is known about efficient concurrent solutions to this problem. This is the gap we address in this paper. We start from one of the classic data structures used to solve this problem, the Euler Tour Tree. Our first contribution is a non-blocking single-writer implementation of it. We leverage this data structure to obtain the first truly concurrent generalization of dynamic connectivity, which preserves the time complexity of its sequential counterpart, but is also scalable in practice. To achieve this, we rely on three main techniques. The first is to ensure that connectivity queries, which usually dominate real-world workloads, are non-blocking. The second non-trivial technique expands the above idea by making all queries that do not change the connectivity structure non-blocking. The third ingredient is applying fine-grained locking for updating the connected components, which allows operations on disjoint components to occur in parallel. We evaluate the resulting algorithm on various workloads, executing on both real and synthetic graphs. The results show the efficiency of each of the proposed optimizations; the most efficient variant improves the performance of a coarse-grained based implementation on realistic scenarios up to 6x on average and up to 30x when connectivity queries dominate.}, author = {Fedorov, Alexander and Koval, Nikita and Alistarh, Dan-Adrian}, booktitle = {Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures}, isbn = {9781450380706}, location = {Virtual, Online}, pages = {208--220}, publisher = {Association for Computing Machinery}, title = {{A scalable concurrent algorithm for dynamic connectivity}}, doi = {10.1145/3409964.3461810}, year = {2021}, } @unpublished{10912, abstract = {Brain dynamics display collective phenomena as diverse as neuronal oscillations and avalanches. Oscillations are rhythmic, with fluctuations occurring at a characteristic scale, whereas avalanches are scale-free cascades of neural activity. Here we show that such antithetic features can coexist in a very generic class of adaptive neural networks. In the most simple yet fully microscopic model from this class we make direct contact with human brain resting-state activity recordings via tractable inference of the model's two essential parameters. The inferred model quantitatively captures the dynamics over a broad range of scales, from single sensor fluctuations, collective behaviors of nearly-synchronous extreme events on multiple sensors, to neuronal avalanches unfolding over multiple sensors across multiple time-bins. Importantly, the inferred parameters correlate with model-independent signatures of "closeness to criticality", suggesting that the coexistence of scale-specific (neural oscillations) and scale-free (neuronal avalanches) dynamics in brain activity occurs close to a non-equilibrium critical point at the onset of self-sustained oscillations.}, author = {Lombardi, Fabrizio and Pepic, Selver and Shriki, Oren and Tkačik, Gašper and De Martino, Daniele}, pages = {37}, publisher = {arXiv}, title = {{Quantifying the coexistence of neuronal oscillations and avalanches}}, doi = {10.48550/ARXIV.2108.06686}, year = {2021}, } @article{11053, abstract = {Understanding basic mechanisms of aging holds great promise for developing interventions that prevent or delay many age-related declines and diseases simultaneously to increase human healthspan. However, a major confounding factor in aging research is the heterogeneity of the aging process itself. At the organismal level, it is clear that chronological age does not always predict biological age or susceptibility to frailty or pathology. While genetics and environment are major factors driving variable rates of aging, additional complexity arises because different organs, tissues, and cell types are intrinsically heterogeneous and exhibit different aging trajectories normally or in response to the stresses of the aging process (e.g., damage accumulation). Tackling the heterogeneity of aging requires new and specialized tools (e.g., single-cell analyses, mass spectrometry-based approaches, and advanced imaging) to identify novel signatures of aging across scales. Cutting-edge computational approaches are then needed to integrate these disparate datasets and elucidate network interactions between known aging hallmarks. There is also a need for improved, human cell-based models of aging to ensure that basic research findings are relevant to human aging and healthspan interventions. The San Diego Nathan Shock Center (SD-NSC) provides access to cutting-edge scientific resources to facilitate the study of the heterogeneity of aging in general and to promote the use of novel human cell models of aging. The center also has a robust Research Development Core that funds pilot projects on the heterogeneity of aging and organizes innovative training activities, including workshops and a personalized mentoring program, to help investigators new to the aging field succeed. Finally, the SD-NSC participates in outreach activities to educate the general community about the importance of aging research and promote the need for basic biology of aging research in particular.}, author = {Shadel, Gerald S. and Adams, Peter D. and Berggren, W. Travis and Diedrich, Jolene K. and Diffenderfer, Kenneth E. and Gage, Fred H. and Hah, Nasun and Hansen, Malene and HETZER, Martin W and Molina, Anthony J. A. and Manor, Uri and Marek, Kurt and O’Keefe, David D. and Pinto, Antonio F. M. and Sacco, Alessandra and Sharpee, Tatyana O. and Shokriev, Maxim N. and Zambetti, Stefania}, issn = {2509-2715}, journal = {GeroScience}, keywords = {Geriatrics and Gerontology, Aging}, number = {5}, pages = {2139--2148}, publisher = {Springer Nature}, title = {{The San Diego Nathan Shock Center: Tackling the heterogeneity of aging}}, doi = {10.1007/s11357-021-00426-x}, volume = {43}, year = {2021}, } @article{11052, abstract = {In order to combat molecular damage, most cellular proteins undergo rapid turnover. We have previously identified large nuclear protein assemblies that can persist for years in post-mitotic tissues and are subject to age-related decline. Here, we report that mitochondria can be long lived in the mouse brain and reveal that specific mitochondrial proteins have half-lives longer than the average proteome. These mitochondrial long-lived proteins (mitoLLPs) are core components of the electron transport chain (ETC) and display increased longevity in respiratory supercomplexes. We find that COX7C, a mitoLLP that forms a stable contact site between complexes I and IV, is required for complex IV and supercomplex assembly. Remarkably, even upon depletion of COX7C transcripts, ETC function is maintained for days, effectively uncoupling mitochondrial function from ongoing transcription of its mitoLLPs. Our results suggest that modulating protein longevity within the ETC is critical for mitochondrial proteome maintenance and the robustness of mitochondrial function.}, author = {Krishna, Shefali and Arrojo e Drigo, Rafael and Capitanio, Juliana S. and Ramachandra, Ranjan and Ellisman, Mark and HETZER, Martin W}, issn = {1534-5807}, journal = {Developmental Cell}, keywords = {Developmental Biology, Cell Biology, General Biochemistry, Genetics and Molecular Biology, Molecular Biology}, number = {21}, pages = {P2952--2965.e9}, publisher = {Elsevier}, title = {{Identification of long-lived proteins in the mitochondria reveals increased stability of the electron transport chain}}, doi = {10.1016/j.devcel.2021.10.008}, volume = {56}, year = {2021}, } @inproceedings{11436, abstract = {Asynchronous distributed algorithms are a popular way to reduce synchronization costs in large-scale optimization, and in particular for neural network training. However, for nonsmooth and nonconvex objectives, few convergence guarantees exist beyond cases where closed-form proximal operator solutions are available. As training most popular deep neural networks corresponds to optimizing nonsmooth and nonconvex objectives, there is a pressing need for such convergence guarantees. In this paper, we analyze for the first time the convergence of stochastic asynchronous optimization for this general class of objectives. In particular, we focus on stochastic subgradient methods allowing for block variable partitioning, where the shared model is asynchronously updated by concurrent processes. To this end, we use a probabilistic model which captures key features of real asynchronous scheduling between concurrent processes. Under this model, we establish convergence with probability one to an invariant set for stochastic subgradient methods with momentum. From a practical perspective, one issue with the family of algorithms that we consider is that they are not efficiently supported by machine learning frameworks, which mostly focus on distributed data-parallel strategies. To address this, we propose a new implementation strategy for shared-memory based training of deep neural networks for a partitioned but shared model in single- and multi-GPU settings. Based on this implementation, we achieve on average1.2x speed-up in comparison to state-of-the-art training methods for popular image classification tasks, without compromising accuracy.}, author = {Kungurtsev, Vyacheslav and Egan, Malcolm and Chatterjee, Bapi and Alistarh, Dan-Adrian}, booktitle = {35th AAAI Conference on Artificial Intelligence, AAAI 2021}, isbn = {9781713835974}, issn = {2374-3468}, location = {Virtual, Online}, number = {9B}, pages = {8209--8216}, publisher = {AAAI Press}, title = {{Asynchronous optimization methods for efficient training of deep neural networks with guarantees}}, volume = {35}, year = {2021}, } @inproceedings{11453, abstract = {Neuronal computations depend on synaptic connectivity and intrinsic electrophysiological properties. Synaptic connectivity determines which inputs from presynaptic neurons are integrated, while cellular properties determine how inputs are filtered over time. Unlike their biological counterparts, most computational approaches to learning in simulated neural networks are limited to changes in synaptic connectivity. However, if intrinsic parameters change, neural computations are altered drastically. Here, we include the parameters that determine the intrinsic properties, e.g., time constants and reset potential, into the learning paradigm. Using sparse feedback signals that indicate target spike times, and gradient-based parameter updates, we show that the intrinsic parameters can be learned along with the synaptic weights to produce specific input-output functions. Specifically, we use a teacher-student paradigm in which a randomly initialised leaky integrate-and-fire or resonate-and-fire neuron must recover the parameters of a teacher neuron. We show that complex temporal functions can be learned online and without backpropagation through time, relying on event-based updates only. Our results are a step towards online learning of neural computations from ungraded and unsigned sparse feedback signals with a biologically inspired learning mechanism.}, author = {Braun, Lukas and Vogels, Tim P}, booktitle = {Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems}, isbn = {9781713845393}, issn = {1049-5258}, location = {Virtual, Online}, pages = {16437--16450}, publisher = {Neural Information Processing Systems Foundation}, title = {{Online learning of neural computations from sparse temporal feedback}}, volume = {20}, year = {2021}, } @inproceedings{11452, abstract = {We study efficient distributed algorithms for the fundamental problem of principal component analysis and leading eigenvector computation on the sphere, when the data are randomly distributed among a set of computational nodes. We propose a new quantized variant of Riemannian gradient descent to solve this problem, and prove that the algorithm converges with high probability under a set of necessary spherical-convexity properties. We give bounds on the number of bits transmitted by the algorithm under common initialization schemes, and investigate the dependency on the problem dimension in each case.}, author = {Alimisis, Foivos and Davies, Peter and Vandereycken, Bart and Alistarh, Dan-Adrian}, booktitle = {Advances in Neural Information Processing Systems - 35th Conference on Neural Information Processing Systems}, isbn = {9781713845393}, issn = {1049-5258}, location = {Virtual, Online}, pages = {2823--2834}, publisher = {Neural Information Processing Systems Foundation}, title = {{Distributed principal component analysis with limited communication}}, volume = {4}, year = {2021}, } @inproceedings{11463, abstract = {Efficiently approximating local curvature information of the loss function is a key tool for optimization and compression of deep neural networks. Yet, most existing methods to approximate second-order information have high computational or storage costs, which limits their practicality. In this work, we investigate matrix-free, linear-time approaches for estimating Inverse-Hessian Vector Products (IHVPs) for the case when the Hessian can be approximated as a sum of rank-one matrices, as in the classic approximation of the Hessian by the empirical Fisher matrix. We propose two new algorithms: the first is tailored towards network compression and can compute the IHVP for dimension d, if the Hessian is given as a sum of m rank-one matrices, using O(dm2) precomputation, O(dm) cost for computing the IHVP, and query cost O(m) for any single element of the inverse Hessian. The second algorithm targets an optimization setting, where we wish to compute the product between the inverse Hessian, estimated over a sliding window of optimization steps, and a given gradient direction, as required for preconditioned SGD. We give an algorithm with cost O(dm + m2) for computing the IHVP and O(dm + m3) for adding or removing any gradient from the sliding window. These two algorithms yield state-of-the-art results for network pruning and optimization with lower computational overhead relative to existing second-order methods. Implementations are available at [9] and [17].}, author = {Frantar, Elias and Kurtic, Eldar and Alistarh, Dan-Adrian}, booktitle = {35th Conference on Neural Information Processing Systems}, isbn = {9781713845393}, issn = {1049-5258}, location = {Virtual, Online}, pages = {14873--14886}, publisher = {Curran Associates}, title = {{M-FAC: Efficient matrix-free approximations of second-order information}}, volume = {34}, year = {2021}, } @inproceedings{11464, abstract = {We consider a standard distributed optimisation setting where N machines, each holding a d-dimensional function fi, aim to jointly minimise the sum of the functions ∑Ni=1fi(x). This problem arises naturally in large-scale distributed optimisation, where a standard solution is to apply variants of (stochastic) gradient descent. We focus on the communication complexity of this problem: our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the N machines to solve this problem under point-to-point communication, within a given error-tolerance. Specifically, we show that Ω(Ndlogd/Nε) total bits need to be communicated between the machines to find an additive ϵ-approximation to the minimum of ∑Ni=1fi(x). The result holds for both deterministic and randomised algorithms, and, importantly, requires no assumptions on the algorithm structure. The lower bound is tight under certain restrictions on parameter values, and is matched within constant factors for quadratic objectives by a new variant of quantised gradient descent, which we describe and analyse. Our results bring over tools from communication complexity to distributed optimisation, which has potential for further applications.}, author = {Alistarh, Dan-Adrian and Korhonen, Janne}, booktitle = {35th Conference on Neural Information Processing Systems}, isbn = {9781713845393}, issn = {1049-5258}, location = {Virtual, Online}, pages = {7254--7266}, publisher = {Curran Associates}, title = {{Towards tight communication lower bounds for distributed optimisation}}, volume = {34}, year = {2021}, } @article{11498, abstract = {Rest-frame ultraviolet (UV) emission lines probe electron densities, gas-phase abundances, metallicities, and ionization parameters of the emitting star-forming galaxies and their environments. The strongest main UV emission line, Lyα, has been instrumental in advancing the general knowledge of galaxy formation in the early universe. However, observing Lyα emission becomes increasingly challenging at z ≳ 6 when the neutral hydrogen fraction of the circumgalactic and intergalactic media increases. Secondary weaker UV emission lines provide important alternative methods for studying galaxy properties at high redshift. We present a large sample of rest-frame UV emission line sources at intermediate redshift for calibrating and exploring the connection between secondary UV lines and the emitting galaxies’ physical properties and their Lyα emission. The sample of 2052 emission line sources with 1.5 < z < 6.4 was collected from integral field data from the MUSE-Wide and MUSE-Deep surveys taken as part of Guaranteed Time Observations. The objects were selected through untargeted source detection (i.e., no preselection of sources as in dedicated spectroscopic campaigns) in the three-dimensional MUSE data cubes. We searched optimally extracted one-dimensional spectra of the full sample for UV emission features via emission line template matching, resulting in a sample of more than 100 rest-frame UV emission line detections. We show that the detection efficiency of (non-Lyα) UV emission lines increases with survey depth, and that the emission line strength of He IIλ1640 Å, [O III] λ1661 + O III] λ1666, and [Si III] λ1883 + Si III] λ1892 correlate with the strength of [C III] λ1907 + C III] λ1909. The rest-frame equivalent width (EW0) of [C III] λ1907 + C III] λ1909 is found to be roughly 0.22 ± 0.18 of EW0(Lyα). We measured the velocity offsets of resonant emission lines with respect to systemic tracers. For C IVλ1548 + C IVλ1551 we find that ΔvC IV ≲ 250 km s−1, whereas ΔvLyα falls in the range of 250−500 km s−1 which is in agreement with previous results from the literature. The electron density ne measured from [Si III] λ1883 + Si III] λ1892 and [C III] λ1907 + C III] λ1909 line flux ratios is generally < 105 cm−3 and the gas-phase abundance is below solar at 12 + log10(O/H)≈8. Lastly, we used “PhotoIonization Model Probability Density Functions” to infer physical parameters of the full sample and individual systems based on photoionization model parameter grids and observational constraints from our UV emission line searches. This reveals that the UV line emitters generally have ionization parameter log10(U) ≈ −2.5 and metal mass fractions that scatter around Z ≈ 10−2, that is Z ≈ 0.66 Z⊙. Value-added catalogs of the full sample of MUSE objects studied in this work and a collection of UV line emitters from the literature are provided with this paper.}, author = {Schmidt, K. B. and Kerutt, J. and Wisotzki, L. and Urrutia, T. and Feltre, A. and Maseda, M. V. and Nanayakkara, T. and Bacon, R. and Boogaard, L. A. and Conseil, S. and Contini, T. and Herenz, E. C. and Kollatschny, W. and Krumpe, M. and Leclercq, F. and Mahler, G. and Matthee, Jorryt J and Mauerhofer, V. and Richard, J. and Schaye, J.}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, ultraviolet: galaxies / galaxies: high-redshift / galaxies: ISM / ISM: lines and bands / methods: observational / techniques: imaging spectroscopy}, publisher = {EDP Sciences}, title = {{Recovery and analysis of rest-frame UV emission lines in 2052 galaxies observed with MUSE at 1.5 < z < 6.4}}, doi = {10.1051/0004-6361/202140876}, volume = {654}, year = {2021}, } @article{11500, abstract = {We report the discovery of diffuse extended Lyα emission from redshift 3.1 to 4.5, tracing cosmic web filaments on scales of 2.5−4 cMpc. These structures have been observed in overdensities of Lyα emitters in the MUSE Extremely Deep Field, a 140 h deep MUSE observation located in the Hubble Ultra-Deep Field. Among the 22 overdense regions identified, five are likely to harbor very extended Lyα emission at high significance with an average surface brightness of 5 × 10−20 erg s−1 cm−2 arcsec−2. Remarkably, 70% of the total Lyα luminosity from these filaments comes from beyond the circumgalactic medium of any identified Lyα emitter. Fluorescent Lyα emission powered by the cosmic UV background can only account for less than 34% of this emission at z ≈ 3 and for not more than 10% at higher redshift. We find that the bulk of this diffuse emission can be reproduced by the unresolved Lyα emission of a large population of ultra low-luminosity Lyα emitters (< 1040 erg s−1), provided that the faint end of the Lyα luminosity function is steep (α ⪅ −1.8), it extends down to luminosities lower than 1038 − 1037 erg s−1, and the clustering of these Lyα emitters is significant (filling factor < 1/6). If these Lyα emitters are powered by star formation, then this implies their luminosity function needs to extend down to star formation rates < 10−4 M⊙ yr−1. These observations provide the first detection of the cosmic web in Lyα emission in typical filamentary environments and the first observational clue indicating the existence of a large population of ultra low-luminosity Lyα emitters at high redshift.}, author = {Bacon, R. and Mary, D. and Garel, T. and Blaizot, J. and Maseda, M. and Schaye, J. and Wisotzki, L. and Conseil, S. and Brinchmann, J. and Leclercq, F. and Abril-Melgarejo, V. and Boogaard, L. and Bouché, N. F. and Contini, T. and Feltre, A. and Guiderdoni, B. and Herenz, C. and Kollatschny, W. and Kusakabe, H. and Matthee, Jorryt J and Michel-Dansac, L. and Nanayakkara, T. and Richard, J. and Roth, M. and Schmidt, K. B. and Steinmetz, M. and Tresse, L. and Urrutia, T. and Verhamme, A. and Weilbacher, P. M. and Zabl, J. and Zoutendijk, S. L.}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: high-redshift / galaxies: groups: general / cosmology: observations}, publisher = {EDP Sciences}, title = {{The MUSE Extremely Deep Field: The cosmic web in emission at high redshift}}, doi = {10.1051/0004-6361/202039887}, volume = {647}, year = {2021}, } @article{11512, abstract = {We study the molecular gas content of 24 star-forming galaxies at z = 3–4, with a median stellar mass of 109.1 M⊙, from the MUSE Hubble Ultra Deep Field (HUDF) Survey. Selected by their Lyα λ1216 emission and HF160W-band magnitude, the galaxies show an average $\langle {\mathrm{EW}}_{\mathrm{Ly}\alpha }^{0}\rangle \approx 20$ Å, below the typical selection threshold for Lyα emitters (${\mathrm{EW}}_{\mathrm{Ly}\alpha }^{0}\gt 25$ Å), and a rest-frame UV spectrum similar to Lyman-break galaxies. We use rest-frame optical spectroscopy from KMOS and MOSFIRE, and the UV features observed with MUSE, to determine the systemic redshifts, which are offset from Lyα by 〈Δv(Lyα)〉 = 346 km s−1, with a 100 to 600 km s−1 range. Stacking 12CO J = 4 → 3 and [C i]3P1 → 3P0 (and higher-J CO lines) from the ALMA Spectroscopic Survey of the HUDF, we determine 3σ upper limits on the line luminosities of 4.0 × 108 K km s−1pc2 and 5.6 × 108 K km s−1pc2, respectively (for a 300 km s−1 line width). Stacking the 1.2 mm and 3 mm dust-continuum flux densities, we find a 3σ upper limits of 9 μJy and 1.2 μJy, respectively. The inferred gas fractions, under the assumption of a "Galactic" CO-to-H2 conversion factor and gas-to-dust ratio, are in tension with previously determined scaling relations. This implies a substantially higher αCO ≥ 10 and δGDR ≥ 1200, consistent with the subsolar metallicity estimated for these galaxies ($12+\mathrm{log}({\rm{O}}/{\rm{H}})\approx 7.8\pm 0.2$). The low metallicity of z ≥ 3 star-forming galaxies may thus make it very challenging to unveil their cold gas through CO or dust emission, warranting further exploration of alternative tracers, such as [C ii].}, author = {Boogaard, Leindert A. and Bouwens, Rychard J. and Riechers, Dominik and van der Werf, Paul and Bacon, Roland and Matthee, Jorryt J and Stefanon, Mauro and Feltre, Anna and Maseda, Michael and Inami, Hanae and Aravena, Manuel and Brinchmann, Jarle and Carilli, Chris and Contini, Thierry and Decarli, Roberto and González-López, Jorge and Nanayakkara, Themiya and Walter, Fabian}, issn = {1538-4357}, journal = {The Astrophysical Journal}, keywords = {Space and Planetary Science, Astronomy and Astrophysics}, number = {1}, publisher = {IOP Publishing}, title = {{Measuring the average molecular gas content of star-forming galaxies at z = 3–4}}, doi = {10.3847/1538-4357/ac01d7}, volume = {916}, year = {2021}, } @article{11523, abstract = {We present the first results from the X-SHOOTER Lyman α survey at z = 2 (XLS-z2). XLS-z2 is a deep spectroscopic survey of 35 Lyman α emitters (LAEs) utilizing ≈90 h of exposure time with Very Large Telescope/X-SHOOTER and covers rest-frame Ly α to H α emission with R ≈ 4000. We present the sample selection, the observations, and the data reduction. Systemic redshifts are measured from rest-frame optical lines for 33/35 sources. In the stacked spectrum, our LAEs are characterized by an interstellar medium with little dust, a low metallicity, and a high ionization state. The ionizing sources are young hot stars that power strong emission lines in the optical and high-ionization lines in the ultraviolet (UV). The LAEs exhibit clumpy UV morphologies and have outflowing kinematics with blueshifted Si II absorption, a broad [O III] component, and a red-skewed Ly α line. Typically, 30 per cent of the Ly α photons escape, of which one quarter on the blue side of the systemic velocity. A fraction of Ly α photons escape directly at the systemic suggesting clear channels enabling an ≈10 per cent escape of ionizing photons, consistent with an inference based on Mg II. A combination of a low effective H I column density, a low dust content, and young starburst determines whether a star-forming galaxy is observed as an LAE. The first is possibly related to outflows and/or a fortunate viewing angle, while we find that the latter two in LAEs are typical for their stellar mass of 109 M⊙.}, author = {Matthee, Jorryt J and Sobral, David and Hayes, Matthew and Pezzulli, Gabriele and Gronke, Max and Schaerer, Daniel and Naidu, Rohan P and Röttgering, Huub and Calhau, João and Paulino-Afonso, Ana and Santos, Sérgio and Amorín, Ricardo}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: formation, galaxies: ISM, galaxies: starburst, dark ages, reionization, first stars}, number = {1}, pages = {1382--1412}, publisher = {Oxford University Press}, title = {{The X-SHOOTER Lyman α survey at z = 2 (XLS-z2) I: What makes a galaxy a Lyman α emitter?}}, doi = {10.1093/mnras/stab1304}, volume = {505}, year = {2021}, } @article{11525, abstract = {The intensity of the Cosmic UV background (UVB), coming from all sources of ionizing photons such as star-forming galaxies and quasars, determines the thermal evolution and ionization state of the intergalactic medium (IGM) and is, therefore, a critical ingredient for models of cosmic structure formation. Most of the previous estimates are based on the comparison between observed and simulated Lyman-α forest. We present the results of an independent method to constrain the product of the UVB photoionization rate and the covering fraction of Lyman limit systems (LLSs) by searching for the fluorescent Lyman-α emission produced by self-shielded clouds. Because the expected surface brightness is well below current sensitivity limits for direct imaging, we developed a new method based on 3D stacking of the IGM around Lyman-α emitting galaxies (LAEs) between 2.9 < z < 6.6 using deep MUSE observations. Combining our results with covering fractions of LLSs obtained from mock cubes extracted from the EAGLE simulation, we obtain new and independent constraints on the UVB at z > 3 that are consistent with previous measurements, with a preference for relatively low UVB intensities at z = 3, and which suggest a non-monotonic decrease of ΓH I with increasing redshift between 3 < z < 5. This could suggest a possible tension between some UVB models and current observations which however require deeper and wider observations in Lyman-α emission and absorption to be confirmed. Assuming instead a value of UVB from current models, our results constrain the covering fraction of LLSs at 3 < z < 4.5 to be less than 25 per cent within 150 kpc from LAEs.}, author = {Gallego, Sofia G and Cantalupo, Sebastiano and Sarpas, Saeed and Duboeuf, Bastien and Lilly, Simon and Pezzulli, Gabriele and Marino, Raffaella Anna and Matthee, Jorryt J and Wisotzki, Lutz and Schaye, Joop and Richard, Johan and Kusakabe, Haruka and Mauerhofer, Valentin}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics}, number = {1}, pages = {16--32}, publisher = {Oxford University Press}, title = {{Constraining the cosmic UV background at z > 3 with MUSE Lyman-α emission observations}}, doi = {10.1093/mnras/stab796}, volume = {504}, year = {2021}, } @article{11522, abstract = {The decline in abundance of Lyman-α (Lyα) emitting galaxies at z ≳ 6 is a powerful and commonly used probe to constrain the progress of cosmic reionization. We use the CODAII simulation, which is a radiation hydrodynamic simulation featuring a box of ∼94 comoving Mpc side length, to compute the Lyα transmission properties of the intergalactic medium (IGM) at z ∼ 5.8 to 7. Our results mainly confirm previous studies, i.e. we find a declining Lyα transmission with redshift and a large sightline-to-sightline variation. However, motivated by the recent discovery of blue Lyα peaks at high redshift, we also analyse the IGM transmission on the blue side, which shows a rapid decline at z ≳ 6 of the blue transmission. This low transmission can be attributed not only to the presence of neutral regions but also to the residual neutral hydrogen within ionized regions, for which a density even as low as nHI∼10−9cm−3 (sometimes combined with kinematic effects) leads to a significantly reduced visibility. Still, we find that ∼1 per cent of sightlines towards M1600AB ∼ −21 galaxies at z ∼ 7 are transparent enough to allow a transmission of a blue Lyα peak. We discuss our results in the context of the interpretation of observations.}, author = {Gronke, Max and Ocvirk, Pierre and Mason, Charlotte and Matthee, Jorryt J and Bosman, Sarah E I and Sorce, Jenny G and Lewis, Joseph and Ahn, Kyungjin and Aubert, Dominique and Dawoodbhoy, Taha and Iliev, Ilian T and Shapiro, Paul R and Yepes, Gustavo}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {dark ages, reionization, first stars, intergalactic medium, galaxies: formation}, number = {3}, pages = {3697--3709}, publisher = {Oxford University Press}, title = {{Lyman-α transmission properties of the intergalactic medium in the CoDaII simulation}}, doi = {10.1093/mnras/stab2762}, volume = {508}, year = {2021}, } @article{11526, abstract = {We present the results from a MUSE survey of twelve z ≃ 3.15 quasars, which were selected to be much fainter (20 < iSDSS < 23) than in previous studies of giant Ly α nebulae around the brightest quasars (16.6 < iAB < 18.7). We detect H I Ly α nebulae around 100 per cent of our target quasars, with emission extending to scales of at least 60 physical kpc, and up to 190 pkpc. We explore correlations between properties of the nebulae and their host quasars, with the goal of connecting variations in the properties of the illuminating QSO to the response in nebular emission. We show that the surface brightness profiles of the nebulae are similar to those of nebulae around bright quasars, but with a lower normalization. Our targeted quasars are on average 3.7 mag (≃30 times) fainter in UV continuum than our bright reference sample, and yet the nebulae around them are only 4.3 times fainter in mean Ly α surface brightness, measured between 20 and 50 pkpc. We find significant correlations between the surface brightness of the nebula and the luminosity of the quasar in both UV continuum and Ly α. The latter can be interpreted as evidence for a substantial contribution from unresolved inner parts of the nebulae to the narrow components seen in the Ly α lines of some of our faint quasars, possibly from the inner circumgalactic medium or from the host galaxy’s interstellar medium.}, author = {Mackenzie, Ruari and Pezzulli, Gabriele and Cantalupo, Sebastiano and Marino, Raffaella A and Lilly, Simon and Muzahid, Sowgat and Matthee, Jorryt J and Schaye, Joop and Wisotzki, Lutz}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, techniques: imaging spectroscopy, intergalactic medium, quasars: emission lines, quasars: general}, number = {1}, pages = {494--509}, publisher = {Oxford University Press}, title = {{Revealing the impact of quasar luminosity on giant Lyα nebulae}}, doi = {10.1093/mnras/staa3277}, volume = {502}, year = {2021}, } @article{11524, abstract = {We measure the evolution of the rest-frame UV luminosity function (LF) and the stellar mass function (SMF) of Lyman-α (Ly α) emitters (LAEs) from z ∼ 2 to z ∼ 6 by exploring ∼4000 LAEs from the SC4K sample. We find a correlation between Ly α luminosity (LLy α) and rest-frame UV (MUV), with best fit MUV=−1.6+0.2−0.3log10(LLyα/ergs−1)+47+12−11 and a shallower relation between LLy α and stellar mass (M⋆), with best fit log10(M⋆/M⊙)=0.9+0.1−0.1log10(LLyα/ergs−1)−28+4.0−3.8⁠. An increasing LLy α cut predominantly lowers the number density of faint MUV and low M⋆ LAEs. We estimate a proxy for the full UV LFs and SMFs of LAEs with simple assumptions of the faint end slope. For the UV LF, we find a brightening of the characteristic UV luminosity (M∗UV⁠) with increasing redshift and a decrease of the characteristic number density (Φ*). For the SMF, we measure a characteristic stellar mass (⁠M∗⋆/M⊙⁠) increase with increasing redshift, and a Φ* decline. However, if we apply a uniform luminosity cut of log10(LLyα/ergs−1)≥43.0⁠, we find much milder to no evolution in the UV and SMF of LAEs. The UV luminosity density (ρUV) of the full sample of LAEs shows moderate evolution and the stellar mass density (ρM) decreases, with both being always lower than the total ρUV and ρM of more typical galaxies but slowly approaching them with increasing redshift. Overall, our results indicate that both ρUV and ρM of LAEs slowly approach the measurements of continuum-selected galaxies at z > 6, which suggests a key role of LAEs in the epoch of reionization.}, author = {Santos, S and Sobral, D and Butterworth, J and Paulino-Afonso, A and Ribeiro, B and da Cunha, E and Calhau, J and Khostovan, A A and Matthee, Jorryt J and Arrabal Haro, P}, issn = {1365-2966}, journal = {Monthly Notices of the Royal Astronomical Society}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, galaxies: evolution, galaxies: high-redshift, galaxies: luminosity function, mass function}, number = {1}, pages = {1117--1134}, publisher = {Oxford University Press}, title = {{The evolution of the UV luminosity and stellar mass functions of Lyman-α emitters from z ∼ 2 to z ∼ 6}}, doi = {10.1093/mnras/stab1218}, volume = {505}, year = {2021}, } @article{11585, abstract = {Observations show that star-forming galaxies reside on a tight three-dimensional plane between mass, gas-phase metallicity and star formation rate (SFR), which can be explained by the interplay between metal-poor gas inflows, SFR and outflows. However, different metals are released on different time-scales, which may affect the slope of this relation. Here, we use central, star-forming galaxies with Mstar = 109.0−10.5 M from the EAGLE hydrodynamical simulation to examine three-dimensional relations between mass, SFR and chemical enrichment using absolute and relative C, N, O and Fe abundances. We show that the scatter is smaller when gas-phase α-enhancement is used rather than metallicity. A similar plane also exists for stellar α-enhancement, implying that present-day specific SFRs are correlated with long time-scale star formation histories. Between z = 0 and 1, the α-enhancement plane is even more insensitive to redshift than the plane using metallicity. However, it evolves at z > 1 due to lagging iron yields. At fixed mass, galaxies with higher SFRs have star formation histories shifted toward late times, are more α-enhanced and this α-enhancement increases with redshift as observed. These findings suggest that relations between physical properties inferred from observations may be affected by systematic variations in α-enhancements.}, author = {Matthee, Jorryt J}, issn = {2397-3366}, journal = {Nature Astronomy}, keywords = {Astronomy and Astrophysics, galaxies, formation - galaxies, evolution - galaxies, star formation - galaxies, abundances}, pages = {984--985}, publisher = {Springer Nature}, title = {{Differences in galaxy colours are not just about the mass}}, doi = {10.1038/s41550-021-01415-y}, volume = {5}, year = {2021}, } @article{11604, abstract = {The NASA Transiting Exoplanet Survey Satellite (TESS) is observing tens of millions of stars with time spans ranging from ∼27 days to about 1 yr of continuous observations. This vast amount of data contains a wealth of information for variability, exoplanet, and stellar astrophysics studies but requires a number of processing steps before it can be fully utilized. In order to efficiently process all the TESS data and make it available to the wider scientific community, the TESS Data for Asteroseismology working group, as part of the TESS Asteroseismic Science Consortium, has created an automated open-source processing pipeline to produce light curves corrected for systematics from the short- and long-cadence raw photometry data and to classify these according to stellar variability type. We will process all stars down to a TESS magnitude of 15. This paper is the next in a series detailing how the pipeline works. Here, we present our methodology for the automatic variability classification of TESS photometry using an ensemble of supervised learners that are combined into a metaclassifier. We successfully validate our method using a carefully constructed labeled sample of Kepler Q9 light curves with a 27.4 days time span mimicking single-sector TESS observations, on which we obtain an overall accuracy of 94.9%. We demonstrate that our methodology can successfully classify stars outside of our labeled sample by applying it to all ∼167,000 stars observed in Q9 of the Kepler space mission.}, author = {Audenaert, J. and Kuszlewicz, J. S. and Handberg, R. and Tkachenko, A. and Armstrong, D. J. and Hon, M. and Kgoadi, R. and Lund, M. N. and Bell, K. J. and Bugnet, Lisa Annabelle and Bowman, D. M. and Johnston, C. and García, R. A. and Stello, D. and Molnár, L. and Plachy, E. and Buzasi, D. and Aerts, C.}, issn = {1538-3881}, journal = {The Astronomical Journal}, keywords = {Space and Planetary Science, Astronomy and Astrophysics}, number = {5}, publisher = {IOP Publishing}, title = {{TESS Data for Asteroseismology (T’DA) stellar variability classification pipeline: Setup and application to the Kepler Q9 data}}, doi = {10.3847/1538-3881/ac166a}, volume = {162}, year = {2021}, } @article{11608, abstract = {In order to understand stellar evolution, it is crucial to efficiently determine stellar surface rotation periods. Indeed, while they are of great importance in stellar models, angular momentum transport processes inside stars are still poorly understood today. Surface rotation, which is linked to the age of the star, is one of the constraints needed to improve the way those processes are modelled. Statistics of the surface rotation periods for a large sample of stars of different spectral types are thus necessary. An efficient tool to automatically determine reliable rotation periods is needed when dealing with large samples of stellar photometric datasets. The objective of this work is to develop such a tool. For this purpose, machine learning classifiers constitute relevant bases to build our new methodology. Random forest learning abilities are exploited to automate the extraction of rotation periods in Kepler light curves. Rotation periods and complementary parameters are obtained via three different methods: a wavelet analysis, the autocorrelation function of the light curve, and the composite spectrum. We trained three different classifiers: one to detect if rotational modulations are present in the light curve, one to flag close binary or classical pulsators candidates that can bias our rotation period determination, and finally one classifier to provide the final rotation period. We tested our machine learning pipeline on 23 431 stars of the Kepler K and M dwarf reference rotation catalogue for which 60% of the stars have been visually inspected. For the sample of 21 707 stars where all the input parameters are provided to the algorithm, 94.2% of them are correctly classified (as rotating or not). Among the stars that have a rotation period in the reference catalogue, the machine learning provides a period that agrees within 10% of the reference value for 95.3% of the stars. Moreover, the yield of correct rotation periods is raised to 99.5% after visually inspecting 25.2% of the stars. Over the two main analysis steps, rotation classification and period selection, the pipeline yields a global agreement with the reference values of 92.1% and 96.9% before and after visual inspection. Random forest classifiers are efficient tools to determine reliable rotation periods in large samples of stars. The methodology presented here could be easily adapted to extract surface rotation periods for stars with different spectral types or observed by other instruments such as K2, TESS or by PLATO in the near future.}, author = {Breton, S. N. and Santos, A. R. G. and Bugnet, Lisa Annabelle and Mathur, S. and García, R. A. and Pallé, P. L.}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, methods: data analysis / stars: solar-type / stars: activity / stars: rotation / starspots}, publisher = {EDP Sciences}, title = {{ROOSTER: A machine-learning analysis tool for Kepler stellar rotation periods}}, doi = {10.1051/0004-6361/202039947}, volume = {647}, year = {2021}, } @article{11609, abstract = {Context. Stellar interiors are the seat of efficient transport of angular momentum all along their evolution. In this context, understanding the dependence of the turbulent transport triggered by the instabilities of the vertical and horizontal shears of the differential rotation in stellar radiation zones as a function of their rotation, stratification, and thermal diffusivity is mandatory. Indeed, it constitutes one of the cornerstones of the rotational transport and mixing theory, which is implemented in stellar evolution codes to predict the rotational and chemical evolutions of stars. Aims. We investigate horizontal shear instabilities in rotating stellar radiation zones by considering the full Coriolis acceleration with both the dimensionless horizontal Coriolis component f̃ and the vertical component f. Methods. We performed a linear stability analysis using linearized equations derived from the Navier-Stokes and heat transport equations in the rotating nontraditional f-plane. We considered a horizontal shear flow with a hyperbolic tangent profile as the base flow. The linear stability was analyzed numerically in wide ranges of parameters, and we performed an asymptotic analysis for large vertical wavenumbers using the Wentzel-Kramers-Brillouin-Jeffreys (WKBJ) approximation for nondiffusive and highly-diffusive fluids. Results. As in the traditional f-plane approximation, we identify two types of instabilities: the inflectional and inertial instabilities. The inflectional instability is destabilized as f̃ increases and its maximum growth rate increases significantly, while the thermal diffusivity stabilizes the inflectional instability similarly to the traditional case. The inertial instability is also strongly affected; for instance, the inertially unstable regime is also extended in the nondiffusive limit as 0 < f < 1 + f̃ 2/N2, where N is the dimensionless Brunt-Väisälä frequency. More strikingly, in the high thermal diffusivity limit, it is always inertially unstable at any colatitude θ except at the poles (i.e., 0° < θ <  180°). We also derived the critical Reynolds numbers for the inertial instability using the asymptotic dispersion relations obtained from the WKBJ analysis. Using the asymptotic and numerical results, we propose a prescription for the effective turbulent viscosities induced by the inertial and inflectional instabilities that can be possibly used in stellar evolution models. The characteristic time of this turbulence is short enough so that it is efficient to redistribute angular momentum and to mix chemicals in stellar radiation zones.}, author = {Park, J. and Prat, V. and Mathis, S. and Bugnet, Lisa Annabelle}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, hydrodynamics / turbulence / stars, rotation / stars, evolution}, publisher = {EDP Sciences}, title = {{Horizontal shear instabilities in rotating stellar radiation zones: II. Effects of the full Coriolis acceleration}}, doi = {10.1051/0004-6361/202038654}, volume = {646}, year = {2021}, } @article{11605, abstract = {Context. The discovery of moderate differential rotation between the core and the envelope of evolved solar-like stars could be the signature of a strong magnetic field trapped inside the radiative interior. The population of intermediate-mass red giants presenting surprisingly low-amplitude mixed modes (i.e. oscillation modes that behave as acoustic modes in their external envelope and as gravity modes in their core) could also arise from the effect of an internal magnetic field. Indeed, stars more massive than about 1.1 solar masses are known to develop a convective core during their main sequence. The field generated by the dynamo triggered by this convection could be the progenitor of a strong fossil magnetic field trapped inside the core of the star for the remainder of its evolution. Aims. Observations of mixed modes can constitute an excellent probe of the deepest layers of evolved solar-like stars, and magnetic fields in those regions can impact their propagation. The magnetic perturbation on mixed modes may therefore be visible in asteroseismic data. To unravel which constraints can be obtained from observations, we theoretically investigate the effects of a plausible mixed axisymmetric magnetic field with various amplitudes on the mixed-mode frequencies of evolved solar-like stars. Methods. First-order frequency perturbations due to an axisymmetric magnetic field were computed for dipolar and quadrupolar mixed modes. These computations were carried out for a range of stellar ages, masses, and metallicities. Conclusions. We show that typical fossil-field strengths of 0.1 − 1 MG, consistent with the presence of a dynamo in the convective core during the main sequence, provoke significant asymmetries on mixed-mode frequency multiplets during the red giant branch. We provide constraints and methods for the detectability of such magnetic signatures. We show that these signatures may be detectable in asteroseismic data for field amplitudes small enough for the amplitude of the modes not to be affected by the conversion of gravity into Alfvén waves inside the magnetised interior. Finally, we infer an upper limit for the strength of the field and the associated lower limit for the timescale of its action in order to redistribute angular momentum in stellar interiors.}, author = {Bugnet, Lisa Annabelle and Prat, V. and Mathis, S. and Astoul, A. and Augustson, K. and García, R. A. and Mathur, S. and Amard, L. and Neiner, C.}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, stars, oscillations / stars, magnetic field / stars, interiors / stars, evolution / stars, rotation}, publisher = {EDP Sciences}, title = {{Magnetic signatures on mixed-mode frequencies: I. An axisymmetric fossil field inside the core of red giants}}, doi = {10.1051/0004-6361/202039159}, volume = {650}, year = {2021}, } @article{11606, abstract = {Context. Our knowledge of the dynamics of stars has undergone a revolution through the simultaneous large amount of high-quality photometric observations collected by space-based asteroseismology and ground-based high-precision spectropolarimetry. They allowed us to probe the internal rotation of stars and their surface magnetism in the whole Hertzsprung-Russell diagram. However, new methods should still be developed to probe the deep magnetic fields in these stars. Aims. Our goal is to provide seismic diagnoses that allow us to probe the internal magnetism of stars. Methods. We focused on asymptotic low-frequency gravity modes and high-frequency acoustic modes. Using a first-order perturbative theory, we derived magnetic splittings of their frequencies as explicit functions of stellar parameters. Results. As in the case of rotation, we show that asymptotic gravity and acoustic modes can allow us to probe the different components of the magnetic field in the cavities in which they propagate. This again demonstrates the high potential of using mixed-modes when this is possible.}, author = {Mathis, S. and Bugnet, Lisa Annabelle and Prat, V. and Augustson, K. and Mathur, S. and Garcia, R. A.}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, keywords = {Space and Planetary Science, Astronomy and Astrophysics, asteroseismology / waves / stars, magnetic field / stars, oscillations / methods, analytical}, publisher = {EDP Sciences}, title = {{Probing the internal magnetism of stars using asymptotic magneto-asteroseismology}}, doi = {10.1051/0004-6361/202039180}, volume = {647}, year = {2021}, } @inproceedings{11649, abstract = {While operating communication networks adaptively may improve utilization and performance, frequent adjustments also introduce an algorithmic challenge: the re-optimization of traffic engineering solutions is time-consuming and may limit the granularity at which a network can be adjusted. This paper is motivated by question whether the reactivity of a network can be improved by re-optimizing solutions dynamically rather than from scratch, especially if inputs such as link weights do not change significantly. This paper explores to what extent dynamic algorithms can be used to speed up fundamental tasks in network operations. We specifically investigate optimizations related to traffic engineering (namely shortest paths and maximum flow computations), but also consider spanning tree and matching applications. While prior work on dynamic graph algorithms focusses on link insertions and deletions, we are interested in the practical problem of link weight changes. We revisit existing upper bounds in the weight-dynamic model, and present several novel lower bounds on the amortized runtime for recomputing solutions. In general, we find that the potential performance gains depend on the application, and there are also strict limitations on what can be achieved, even if link weights change only slightly.}, author = {Henzinger, Monika H and Paz, Ami and Schmid, Stefan}, booktitle = {IFIP Networking Conference}, issn = {1861-2288}, location = { Espoo and Helsinki, Finland}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{On the complexity of weight-dynamic network algorithms}}, doi = {10.23919/ifipnetworking52078.2021.9472803}, year = {2021}, } @article{11663, abstract = {Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas) and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability. In this article, we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem. (1) For dynamic spanner, the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case update time for maintaining a 3-spanner and O(n5/9) for maintaining a 5-spanner. We give a O(1)k log3 (n) high-probability worst-case time bound for maintaining a (2k-1)-spanner, which yields the first worst-case polylog update time for all constant k. (All the results above maintain the optimal tradeoff of stretch 2k-1 and Õ(n1+1/k) edges.) (2) For dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O(log 5 (n)) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2+ϵ)-approximate, and hence not maximal. Our results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: An algorithm is said to have worst-case expected update time ɑ if for every update σ, the expected time to process σ is at most ɑ. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: A worst-case expected update time of O(1) still allows for the possibility that every 1/f(n) updates requires ϴ (f(n)) time to process, for arbitrarily high f(n). In this article, we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: The query time remains the same, while the update time increases by a factor of O(log 2(n)). Thus, we achieve our results in two steps: (1) First, we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times. (2) Then, we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms.}, author = {Bernstein, Aaron and Forster, Sebastian and Henzinger, Monika H}, issn = {1549-6333}, journal = {ACM Transactions on Algorithms}, number = {4}, publisher = {Association for Computing Machinery}, title = {{A deamortization approach for dynamic spanner and dynamic maximal matching}}, doi = {10.1145/3469833}, volume = {17}, year = {2021}, } @article{11756, abstract = {We give two fully dynamic algorithms that maintain a (1 + ε)-approximation of the weight M of a minimum spanning forest (MSF) of an n-node graph G with edges weights in [1, W ], for any ε > 0. (1) Our deterministic algorithm takes O (W 2 log W /ε3) worst-case update time, which is O (1) if both W and ε are constants. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case O (log W /ε4) update time if W = O ((m∗)1/6/log2/3 n), where m∗ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. We complement our algorithmic results with two cell-probe lower bounds for dynamically maintaining an approximation of the weight of an MSF of a graph.}, author = {Henzinger, Monika H and Peng, Pan}, issn = {0890-5401}, journal = {Information and Computation}, number = {12}, publisher = {Elsevier}, title = {{Constant-time dynamic weight approximation for minimum spanning forest}}, doi = {10.1016/j.ic.2021.104805}, volume = {281}, year = {2021}, } @inproceedings{11771, abstract = {Classic dynamic data structure problems maintain a data structure subject to a sequence S of updates and they answer queries using the latest version of the data structure, i.e., the data structure after processing the whole sequence. To handle operations that change the sequence S of updates, Demaine et al. [7] introduced retroactive data structures (RDS). A retroactive operation modifies the update sequence S in a given position t, called time, and either creates or cancels an update in S at time t. A fully retroactive data structure supports queries at any time t: a query at time t is answered using only the updates of S up to time t. While efficient RDS have been proposed for classic data structures, e.g., stack, priority queue and binary search tree, the retroactive version of graph problems are rarely studied. In this paper we study retroactive graph problems including connectivity, minimum spanning forest (MSF), maximum degree, etc. We show that under the OMv conjecture (proposed by Henzinger et al. [15]), there does not exist fully RDS maintaining connectivity or MSF, or incremental fully RDS maintaining the maximum degree with 𝑂(𝑛1−𝜖) time per operation, for any constant 𝜖>0. Furthermore, We provide RDS with almost tight time per operation. We give fully RDS for maintaining the maximum degree, connectivity and MSF in 𝑂̃ (𝑛) time per operation. We also give an algorithm for the incremental (insertion-only) fully retroactive connectivity with 𝑂̃ (1) time per operation, showing that the lower bound cannot be extended to this setting. We also study a restricted version of RDS, where the only change to S is the swap of neighboring updates and show that for this problem we can beat the above hardness result. This also implies the first non-trivial dynamic Reeb graph computation algorithm.}, author = {Henzinger, Monika H and Wu, Xiaowei}, booktitle = {17th International Symposium on Algorithms and Data Structures}, isbn = {9783030835071}, issn = {1611-3349}, location = {Virtual}, pages = {471–484}, publisher = {Springer Nature}, title = {{Upper and lower bounds for fully retroactive graph problems}}, doi = {10.1007/978-3-030-83508-8_34}, volume = {12808}, year = {2021}, } @inproceedings{11814, abstract = {Differentially private algorithms protect individuals in data analysis scenarios by ensuring that there is only a weak correlation between the existence of the user in the data and the result of the analysis. Dynamic graph algorithms maintain the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph where nodes or edges are inserted or deleted over time. They output the value of the solution after each update operation, i.e., continuously. We study (event-level and user-level) differentially private algorithms for graph problems under continual observation, i.e., differentially private dynamic graph algorithms. We present event-level private algorithms for partially dynamic counting-based problems such as triangle count that improve the additive error by a polynomial factor (in the length T of the update sequence) on the state of the art, resulting in the first algorithms with additive error polylogarithmic in T. We also give ε-differentially private and partially dynamic algorithms for minimum spanning tree, minimum cut, densest subgraph, and maximum matching. The additive error of our improved MST algorithm is O(W log^{3/2}T / ε), where W is the maximum weight of any edge, which, as we show, is tight up to a (√{log T} / ε)-factor. For the other problems, we present a partially-dynamic algorithm with multiplicative error (1+β) for any constant β > 0 and additive error O(W log(nW) log(T) / (ε β)). Finally, we show that the additive error for a broad class of dynamic graph algorithms with user-level privacy must be linear in the value of the output solution’s range.}, author = {Fichtenberger, Hendrik and Henzinger, Monika H and Ost, Wolfgang}, booktitle = {29th Annual European Symposium on Algorithms}, isbn = {9783959772044}, issn = {1868-8969}, location = {Lisbon, Portual}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Differentially private algorithms for graphs under continual observation}}, doi = {10.4230/LIPIcs.ESA.2021.42}, volume = {204}, year = {2021}, } @article{11886, abstract = {We present a deterministic (1+𝑜(1))-approximation (𝑛1/2+𝑜(1)+𝐷1+𝑜(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the \sf CONGEST model); here 𝑛 is the number of nodes in the network, 𝐷 is its (hop) diameter, and edge weights are positive integers from 1 to poly(𝑛). This is the first nontrivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+𝑜(1))-approximation 𝑂̃ (𝑛√𝐷1/4+𝐷)-time algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565--573] by a factor of as large as 𝑛1/8, and (ii) the 𝑂(𝜖−1log𝜖−1)-approximation factor of Lenzen and Patt-Shamir's 𝑂̃ (𝑛1/2+𝜖+𝐷)-time algorithm [in Proceedings of STOC, 2013, pp. 381--390] within the same running time. (Throughout, we use 𝑂̃ (⋅) to hide polylogarithmic factors in 𝑛.) Our running time matches the known time lower bound of Ω(𝑛/log𝑛‾‾‾‾‾‾‾√+𝐷) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433--456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40--57]. It also implies a (2+𝑜(1))-approximation (𝑛1/2+𝑜(1)+𝐷1+𝑜(1))-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an (𝑛𝑜(1),𝑜(1))-hop set of size 𝑛1+𝑜(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434--446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375--382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153--162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+𝑜(1))-approximation 𝑛𝑜(1)-time algorithm on congested cliques, and (ii) a (1+𝑜(1))-approximation 𝑛𝑜(1)-pass 𝑛1+𝑜(1)-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565--573]. The second result partially answers an open problem raised by McGregor in 2006 [List of Open Problems in Sublinear Algorithms: Problem 14].}, author = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon}, issn = {1095-7111}, journal = {SIAM Journal on Computing}, number = {3}, pages = {STOC16--98--STOC16--137}, publisher = {Society for Industrial & Applied Mathematics}, title = {{A deterministic almost-tight distributed algorithm for approximating single-source shortest paths}}, doi = {10.1137/16m1097808}, volume = {50}, year = {2021}, } @inproceedings{11919, abstract = {Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and it is preferable to perform the computations on a sparse skeleton of the given graph that roughly preserves the shortest paths information. Spanners and emulators serve this purpose. Unfortunately, very little is known about dynamically maintaining sparse spanners and emulators as the graph is modified by a sequence of edge insertions and deletions. This paper develops fast dynamic algorithms for spanner and emulator maintenance and provides evidence from fine-grained complexity that these algorithms are tight. For unweighted undirected m-edge n-node graphs we obtain the following results. Under the popular OMv conjecture, there can be no decremental or incremental algorithm that maintains an n1+o(1) edge (purely additive) +nδ-emulator for any δ < 1/2 with arbitrary polynomial preprocessing time and total update time m1+o(1). Also, under the Combinatorial k-Clique hypothesis, any fully dynamic combinatorial algorithm that maintains an n1+o(1) edge (1 + ∊, no(1))-spanner or emulator for small ∊ must either have preprocessing time mn1–o(1) or amortized update time m1–o(1). Both of our conditional lower bounds are tight. As the above fully dynamic lower bound only applies to combinatorial algorithms, we also develop an algebraic spanner algorithm that improves over the m1–o(1) update time for dense graphs. For any constant ∊ ∊ (0, 1], there is a fully dynamic algorithm with worst-case update time O(n1.529) that whp maintains an n1+o(1) edge (1 + ∊, no(1))-spanner. Our new algebraic techniques allow us to also obtain a new fully dynamic algorithm for All-Pairs Shortest Paths (APSP) that can perform both edge updates and can report shortest paths in worst-case time O(n1.9), which are correct whp. This is the first path-reporting fully dynamic APSP algorithm with a truly subquadratic query time that beats O(n2.5) update time. It works against an oblivious adversary. Finally, we give two applications of our new dynamic spanner algorithms: (1) a fully dynamic (1 + ∊)-approximate APSP algorithm with update time O(n1.529) that can report approximate shortest paths in n1+o(1) time per query; previous subquadratic update/query algorithms could only report the distance, but not obtain the paths; (2) a fully dynamic algorithm for near-2-approximate Steiner tree maintenance with both terminal and edge updates.}, author = {Bergamaschi, Thiago and Henzinger, Monika H and Gutenberg, Maximilian Probst and Williams, Virginia Vassilevska and Wein, Nicole}, booktitle = {32nd Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Alexandria, VA, United States}, pages = {1836--1855}, publisher = {Society for Industrial and Applied Mathematics}, title = {{New techniques and fine-grained hardness for dynamic near-additive spanners}}, doi = {10.1137/1.9781611976465.110}, year = {2021}, } @inproceedings{11923, abstract = {We consider the following online optimization problem. We are given a graph G and each vertex of the graph is assigned to one of ℓ servers, where servers have capacity k and we assume that the graph has ℓ · k vertices. Initially, G does not contain any edges and then the edges of G are revealed one-by-one. The goal is to design an online algorithm ONL, which always places the connected components induced by the revealed edges on the same server and never exceeds the server capacities by more than ∊k for constant ∊ > 0. Whenever ONL learns about a new edge, the algorithm is allowed to move vertices from one server to another. Its objective is to minimize the number of vertex moves. More specifically, ONL should minimize the competitive ratio: the total cost ONL incurs compared to an optimal offline algorithm OPT. The problem was recently introduced by Henzinger et al. (SIGMETRICS'2019) and is related to classic online problems such as online paging and scheduling. It finds applications in the context of resource allocation in the cloud and for optimizing distributed data structures such as union–find data structures. Our main contribution is a polynomial-time randomized algorithm, that is asymptotically optimal: we derive an upper bound of O(log ℓ + log k) on its competitive ratio and show that no randomized online algorithm can achieve a competitive ratio of less than Ω(log ℓ + log k). We also settle the open problem of the achievable competitive ratio by deterministic online algorithms, by deriving a competitive ratio of Θ(ℓ log k); to this end, we present an improved lower bound as well as a deterministic polynomial-time online algorithm. Our algorithms rely on a novel technique which combines efficient integer programming with a combinatorial approach for maintaining ILP solutions. More precisely, we use an ILP to assign the connected components induced by the revealed edges to the servers; this is similar to existing approximation schemes for scheduling algorithms. However, we cannot obtain our competitive ratios if we run the ILP after each edge insertion. Instead, we identify certain types of edge insertions, after which we can manually obtain an optimal ILP solution at zero cost without resolving the ILP. We believe this technique is of independent interest and will find further applications in the future.}, author = {Henzinger, Monika H and Neumann, Stefan and Räcke, Harald and Schmid, Stefan}, booktitle = {32nd Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Alexandria, VA, United States}, pages = {2799--2818}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Tight bounds for online graph partitioning}}, doi = {10.1137/1.9781611976465.166}, year = {2021}, } @inproceedings{11920, abstract = {In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal min(O(log n), f) approximation factor. (Throughout, m, n, f, and C are parameters denoting the maximum number of sets, number of elements, frequency, and the cost range.) In the high-frequency range, when f = Ω(log n), this was achieved by a deterministic O(log n)-approximation algorithm with O(f log n) amortized update time [Gupta et al. STOC'17]. In the low-frequency range, the line of work by Gupta et al. [STOC'17], Abboud et al. [STOC'19], and Bhattacharya et al. [ICALP'15, IPCO'17, FOCS'19] led to a deterministic (1 + ∊) f-approximation algorithm with O(f log(Cn)/∊2) amortized update time. In this paper we improve the latter update time and provide the first bounds that subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms. We obtain: (1) (1 + ∊) f-approximation ratio in O(f log2(Cn)/∊3) worst-case update time: No non-trivial worst-case update time was previously known for dynamic set cover. Our bound subsumes and improves by a logarithmic factor the O(log3 n/poly(∊)) worst-case update time for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1) by Bhattacharya et al. [SODA'17]. (2) (1 + ∊) f-approximation ratio in O ((f2/∊3) + (f/∊2) log C) amortized update time: This result improves the previous O(f log (Cn)/∊2) update time bound for most values of f in the low-frequency range, i.e. whenever f = o(log n). It is the first that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA'19] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). These results are achieved by leveraging the approximate complementary slackness and background schedulers techniques. These techniques were used in the local update scheme for dynamic vertex cover. Our main technical contribution is to adapt these techniques within the global update scheme of Bhattacharya et al. [FOCS'19] for the dynamic set cover problem.}, author = {Bhattacharya, Sayan and Henzinger, Monika H and Nanongkai, Danupon and Wu, Xiaowei}, booktitle = {32nd Annual ACM-SIAM Symposium on Discrete Algorithms}, location = {Alexandria, VA, United States}, pages = {2537--2549}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Dynamic set cover: Improved amortized and worst-case update time}}, doi = {10.1137/1.9781611976465.150}, year = {2021}, } @inproceedings{11931, abstract = {Clustering is one of the most fundamental problems in unsupervised learning with a large number of applications. However, classical clustering algorithms assume that the data is static, thus failing to capture many real-world applications where data is constantly changing and evolving. Driven by this, we study the metric k-center clustering problem in the fully dynamic setting, where the goal is to efficiently maintain a clustering while supporting an intermixed sequence of insertions and deletions of points. This model also supports queries of the form (1) report whether a given point is a center or (2) determine the cluster a point is assigned to. We present a deterministic dynamic algorithm for the k-center clustering problem that provably achieves a (2 + ∊)-approximation in nearly logarithmic update and query time, if the underlying metric has bounded doubling dimension, its aspect ratio is bounded by a polynomial and ∊ is a constant. An important feature of our algorithm is that the update and query times are independent of k. We confirm the practical relevance of this feature via an extensive experimental study which shows that for large values of k, our algorithmic construction outperforms the state-of-the-art algorithm in terms of solution quality and running time.}, author = {Goranci, Gramoz and Henzinger, Monika H and Leniowski, Dariusz and Schulz, Christian and Svozil, Alexander}, booktitle = {2021 Proceedings of the Workshop on Algorithm Engineering and Experiments}, issn = {2164-0300}, location = {Alexandria, VA, United States}, pages = {143 --153}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Fully dynamic k-center clustering in low dimensional metrics}}, doi = {10.1137/1.9781611976472.11}, year = {2021}, } @article{11956, abstract = {Controlling the selectivity of a chemical reaction with external stimuli is common in thermal processes, but rare in visible-light photocatalysis. Here we show that the redox potential of a carbon nitride photocatalyst (CN-OA-m) can be tuned by changing the irradiation wavelength to generate electron holes with different oxidation potentials. This tuning was the key to realizing photo-chemo-enzymatic cascades that give either the (S)- or the (R)-enantiomer of phenylethanol. In combination with an unspecific peroxygenase from Agrocybe aegerita, green light irradiation of CN-OA-m led to the enantioselective hydroxylation of ethylbenzene to (R)-1-phenylethanol (99 % ee). In contrast, blue light irradiation triggered the photocatalytic oxidation of ethylbenzene to acetophenone, which in turn was enantioselectively reduced with an alcohol dehydrogenase from Rhodococcus ruber to form (S)-1-phenylethanol (93 % ee).}, author = {Schmermund, Luca and Reischauer, Susanne and Bierbaumer, Sarah and Winkler, Christoph K. and Diaz‐Rodriguez, Alba and Edwards, Lee J. and Kara, Selin and Mielke, Tamara and Cartwright, Jared and Grogan, Gideon and Pieber, Bartholomäus and Kroutil, Wolfgang}, issn = {1521-3773}, journal = {Angewandte Chemie International Edition}, number = {13}, pages = {6965--6969}, publisher = {Wiley}, title = {{Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways}}, doi = {10.1002/anie.202100164}, volume = {60}, year = {2021}, } @article{11965, abstract = {Metallaphotocatalytic cross-coupling reactions are typically carried out by combining homogeneous or heterogeneous photocatalysts with a soluble nickel complex. Previous attempts to realize recyclable catalytic systems use immobilized iridium complexes to harvest light. We present bifunctional materials based on semiconductors for metallaphotocatalytic C−S cross-coupling reactions that can be reused without losing their catalytic activity. Key to the success is the permanent immobilization of a nickel complex on the surface of a heterogeneous semiconductor through phosphonic acid anchors. The optimized catalyst harvests a broad range of the visible light spectrum and requires a nickel loading of only ∼0.1 mol %.}, author = {Reischauer, Susanne and Pieber, Bartholomäus}, issn = {2367-0932}, journal = {ChemPhotoChem}, number = {8}, pages = {716--720}, publisher = {Wiley}, title = {{Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions}}, doi = {10.1002/cptc.202100062}, volume = {5}, year = {2021}, } @article{11972, abstract = {Carbon dots have been previosly immobilized on titanium dioxide to generate photocatalysts for pollutant degradation and water splitting. Here we demonstrate that these nanocomposites are valuable photocatalysts for metallaphotocatalytic carbon–heteroatom cross-couplings. These sustainable materials show a large applicability, high photostability, excellent reusability, and broadly absorb across the visible-light spectrum.}, author = {Zhao, Zhouxiang and Reischauer, Susanne and Pieber, Bartholomäus and Delbianco, Martina}, issn = {1463-9270}, journal = {Green Chemistry}, number = {12}, pages = {4524--4530}, publisher = {Royal Society of Chemistry}, title = {{Carbon dot/TiO₂ nanocomposites as photocatalysts for metallaphotocatalytic carbon-heteroatom cross-couplings}}, doi = {10.1039/d1gc01284c}, volume = {23}, year = {2021}, } @article{11974, abstract = {Visible light photocatalysis has become a powerful tool in organic synthesis that uses photons as traceless, sustainable reagents. Most of the activities in the field focus on the development of new reactions via common photoredox cycles, but recently a number of exciting new concepts and strategies entered less charted territories. We survey approaches that enable the use of longer wavelengths and show that the wavelength and intensity of photons are import parameters that enable tuning of the reactivity of a photocatalyst to control or change the selectivity of chemical reactions. In addition, we discuss recent efforts to substitute strong reductants, such as elemental lithium and sodium, by light and technological advances in the field.}, author = {Reischauer, Susanne and Pieber, Bartholomäus}, issn = {2589-0042}, journal = {iScience}, number = {3}, publisher = {Elsevier}, title = {{Emerging concepts in photocatalytic organic synthesis}}, doi = {10.1016/j.isci.2021.102209}, volume = {24}, year = {2021}, } @article{11981, abstract = {The cleavage of benzyl ethers by catalytic hydrogenolysis or Birch reduction suffers from poor functional group compatibility and limits their use as a protecting group. The visible-light-mediated debenzylation disclosed here renders benzyl ethers temporary protective groups, enabling new orthogonal protection strategies. Using 2,3-dichloro-5,6-dicyano-1,4-benzoquinone (DDQ) as a stoichiometric or catalytic photooxidant, benzyl ethers can be cleaved in the presence of azides, alkenes, and alkynes. The reaction time can be reduced from hours to minutes in continuous flow.}, author = {Cavedon, Cristian and Sletten, Eric T. and Madani, Amiera and Niemeyer, Olaf and Seeberger, Peter H. and Pieber, Bartholomäus}, issn = {1523-7052}, journal = {Organic Letters}, number = {2}, pages = {514--518}, publisher = {American Chemical Society}, title = {{Visible-light-mediated oxidative debenzylation enables the use of benzyl ethers as temporary protecting groups}}, doi = {10.1021/acs.orglett.0c04026}, volume = {23}, year = {2021}, } @article{12071, abstract = {Despite many efforts to rationalize the strongly correlated electronic ground states in doped Mott insulators, the nature of the doping-induced insulator-to-metal transition is still a subject under intensive investigation. Here, we probe the nanoscale electronic structure of the Mott insulator Sr₂IrO₄δ with low-temperature scanning tunneling microscopy and find an enhanced local density of states (LDOS) inside the Mott gap at the location of individual defects which we interpret as defects at apical oxygen sites. A chiral behavior in the topography for those defects has been observed. We also visualize the local enhanced conductance arising from the overlapping of defect states which induces finite LDOS inside of the Mott gap. By combining these findings with the typical spatial extension of isolated defects of about 2 nm, our results indicate that the insulator-to-metal transition in Sr₂IrO₄−δ could be percolative in nature.}, author = {Sun, Zhixiang and Guevara, Jose M. and Sykora, Steffen and Paerschke, Ekaterina and Manna, Kaustuv and Maljuk, Andrey and Wurmehl, Sabine and van den Brink, Jeroen and Büchner, Bernd and Hess, Christian}, issn = {2643-1564}, journal = {Physical Review Research}, number = {2}, publisher = {American Physical Society}, title = {{Evidence for a percolative Mott insulator-metal transition in doped Sr₂IrO₄}}, doi = {10.1103/physrevresearch.3.023075}, volume = {3}, year = {2021}, } @unpublished{12070, abstract = {Controlling the selectivity of a chemical reaction with external stimuli is common in thermal processes, but rare in visible-light photocatalysis. Here we show that the redox potential of a carbon nitride photocatalyst (CN-OA-m) can be tuned by changing the irradiation wavelength to generate electron holes with different oxidation potentials. This tuning was the key to realizing photo-chemo-enzymatic cascades that give either the (S)- or the (R)-enantiomer of phenylethanol. In combination with an unspecific peroxygenase from Agrocybe aegerita, green light irradiation of CN-OA-m led to the enantioselective hydroxylation of ethylbenzene to (R)-1-phenylethanol (99% ee). In contrast, blue light irradiation triggered the photocatalytic oxidation of ethylbenzene to acetophenone, which in turn was enantioselectively reduced with an alcohol dehydrogenase from Rhodococcus ruber to form (S)-1-phenylethanol (93% ee).}, author = {Schmermund, Luca and Reischauer, Susanne and Bierbaumer, Sarah and Winkler, Christoph and Diaz-Rodriguez, Alba and Edwards, Lee J. and Kara, Selin and Mielke, Tamara and Cartwright, Jared and Grogan, Gideon and Pieber, Bartholomäus and Kroutil, Wolfgang}, publisher = {ChemRxiv}, title = {{Switching between enantiomers by combining chromoselective photocatalysis and biocatalysis}}, doi = {10.26434/chemrxiv.13521527}, year = {2021}, } @unpublished{12068, abstract = {Metallaphotocatalysis typically requires a photocatalyst to harness the energy of visible-light and transfer it to a transition metal catalyst to trigger chemical reactions. The most prominent example is the merger of photo- and nickel catalysis that unlocked various cross-couplings. However, the high reactivity of excited photocatalyst can lead to unwanted side reactions thus limiting this approach. Here we show that a bipyridine ligand that is subtly decorated with two carbazole groups forms a nickel complex that absorbs visible-light and promotes several carbon–heteroatom cross-couplings in the absence of an exogenous photocatalysts. The ligand can be polymerized in a simple one-step procedure to afford a porous organic polymer that can be used for heterogeneous nickel catalysis in the same reactions. The material can be easily recovered and reused multiple times maintaining high catalytic activity and selectivity.}, author = {Cavedon, Cristian and Gisbertz, Sebastian and Vogl, Sarah and Richter, Noah and Schrottke, Stefanie and Teutloff, Christian and Seeberger, Peter H. and Thomas, Arne and Pieber, Bartholomäus}, publisher = {ChemRxiv}, title = {{Photocatalyst-free, visible-light-mediated nickel catalyzed carbon–heteroatom cross-couplings}}, doi = {10.26434/chemrxiv-2021-kt2wr}, year = {2021}, } @unpublished{12077, abstract = {We compare the Manin-type conjecture for Campana points recently formulated by Pieropan, Smeets, Tanimoto and V\'{a}rilly-Alvarado with an alternative prediction of Browning and Van Valckenborgh in the special case of the orbifold $(\mathbb{P}^1,D)$, where $D =\frac{1}{2}[0]+\frac{1}{2}[1]+\frac{1}{2}[\infty]$. We find that the two predicted leading constants do not agree, and we discuss whether thin sets could explain this discrepancy. Motivated by this, we provide a counterexample to the Manin-type conjecture for Campana points, by considering orbifolds corresponding to squareful values of binary quadratic forms.}, author = {Shute, Alec L}, booktitle = {arXiv}, title = {{On the leading constant in the Manin-type conjecture for Campana points}}, doi = {10.48550/arXiv.2104.14946}, year = {2021}, } @unpublished{12076, abstract = {We find an asymptotic formula for the number of primitive vectors $(z_1,\ldots,z_4)\in (\mathbb{Z}_{\neq 0})^4$ such that $z_1,\ldots, z_4$ are all squareful and bounded by $B$, and $z_1+\cdots + z_4 = 0$. Our result agrees in the power of $B$ and $\log B$ with the Campana-Manin conjecture of Pieropan, Smeets, Tanimoto and V\'{a}rilly-Alvarado.}, author = {Shute, Alec L}, booktitle = {arXiv}, title = {{Sums of four squareful numbers}}, doi = {10.48550/arXiv.2104.06966}, year = {2021}, } @unpublished{12314, abstract = {In literature, there are two different definitions of elliptic divisibility sequences. The first one says that a sequence of integers $\{h_n\}_{n\geq 0}$ is an elliptic divisibility sequence if it verifies the recurrence relation $h_{m+n}h_{m-n}h_{r}^2=h_{m+r}h_{m-r}h_{n}^2-h_{n+r}h_{n-r}h_{m}^2$ for every natural number $m\geq n\geq r$. The second definition says that a sequence of integers $\{\beta_n\}_{n\geq 0}$ is an elliptic divisibility sequence if it is the sequence of the square roots (chosen with an appropriate sign) of the denominators of the abscissas of the iterates of a point on a rational elliptic curve. It is well-known that the two sequences are not equivalent. Hence, given a sequence of the denominators $\{\beta_n\}_{n\geq 0}$, in general does not hold $\beta_{m+n}\beta_{m-n}\beta_{r}^2=\beta_{m+r}\beta_{m-r}\beta_{n}^2-\beta_{n+r}\beta_{n-r}\beta_{m}^2$ for $m\geq n\geq r$. We will prove that the recurrence relation above holds for $\{\beta_n\}_{n\geq 0}$ under some conditions on the indexes $m$, $n$, and $r$.}, author = {Verzobio, Matteo}, booktitle = {arXiv}, title = {{A recurrence relation for elliptic divisibility sequences}}, doi = {10.48550/arXiv.2102.07573}, year = {2021}, } @article{12667, abstract = {Unlike crystalline atomic and ionic solids, texture development due to crystallographically preferred growth in colloidal crystals is less studied. Here we investigate the underlying mechanisms of the texture evolution in an evaporation-induced colloidal assembly process through experiments, modeling, and theoretical analysis. In this widely used approach to obtain large-area colloidal crystals, the colloidal particles are driven to the meniscus via the evaporation of a solvent or matrix precursor solution where they close-pack to form a face-centered cubic colloidal assembly. Via two-dimensional large-area crystallographic mapping, we show that the initial crystal orientation is dominated by the interaction of particles with the meniscus, resulting in the expected coalignment of the close-packed direction with the local meniscus geometry. By combining with crystal structure analysis at a single-particle level, we further reveal that, at the later stage of self-assembly, however, the colloidal crystal undergoes a gradual rotation facilitated by geometrically necessary dislocations (GNDs) and achieves a large-area uniform crystallographic orientation with the close-packed direction perpendicular to the meniscus and parallel to the growth direction. Classical slip analysis, finite element-based mechanical simulation, computational colloidal assembly modeling, and continuum theory unequivocally show that these GNDs result from the tensile stress field along the meniscus direction due to the constrained shrinkage of the colloidal crystal during drying. The generation of GNDs with specific slip systems within individual grains leads to crystallographic rotation to accommodate the mechanical stress. The mechanistic understanding reported here can be utilized to control crystallographic features of colloidal assemblies, and may provide further insights into crystallographically preferred growth in synthetic, biological, and geological crystals.}, author = {Li, Ling and Goodrich, Carl Peter and Yang, Haizhao and Phillips, Katherine R. and Jia, Zian and Chen, Hongshun and Wang, Lifeng and Zhong, Jinjin and Liu, Anhua and Lu, Jianfeng and Shuai, Jianwei and Brenner, Michael P. and Spaepen, Frans and Aizenberg, Joanna}, issn = {1091-6490}, journal = {PNAS}, number = {32}, publisher = {Proceedings of the National Academy of Sciences}, title = {{Microscopic origins of the crystallographically preferred growth in evaporation-induced colloidal crystals}}, doi = {10.1073/pnas.2107588118}, volume = {118}, year = {2021}, } @inbook{7941, abstract = {Expansion microscopy is a recently developed super-resolution imaging technique, which provides an alternative to optics-based methods such as deterministic approaches (e.g. STED) or stochastic approaches (e.g. PALM/STORM). The idea behind expansion microscopy is to embed the biological sample in a swellable gel, and then to expand it isotropically, thereby increasing the distance between the fluorophores. This approach breaks the diffraction barrier by simply separating the emission point-spread-functions of the fluorophores. The resolution attainable in expansion microscopy is thus directly dependent on the separation that can be achieved, i.e. on the expansion factor. The original implementation of the technique achieved an expansion factor of fourfold, for a resolution of 70–80 nm. The subsequently developed X10 method achieves an expansion factor of 10-fold, for a resolution of 25–30 nm. This technique can be implemented with minimal technical requirements on any standard fluorescence microscope, and is more easily applied for multi-color imaging than either deterministic or stochastic super-resolution approaches. This renders X10 expansion microscopy a highly promising tool for new biological discoveries, as discussed here, and as demonstrated by several recent applications.}, author = {Truckenbrodt, Sven M and Rizzoli, Silvio O.}, booktitle = {Methods in Cell Biology}, isbn = {978012820807-6}, issn = {0091-679X}, pages = {33--56}, publisher = {Elsevier}, title = {{Simple multi-color super-resolution by X10 microscopy}}, doi = {10.1016/bs.mcb.2020.04.016}, volume = {161}, year = {2021}, } @article{11446, abstract = {Suppose that n is not a prime power and not twice a prime power. We prove that for any Hausdorff compactum X with a free action of the symmetric group Sn, there exists an Sn-equivariant map X→Rn whose image avoids the diagonal {(x,x,…,x)∈Rn∣x∈R}. Previously, the special cases of this statement for certain X were usually proved using the equivartiant obstruction theory. Such calculations are difficult and may become infeasible past the first (primary) obstruction. We take a different approach which allows us to prove the vanishing of all obstructions simultaneously. The essential step in the proof is classifying the possible degrees of Sn-equivariant maps from the boundary ∂Δn−1 of (n−1)-simplex to itself. Existence of equivariant maps between spaces is important for many questions arising from discrete mathematics and geometry, such as Kneser’s conjecture, the Square Peg conjecture, the Splitting Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate the utility of our result applying it to one such question, a specific instance of envy-free division problem.}, author = {Avvakumov, Sergey and Kudrya, Sergey}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, keywords = {Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, Theoretical Computer Science}, number = {3}, pages = {1202--1216}, publisher = {Springer Nature}, title = {{Vanishing of all equivariant obstructions and the mapping degree}}, doi = {10.1007/s00454-021-00299-z}, volume = {66}, year = {2021}, } @article{9097, abstract = {Psoriasis is a chronic inflammatory skin disease clinically characterized by the appearance of red colored, well-demarcated plaques with thickened skin and with silvery scales. Recent studies have established the involvement of a complex signalling network of interactions between cytokines, immune cells and skin cells called keratinocytes. Keratinocytes form the cells of the outermost layer of the skin (epidermis). Visible plaques in psoriasis are developed due to the fast proliferation and unusual differentiation of keratinocyte cells. Despite that, the exact mechanism of the appearance of these plaques in the cytokine-immune cell network is not clear. A mathematical model embodying interactions between key immune cells believed to be involved in psoriasis, keratinocytes and relevant cytokines has been developed. The complex network formed of these interactions poses several challenges. Here, we choose to study subnetworks of this complex network and initially focus on interactions involving TNFα, IL-23/IL-17, and IL-15. These are chosen based on known evidence of their therapeutic efficacy. In addition, we explore the role of IL-15 in the pathogenesis of psoriasis and its potential as a future drug target for a novel treatment option. We perform steady state analyses for these subnetworks and demonstrate that the interactions between cells, driven by cytokines could cause the emergence of a psoriasis state (hyper-proliferation of keratinocytes) when levels of TNFα, IL-23/IL-17 or IL-15 are increased. The model results explain and support the clinical potentiality of anti-cytokine treatments. Interestingly, our results suggest different dynamic scenarios underpin the pathogenesis of psoriasis, depending upon the dominant cytokines of subnetworks. We observed that the increase in the level of IL-23/IL-17 and IL-15 could lead to psoriasis via a bistable route, whereas an increase in the level of TNFα would lead to a monotonic and gradual disease progression. Further, we demonstrate how this insight, bistability, could be exploited to improve the current therapies and develop novel treatment strategies for psoriasis.}, author = {Pandey, Rakesh and Al-Nuaimi, Yusur and Mishra, Rajiv Kumar and Spurgeon, Sarah K. and Goodfellow, Marc}, issn = {20452322}, journal = {Scientific Reports}, publisher = {Springer Nature}, title = {{Role of subnetworks mediated by TNF α, IL-23/IL-17 and IL-15 in a network involved in the pathogenesis of psoriasis}}, doi = {10.1038/s41598-020-80507-7}, volume = {11}, year = {2021}, } @inbook{9245, abstract = {Tissue morphogenesis is driven by mechanical forces triggering cell movements and shape changes. Quantitatively measuring tension within tissues is of great importance for understanding the role of mechanical signals acting on the cell and tissue level during morphogenesis. Here we introduce laser ablation as a useful tool to probe tissue tension within the granulosa layer, an epithelial monolayer of somatic cells that surround the zebrafish female gamete during folliculogenesis. We describe in detail how to isolate follicles, mount samples, perform laser surgery, and analyze the data.}, author = {Xia, Peng and Heisenberg, Carl-Philipp J}, booktitle = {Germline Development in the Zebrafish}, editor = {Dosch, Roland}, isbn = {978-1-0716-0969-9}, issn = {1940-6029}, keywords = {Tissue tension, Morphogenesis, Laser ablation, Zebrafish folliculogenesis, Granulosa cells}, pages = {117--128}, publisher = {Humana}, title = {{Quantifying tissue tension in the granulosa layer after laser surgery}}, doi = {10.1007/978-1-0716-0970-5_10}, volume = {2218}, year = {2021}, } @article{9282, abstract = {Several Ising-type magnetic van der Waals (vdW) materials exhibit stable magnetic ground states. Despite these clear experimental demonstrations, a complete theoretical and microscopic understanding of their magnetic anisotropy is still lacking. In particular, the validity limit of identifying their one-dimensional (1-D) Ising nature has remained uninvestigated in a quantitative way. Here we performed the complete mapping of magnetic anisotropy for a prototypical Ising vdW magnet FePS3 for the first time. Combining torque magnetometry measurements with their magnetostatic model analysis and the relativistic density functional total energy calculations, we successfully constructed the three-dimensional (3-D) mappings of the magnetic anisotropy in terms of magnetic torque and energy. The results not only quantitatively confirm that the easy axis is perpendicular to the ab plane, but also reveal the anisotropies within the ab, ac, and bc planes. Our approach can be applied to the detailed quantitative study of magnetism in vdW materials.}, author = {Nauman, Muhammad and Kiem, Do Hoon and Lee, Sungmin and Son, Suhan and Park, J-G and Kang, Woun and Han, Myung Joon and Jo, Youn Jung}, issn = {2053-1583}, journal = {2D Materials}, keywords = {Mechanical Engineering, General Materials Science, Mechanics of Materials, General Chemistry, Condensed Matter Physics}, number = {3}, publisher = {IOP Publishing}, title = {{Complete mapping of magnetic anisotropy for prototype Ising van der Waals FePS3}}, doi = {10.1088/2053-1583/abeed3}, volume = {8}, year = {2021}, }