@misc{9192, abstract = {Here are the research data underlying the publication " Effects of fine-scale population structure on inbreeding in a long-term study of snapdragons (Antirrhinum majus)." Further information are summed up in the README document.}, author = {Surendranadh, Parvathy and Arathoon, Louise S and Baskett, Carina and Field, David and Pickup, Melinda and Barton, Nicholas H}, publisher = {Institute of Science and Technology Austria}, title = {{Effects of fine-scale population structure on the distribution of heterozygosity in a long-term study of Antirrhinum majus}}, doi = {10.15479/AT:ISTA:9192}, year = {2021}, } @misc{9949, author = {Vicoso, Beatriz}, publisher = {Institute of Science and Technology Austria}, title = {{Data from Hyulmans et al 2021, "Transitions to asexuality and evolution of gene expression in Artemia brine shrimp"}}, doi = {10.15479/AT:ISTA:9949}, year = {2021}, } @article{8997, abstract = {Phenomenological relations such as Ohm’s or Fourier’s law have a venerable history in physics but are still scarce in biology. This situation restrains predictive theory. Here, we build on bacterial “growth laws,” which capture physiological feedback between translation and cell growth, to construct a minimal biophysical model for the combined action of ribosome-targeting antibiotics. Our model predicts drug interactions like antagonism or synergy solely from responses to individual drugs. We provide analytical results for limiting cases, which agree well with numerical results. We systematically refine the model by including direct physical interactions of different antibiotics on the ribosome. In a limiting case, our model provides a mechanistic underpinning for recent predictions of higher-order interactions that were derived using entropy maximization. We further refine the model to include the effects of antibiotics that mimic starvation and the presence of resistance genes. We describe the impact of a starvation-mimicking antibiotic on drug interactions analytically and verify it experimentally. Our extended model suggests a change in the type of drug interaction that depends on the strength of resistance, which challenges established rescaling paradigms. We experimentally show that the presence of unregulated resistance genes can lead to altered drug interaction, which agrees with the prediction of the model. While minimal, the model is readily adaptable and opens the door to predicting interactions of second and higher-order in a broad range of biological systems.}, author = {Kavcic, Bor and Tkačik, Gašper and Bollenbach, Tobias}, issn = {1553-7358}, journal = {PLOS Computational Biology}, keywords = {Modelling and Simulation, Genetics, Molecular Biology, Antibiotics, Drug interactions}, publisher = {Public Library of Science}, title = {{Minimal biophysical model of combined antibiotic action}}, doi = {10.1371/journal.pcbi.1008529}, volume = {17}, year = {2021}, } @article{9283, abstract = {Gene expression levels are influenced by multiple coexisting molecular mechanisms. Some of these interactions such as those of transcription factors and promoters have been studied extensively. However, predicting phenotypes of gene regulatory networks (GRNs) remains a major challenge. Here, we use a well-defined synthetic GRN to study in Escherichia coli how network phenotypes depend on local genetic context, i.e. the genetic neighborhood of a transcription factor and its relative position. We show that one GRN with fixed topology can display not only quantitatively but also qualitatively different phenotypes, depending solely on the local genetic context of its components. Transcriptional read-through is the main molecular mechanism that places one transcriptional unit (TU) within two separate regulons without the need for complex regulatory sequences. We propose that relative order of individual TUs, with its potential for combinatorial complexity, plays an important role in shaping phenotypes of GRNs.}, author = {Nagy-Staron, Anna A and Tomasek, Kathrin and Caruso Carter, Caroline and Sonnleitner, Elisabeth and Kavcic, Bor and Paixão, Tiago and Guet, Calin C}, issn = {2050-084X}, journal = {eLife}, keywords = {Genetics and Molecular Biology}, publisher = {eLife Sciences Publications}, title = {{Local genetic context shapes the function of a gene regulatory network}}, doi = {10.7554/elife.65993}, volume = {10}, year = {2021}, } @article{10184, abstract = {We introduce a novel technique to automatically decompose an input object’s volume into a set of parts that can be represented by two opposite height fields. Such decomposition enables the manufacturing of individual parts using two-piece reusable rigid molds. Our decomposition strategy relies on a new energy formulation that utilizes a pre-computed signal on the mesh volume representing the accessibility for a predefined set of extraction directions. Thanks to this novel formulation, our method allows for efficient optimization of a fabrication-aware partitioning of volumes in a completely automatic way. We demonstrate the efficacy of our approach by generating valid volume partitionings for a wide range of complex objects and physically reproducing several of them.}, author = {Alderighi, Thomas and Malomo, Luigi and Bickel, Bernd and Cignoni, Paolo and Pietroni, Nico}, issn = {1557-7368 }, journal = {ACM Transactions on Graphics}, number = {6}, publisher = {Association for Computing Machinery}, title = {{Volume decomposition for two-piece rigid casting}}, doi = {10.1145/3478513.3480555}, volume = {40}, year = {2021}, } @article{9541, abstract = {The Massively Parallel Computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP’86], we obtain O(log Δ + log log n)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with O(nɛ) space on each machine for any constant ɛ > 0. These algorithms also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel et al. [DISC’17].}, author = {Czumaj, Artur and Davies, Peter and Parter, Merav}, issn = {1549-6333}, journal = {ACM Transactions on Algorithms}, number = {2}, publisher = {Association for Computing Machinery}, title = {{Graph sparsification for derandomizing massively parallel computation with low space}}, doi = {10.1145/3451992}, volume = {17}, year = {2021}, } @article{10134, abstract = {We investigate the effect of coupling between translational and internal degrees of freedom of composite quantum particles on their localization in a random potential. We show that entanglement between the two degrees of freedom weakens localization due to the upper bound imposed on the inverse participation ratio by purity of a quantum state. We perform numerical calculations for a two-particle system bound by a harmonic force in a 1D disordered lattice and a rigid rotor in a 2D disordered lattice. We illustrate that the coupling has a dramatic effect on localization properties, even with a small number of internal states participating in quantum dynamics.}, author = {Suzuki, Fumika and Lemeshko, Mikhail and Zurek, Wojciech H. and Krems, Roman V.}, issn = {1079-7114}, journal = {Physical Review Letters}, keywords = {General Physics and Astronomy}, number = {16}, publisher = {American Physical Society }, title = {{Anderson localization of composite particles}}, doi = {10.1103/physrevlett.127.160602}, volume = {127}, year = {2021}, } @inproceedings{9678, abstract = {We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(Δ^5) rounds in graphs of maximum degree Δ, while we improve it to O(Δ^4) and also prove a lower bound of Ω(Δ). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.}, author = {Brandt, Sebastian and Keller, Barbara and Rybicki, Joel and Suomela, Jukka and Uitto, Jara}, booktitle = {Annual ACM Symposium on Parallelism in Algorithms and Architectures}, isbn = {9781450380706}, location = { Virtual Event, United States}, pages = {129--139}, title = {{Efficient load-balancing through distributed token dropping}}, doi = {10.1145/3409964.3461785}, year = {2021}, } @article{8286, abstract = {We consider the following dynamic load-balancing process: given an underlying graph G with n nodes, in each step t≥ 0, one unit of load is created, and placed at a randomly chosen graph node. In the same step, the chosen node picks a random neighbor, and the two nodes balance their loads by averaging them. We are interested in the expected gap between the minimum and maximum loads at nodes as the process progresses, and its dependence on n and on the graph structure. Variants of the above graphical balanced allocation process have been studied previously by Peres, Talwar, and Wieder [Peres et al., 2015], and by Sauerwald and Sun [Sauerwald and Sun, 2015]. These authors left as open the question of characterizing the gap in the case of cycle graphs in the dynamic case, where weights are created during the algorithm’s execution. For this case, the only known upper bound is of 𝒪(n log n), following from a majorization argument due to [Peres et al., 2015], which analyzes a related graphical allocation process. In this paper, we provide an upper bound of 𝒪 (√n log n) on the expected gap of the above process for cycles of length n. We introduce a new potential analysis technique, which enables us to bound the difference in load between k-hop neighbors on the cycle, for any k ≤ n/2. We complement this with a "gap covering" argument, which bounds the maximum value of the gap by bounding its value across all possible subsets of a certain structure, and recursively bounding the gaps within each subset. We provide analytical and experimental evidence that our upper bound on the gap is tight up to a logarithmic factor. }, author = {Alistarh, Dan-Adrian and Nadiradze, Giorgi and Sabour, Amirmojtaba}, issn = {1432-0541}, journal = {Algorithmica}, location = {Virtual, Online; Germany}, publisher = {Springer Nature}, title = {{Dynamic averaging load balancing on cycles}}, doi = {10.1007/s00453-021-00905-9}, year = {2021}, } @phdthesis{9733, abstract = {This thesis is the result of the research carried out by the author during his PhD at IST Austria between 2017 and 2021. It mainly focuses on the Fröhlich polaron model, specifically to its regime of strong coupling. This model, which is rigorously introduced and discussed in the introduction, has been of great interest in condensed matter physics and field theory for more than eighty years. It is used to describe an electron interacting with the atoms of a solid material (the strength of this interaction is modeled by the presence of a coupling constant α in the Hamiltonian of the system). The particular regime examined here, which is mathematically described by considering the limit α →∞, displays many interesting features related to the emergence of classical behavior, which allows for a simplified effective description of the system under analysis. The properties, the range of validity and a quantitative analysis of the precision of such classical approximations are the main object of the present work. We specify our investigation to the study of the ground state energy of the system, its dynamics and its effective mass. For each of these problems, we provide in the introduction an overview of the previously known results and a detailed account of the original contributions by the author.}, author = {Feliciangeli, Dario}, issn = {2663-337X}, pages = {180}, publisher = {Institute of Science and Technology Austria}, title = {{The polaron at strong coupling}}, doi = {10.15479/at:ista:9733}, year = {2021}, } @article{9571, abstract = {As the size and complexity of models and datasets grow, so does the need for communication-efficient variants of stochastic gradient descent that can be deployed to perform parallel model training. One popular communication-compression method for data-parallel SGD is QSGD (Alistarh et al., 2017), which quantizes and encodes gradients to reduce communication costs. The baseline variant of QSGD provides strong theoretical guarantees, however, for practical purposes, the authors proposed a heuristic variant which we call QSGDinf, which demonstrated impressive empirical gains for distributed training of large neural networks. In this paper, we build on this work to propose a new gradient quantization scheme, and show that it has both stronger theoretical guarantees than QSGD, and matches and exceeds the empirical performance of the QSGDinf heuristic and of other compression methods.}, author = {Ramezani-Kebrya, Ali and Faghri, Fartash and Markov, Ilya and Aksenov, Vitalii and Alistarh, Dan-Adrian and Roy, Daniel M.}, issn = {15337928}, journal = {Journal of Machine Learning Research}, number = {114}, pages = {1−43}, publisher = {Journal of Machine Learning Research}, title = {{NUQSGD: Provably communication-efficient data-parallel SGD via nonuniform quantization}}, volume = {22}, year = {2021}, } @article{8544, abstract = {The synaptotrophic hypothesis posits that synapse formation stabilizes dendritic branches, yet this hypothesis has not been causally tested in vivo in the mammalian brain. Presynaptic ligand cerebellin-1 (Cbln1) and postsynaptic receptor GluD2 mediate synaptogenesis between granule cells and Purkinje cells in the molecular layer of the cerebellar cortex. Here we show that sparse but not global knockout of GluD2 causes under-elaboration of Purkinje cell dendrites in the deep molecular layer and overelaboration in the superficial molecular layer. Developmental, overexpression, structure-function, and genetic epistasis analyses indicate that dendrite morphogenesis defects result from competitive synaptogenesis in a Cbln1/GluD2-dependent manner. A generative model of dendritic growth based on competitive synaptogenesis largely recapitulates GluD2 sparse and global knockout phenotypes. Our results support the synaptotrophic hypothesis at initial stages of dendrite development, suggest a second mode in which cumulative synapse formation inhibits further dendrite growth, and highlight the importance of competition in dendrite morphogenesis.}, author = {Takeo, Yukari H. and Shuster, S. Andrew and Jiang, Linnie and Hu, Miley and Luginbuhl, David J. and Rülicke, Thomas and Contreras, Ximena and Hippenmeyer, Simon and Wagner, Mark J. and Ganguli, Surya and Luo, Liqun}, issn = {1097-4199}, journal = {Neuron}, number = {4}, pages = {P629--644.E8}, publisher = {Elsevier}, title = {{GluD2- and Cbln1-mediated competitive synaptogenesis shapes the dendritic arbors of cerebellar Purkinje cells}}, doi = {10.1016/j.neuron.2020.11.028}, volume = {109}, year = {2021}, } @unpublished{9791, abstract = {We provide a definition of the effective mass for the classical polaron described by the Landau-Pekar equations. It is based on a novel variational principle, minimizing the energy functional over states with given (initial) velocity. The resulting formula for the polaron's effective mass agrees with the prediction by Landau and Pekar.}, author = {Feliciangeli, Dario and Rademacher, Simone Anna Elvira and Seiringer, Robert}, booktitle = {arXiv}, title = {{The effective mass problem for the Landau-Pekar equations}}, year = {2021}, } @article{7553, abstract = {Normative theories and statistical inference provide complementary approaches for the study of biological systems. A normative theory postulates that organisms have adapted to efficiently solve essential tasks, and proceeds to mathematically work out testable consequences of such optimality; parameters that maximize the hypothesized organismal function can be derived ab initio, without reference to experimental data. In contrast, statistical inference focuses on efficient utilization of data to learn model parameters, without reference to any a priori notion of biological function, utility, or fitness. Traditionally, these two approaches were developed independently and applied separately. Here we unify them in a coherent Bayesian framework that embeds a normative theory into a family of maximum-entropy “optimization priors.” This family defines a smooth interpolation between a data-rich inference regime (characteristic of “bottom-up” statistical models), and a data-limited ab inito prediction regime (characteristic of “top-down” normative theory). We demonstrate the applicability of our framework using data from the visual cortex, and argue that the flexibility it affords is essential to address a number of fundamental challenges relating to inference and prediction in complex, high-dimensional biological problems.}, author = {Mlynarski, Wiktor F and Hledik, Michal and Sokolowski, Thomas R and Tkačik, Gašper}, journal = {Neuron}, number = {7}, pages = {1227--1241.e5}, publisher = {Cell Press}, title = {{Statistical analysis and optimality of neural systems}}, doi = {10.1016/j.neuron.2021.01.020}, volume = {109}, year = {2021}, } @inproceedings{10598, abstract = { We consider the problem of estimating a signal from measurements obtained via a generalized linear model. We focus on estimators based on approximate message passing (AMP), a family of iterative algorithms with many appealing features: the performance of AMP in the high-dimensional limit can be succinctly characterized under suitable model assumptions; AMP can also be tailored to the empirical distribution of the signal entries, and for a wide class of estimation problems, AMP is conjectured to be optimal among all polynomial-time algorithms. However, a major issue of AMP is that in many models (such as phase retrieval), it requires an initialization correlated with the ground-truth signal and independent from the measurement matrix. Assuming that such an initialization is available is typically not realistic. In this paper, we solve this problem by proposing an AMP algorithm initialized with a spectral estimator. With such an initialization, the standard AMP analysis fails since the spectral estimator depends in a complicated way on the design matrix. Our main contribution is a rigorous characterization of the performance of AMP with spectral initialization in the high-dimensional limit. The key technical idea is to define and analyze a two-phase artificial AMP algorithm that first produces the spectral estimator, and then closely approximates the iterates of the true AMP. We also provide numerical results that demonstrate the validity of the proposed approach. }, author = {Mondelli, Marco and Venkataramanan, Ramji}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, issn = {2640-3498}, location = {Virtual, San Diego, CA, United States}, pages = {397--405}, publisher = {ML Research Press}, title = {{Approximate message passing with spectral initialization for generalized linear models}}, volume = {130}, year = {2021}, } @article{8196, abstract = {This paper aims to obtain a strong convergence result for a Douglas–Rachford splitting method with inertial extrapolation step for finding a zero of the sum of two set-valued maximal monotone operators without any further assumption of uniform monotonicity on any of the involved maximal monotone operators. Furthermore, our proposed method is easy to implement and the inertial factor in our proposed method is a natural choice. Our method of proof is of independent interest. Finally, some numerical implementations are given to confirm the theoretical analysis.}, author = {Shehu, Yekini and Dong, Qiao-Li and Liu, Lu-Lu and Yao, Jen-Chih}, issn = {1573-2924}, journal = {Optimization and Engineering}, pages = {2627--2653}, publisher = {Springer Nature}, title = {{New strong convergence method for the sum of two maximal monotone operators}}, doi = {10.1007/s11081-020-09544-5}, volume = {22}, year = {2021}, } @article{8911, abstract = {In the worldwide endeavor for disruptive quantum technologies, germanium is emerging as a versatile material to realize devices capable of encoding, processing, or transmitting quantum information. These devices leverage special properties of the germanium valence-band states, commonly known as holes, such as their inherently strong spin-orbit coupling and the ability to host superconducting pairing correlations. In this Review, we initially introduce the physics of holes in low-dimensional germanium structures with key insights from a theoretical perspective. We then examine the material science progress underpinning germanium-based planar heterostructures and nanowires. We review the most significant experimental results demonstrating key building blocks for quantum technology, such as an electrically driven universal quantum gate set with spin qubits in quantum dots and superconductor-semiconductor devices for hybrid quantum systems. We conclude by identifying the most promising prospects toward scalable quantum information processing. }, author = {Scappucci, Giordano and Kloeffel, Christoph and Zwanenburg, Floris A. and Loss, Daniel and Myronov, Maksym and Zhang, Jian-Jun and Franceschi, Silvano De and Katsaros, Georgios and Veldhorst, Menno}, issn = {2058-8437}, journal = {Nature Reviews Materials}, pages = {926–943 }, publisher = {Springer Nature}, title = {{The germanium quantum information route}}, doi = {10.1038/s41578-020-00262-z}, volume = {6}, year = {2021}, } @article{8338, abstract = {Canonical parametrisations of classical confocal coordinate systems are introduced and exploited to construct non-planar analogues of incircular (IC) nets on individual quadrics and systems of confocal quadrics. Intimate connections with classical deformations of quadrics that are isometric along asymptotic lines and circular cross-sections of quadrics are revealed. The existence of octahedral webs of surfaces of Blaschke type generated by asymptotic and characteristic lines that are diagonally related to lines of curvature is proved theoretically and established constructively. Appropriate samplings (grids) of these webs lead to three-dimensional extensions of non-planar IC nets. Three-dimensional octahedral grids composed of planes and spatially extending (checkerboard) IC-nets are shown to arise in connection with systems of confocal quadrics in Minkowski space. In this context, the Laguerre geometric notion of conical octahedral grids of planes is introduced. The latter generalise the octahedral grids derived from systems of confocal quadrics in Minkowski space. An explicit construction of conical octahedral grids is presented. The results are accompanied by various illustrations which are based on the explicit formulae provided by the theory.}, author = {Akopyan, Arseniy and Bobenko, Alexander I. and Schief, Wolfgang K. and Techter, Jan}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {938--976}, publisher = {Springer Nature}, title = {{On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs}}, doi = {10.1007/s00454-020-00240-w}, volume = {66}, year = {2021}, } @article{7939, abstract = {We design fast deterministic algorithms for distance computation in the Congested Clique model. Our key contributions include: A (2+ϵ)-approximation for all-pairs shortest paths in O(log2n/ϵ) rounds on unweighted undirected graphs. With a small additional additive factor, this also applies for weighted graphs. This is the first sub-polynomial constant-factor approximation for APSP in this model. A (1+ϵ)-approximation for multi-source shortest paths from O(n−−√) sources in O(log2n/ϵ) rounds on weighted undirected graphs. This is the first sub-polynomial algorithm obtaining this approximation for a set of sources of polynomial size. Our main techniques are new distance tools that are obtained via improved algorithms for sparse matrix multiplication, which we leverage to construct efficient hopsets and shortest paths. Furthermore, our techniques extend to additional distance problems for which we improve upon the state-of-the-art, including diameter approximation, and an exact single-source shortest paths algorithm for weighted undirected graphs in O~(n1/6) rounds. }, author = {Censor-Hillel, Keren and Dory, Michal and Korhonen, Janne and Leitersdorf, Dean}, issn = {1432-0452}, journal = {Distributed Computing}, pages = {463--487}, publisher = {Springer Nature}, title = {{Fast approximate shortest paths in the congested clique}}, doi = {10.1007/s00446-020-00380-5}, volume = {34}, year = {2021}, } @article{8248, abstract = {We consider the following setting: suppose that we are given a manifold M in Rd with positive reach. Moreover assume that we have an embedded simplical complex A without boundary, whose vertex set lies on the manifold, is sufficiently dense and such that all simplices in A have sufficient quality. We prove that if, locally, interiors of the projection of the simplices onto the tangent space do not intersect, then A is a triangulation of the manifold, that is, they are homeomorphic.}, author = {Boissonnat, Jean-Daniel and Dyer, Ramsay and Ghosh, Arijit and Lieutier, Andre and Wintraecken, Mathijs}, issn = {1432-0444}, journal = {Discrete and Computational Geometry}, pages = {666--686}, publisher = {Springer Nature}, title = {{Local conditions for triangulating submanifolds of Euclidean space}}, doi = {10.1007/s00454-020-00233-9}, volume = {66}, year = {2021}, }