@unpublished{8182, abstract = {Suppose that $n\neq p^k$ and $n\neq 2p^k$ for all $k$ and all primes $p$. We prove that for any Hausdorff compactum $X$ with a free action of the symmetric group $\mathfrak S_n$ there exists an $\mathfrak S_n$-equivariant map $X \to {\mathbb R}^n$ whose image avoids the diagonal $\{(x,x\dots,x)\in {\mathbb R}^n|x\in {\mathbb 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 $\mathfrak S_n$-equivariant maps from the boundary $\partial\Delta^{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}, booktitle = {arXiv}, publisher = {arXiv}, title = {{Vanishing of all equivariant obstructions and the mapping degree}}, year = {2019}, } @unpublished{8185, abstract = {In this paper we study envy-free division problems. The classical approach to some of such problems, used by David Gale, reduces to considering continuous maps of a simplex to itself and finding sufficient conditions when this map hits the center of the simplex. The mere continuity is not sufficient for such a conclusion, the usual assumption (for example, in the Knaster--Kuratowski--Mazurkiewicz and the Gale theorem) is a certain boundary condition. We follow Erel Segal-Halevi, Fr\'ed\'eric Meunier, and Shira Zerbib, and replace the boundary condition by another assumption, which has the economic meaning of possibility for a player to prefer an empty part in the segment partition problem. We solve the problem positively when $n$, the number of players that divide the segment, is a prime power, and we provide counterexamples for every $n$ which is not a prime power. We also provide counterexamples relevant to a wider class of fair or envy-free partition problems when $n$ is odd and not a prime power.}, author = {Avvakumov, Sergey and Karasev, Roman}, booktitle = {arXiv}, title = {{Envy-free division using mapping degree}}, doi = {10.48550/arXiv.1907.11183}, year = {2019}, } @unpublished{7524, abstract = {We prove a lower bound for the free energy (per unit volume) of the two-dimensional Bose gas in the thermodynamic limit. We show that the free energy at density $\rho$ and inverse temperature $\beta$ differs from the one of the non-interacting system by the correction term $4 \pi \rho^2 |\ln a^2 \rho|^{-1} (2 - [1 - \beta_{\mathrm{c}}/\beta]_+^2)$. Here $a$ is the scattering length of the interaction potential, $[\cdot]_+ = \max\{ 0, \cdot \}$ and $\beta_{\mathrm{c}}$ is the inverse Berezinskii--Kosterlitz--Thouless critical temperature for superfluidity. The result is valid in the dilute limit $a^2\rho \ll 1$ and if $\beta \rho \gtrsim 1$.}, author = {Deuchert, Andreas and Mayer, Simon and Seiringer, Robert}, booktitle = {arXiv:1910.03372}, pages = {61}, publisher = {ArXiv}, title = {{The free energy of the two-dimensional dilute Bose gas. I. Lower bound}}, year = {2019}, } @article{6608, abstract = {We use the canonical bases produced by the tri-partition algorithm in (Edelsbrunner and Ölsböck, 2018) to open and close holes in a polyhedral complex, K. In a concrete application, we consider the Delaunay mosaic of a finite set, we let K be an Alpha complex, and we use the persistence diagram of the distance function to guide the hole opening and closing operations. The dependences between the holes define a partial order on the cells in K that characterizes what can and what cannot be constructed using the operations. The relations in this partial order reveal structural information about the underlying filtration of complexes beyond what is expressed by the persistence diagram.}, author = {Edelsbrunner, Herbert and Ölsböck, Katharina}, journal = {Computer Aided Geometric Design}, pages = {1--15}, publisher = {Elsevier}, title = {{Holes and dependences in an ordered complex}}, doi = {10.1016/j.cagd.2019.06.003}, volume = {73}, year = {2019}, } @inproceedings{6677, abstract = {The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography. We show that solving the END−OF−METERED−LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT. Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n).}, author = {Choudhuri, Arka Rai and Hubáček, Pavel and Kamath Hosdurg, Chethan and Pietrzak, Krzysztof Z and Rosen, Alon and Rothblum, Guy N.}, booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019}, isbn = {9781450367059}, location = {Phoenix, AZ, United States}, pages = {1103--1114}, publisher = {ACM Press}, title = {{Finding a Nash equilibrium is no easier than breaking Fiat-Shamir}}, doi = {10.1145/3313276.3316400}, year = {2019}, } @article{5986, abstract = {Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.}, author = {Lubiw, Anna and Masárová, Zuzana and Wagner, Uli}, issn = {1432-0444}, journal = {Discrete & Computational Geometry}, number = {4}, pages = {880--898}, publisher = {Springer Nature}, title = {{A proof of the orbit conjecture for flipping edge-labelled triangulations}}, doi = {10.1007/s00454-018-0035-8}, volume = {61}, year = {2019}, } @article{5886, abstract = {Problems involving quantum impurities, in which one or a few particles are interacting with a macroscopic environment, represent a pervasive paradigm, spanning across atomic, molecular, and condensed-matter physics. In this paper we introduce new variational approaches to quantum impurities and apply them to the Fröhlich polaron–a quasiparticle formed out of an electron (or other point-like impurity) in a polar medium, and to the angulon–a quasiparticle formed out of a rotating molecule in a bosonic bath. We benchmark these approaches against established theories, evaluating their accuracy as a function of the impurity-bath coupling.}, author = {Li, Xiang and Bighin, Giacomo and Yakaboylu, Enderalp and Lemeshko, Mikhail}, issn = {00268976}, journal = {Molecular Physics}, publisher = {Taylor and Francis}, title = {{Variational approaches to quantum impurities: from the Fröhlich polaron to the angulon}}, doi = {10.1080/00268976.2019.1567852}, year = {2019}, } @inproceedings{6556, abstract = {Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.}, author = {Huszár, Kristóf and Spreer, Jonathan}, booktitle = {35th International Symposium on Computational Geometry}, isbn = {978-3-95977-104-7}, issn = {1868-8969}, keywords = {computational 3-manifold topology, fixed-parameter tractability, layered triangulations, structural graph theory, treewidth, cutwidth, Heegaard genus}, location = {Portland, Oregon, United States}, pages = {44:1--44:20}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{3-manifold triangulations with small treewidth}}, doi = {10.4230/LIPIcs.SoCG.2019.44}, volume = {129}, year = {2019}, } @article{7093, abstract = {In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth. In view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs). We derive these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann, Schultens and Saito by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 18(k+1) (resp. 4(3k+1)).}, author = {Huszár, Kristóf and Spreer, Jonathan and Wagner, Uli}, issn = {1920-180X}, journal = {Journal of Computational Geometry}, number = {2}, pages = {70–98}, publisher = {Computational Geometry Laborartoy}, title = {{On the treewidth of triangulated 3-manifolds}}, doi = {10.20382/JOGC.V10I2A5}, volume = {10}, year = {2019}, } @article{7197, abstract = {During bacterial cell division, the tubulin-homolog FtsZ forms a ring-like structure at the center of the cell. This Z-ring not only organizes the division machinery, but treadmilling of FtsZ filaments was also found to play a key role in distributing proteins at the division site. What regulates the architecture, dynamics and stability of the Z-ring is currently unknown, but FtsZ-associated proteins are known to play an important role. Here, using an in vitro reconstitution approach, we studied how the well-conserved protein ZapA affects FtsZ treadmilling and filament organization into large-scale patterns. Using high-resolution fluorescence microscopy and quantitative image analysis, we found that ZapA cooperatively increases the spatial order of the filament network, but binds only transiently to FtsZ filaments and has no effect on filament length and treadmilling velocity. Together, our data provides a model for how FtsZ-associated proteins can increase the precision and stability of the bacterial cell division machinery in a switch-like manner.}, author = {Dos Santos Caldas, Paulo R and Lopez Pelegrin, Maria D and Pearce, Daniel J. G. and Budanur, Nazmi B and Brugués, Jan and Loose, Martin}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA}}, doi = {10.1038/s41467-019-13702-4}, volume = {10}, year = {2019}, } @article{7210, abstract = {The rate of biological evolution depends on the fixation probability and on the fixation time of new mutants. Intensive research has focused on identifying population structures that augment the fixation probability of advantageous mutants. But these amplifiers of natural selection typically increase fixation time. Here we study population structures that achieve a tradeoff between fixation probability and time. First, we show that no amplifiers can have an asymptotically lower absorption time than the well-mixed population. Then we design population structures that substantially augment the fixation probability with just a minor increase in fixation time. Finally, we show that those structures enable higher effective rate of evolution than the well-mixed population provided that the rate of generating advantageous mutants is relatively low. Our work sheds light on how population structure affects the rate of evolution. Moreover, our structures could be useful for lab-based, medical, or industrial applications of evolutionary optimization.}, author = {Tkadlec, Josef and Pavlogiannis, Andreas and Chatterjee, Krishnendu and Nowak, Martin A.}, issn = {2399-3642}, journal = {Communications Biology}, publisher = {Springer Nature}, title = {{Population structure determines the tradeoff between fixation probability and fixation time}}, doi = {10.1038/s42003-019-0373-y}, volume = {2}, year = {2019}, } @inproceedings{10190, abstract = {The verification of concurrent programs remains an open challenge, as thread interaction has to be accounted for, which leads to state-space explosion. Stateless model checking battles this problem by exploring traces rather than states of the program. As there are exponentially many traces, dynamic partial-order reduction (DPOR) techniques are used to partition the trace space into equivalence classes, and explore a few representatives from each class. The standard equivalence that underlies most DPOR techniques is the happens-before equivalence, however recent works have spawned a vivid interest towards coarser equivalences. The efficiency of such approaches is a product of two parameters: (i) the size of the partitioning induced by the equivalence, and (ii) the time spent by the exploration algorithm in each class of the partitioning. In this work, we present a new equivalence, called value-happens-before and show that it has two appealing features. First, value-happens-before is always at least as coarse as the happens-before equivalence, and can be even exponentially coarser. Second, the value-happens-before partitioning is efficiently explorable when the number of threads is bounded. We present an algorithm called value-centric DPOR (VCDPOR), which explores the underlying partitioning using polynomial time per class. Finally, we perform an experimental evaluation of VCDPOR on various benchmarks, and compare it against other state-of-the-art approaches. Our results show that value-happens-before typically induces a significant reduction in the size of the underlying partitioning, which leads to a considerable reduction in the running time for exploring the whole partitioning.}, author = {Chatterjee, Krishnendu and Pavlogiannis, Andreas and Toman, Viktor}, booktitle = {Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications}, issn = {2475-1421}, keywords = {safety, risk, reliability and quality, software}, location = {Athens, Greece}, publisher = {ACM}, title = {{Value-centric dynamic partial order reduction}}, doi = {10.1145/3360550}, volume = {3}, year = {2019}, } @inproceedings{6673, abstract = {Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared state, which gets updated progressively. While the sequential variant of such algorithms usually specifies a fixed (but sometimes random) order in which the tasks should be performed, a standard approach to parallelizing such algorithms is to relax this constraint to allow for out-of-order parallel execution. This is the case for parallel implementations of Dijkstra's single-source shortest-paths (SSSP) algorithm, and for parallel Delaunay mesh triangulation. While many software frameworks parallelize incremental computation in this way, it is still not well understood whether this relaxed ordering approach can still provide any complexity guarantees. In this paper, we address this problem, and analyze the efficiency guarantees provided by a range of incremental algorithms when parallelized via relaxed schedulers. We show that, for algorithms such as Delaunay mesh triangulation and sorting by insertion, schedulers with a maximum relaxation factor of k in terms of the maximum priority inversion allowed will introduce a maximum amount of wasted work of O(łog n poly(k)), where n is the number of tasks to be executed. For SSSP, we show that the additional work is O(poly(k), dmax / wmin), where dmax is the maximum distance between two nodes, and wmin is the minimum such distance. In practical settings where n >> k, this suggests that the overheads of relaxation will be outweighed by the improved scalability of the relaxed scheduler. On the negative side, we provide lower bounds showing that certain algorithms will inherently incur a non-trivial amount of wasted work due to scheduler relaxation, even for relatively benign relaxed schedulers.}, author = {Alistarh, Dan-Adrian and Nadiradze, Giorgi and Koval, Nikita}, booktitle = {31st ACM Symposium on Parallelism in Algorithms and Architectures}, isbn = {9781450361842}, location = {Phoenix, AZ, United States}, pages = {145--154}, publisher = {ACM Press}, title = {{Efficiency guarantees for parallel incremental algorithms under relaxed schedulers}}, doi = {10.1145/3323165.3323201}, year = {2019}, } @article{7398, abstract = {Transporters of the solute carrier 6 (SLC6) family translocate their cognate substrate together with Na+ and Cl−. Detailed kinetic models exist for the transporters of GABA (GAT1/SLC6A1) and the monoamines dopamine (DAT/SLC6A3) and serotonin (SERT/SLC6A4). Here, we posited that the transport cycle of individual SLC6 transporters reflects the physiological requirements they operate under. We tested this hypothesis by analyzing the transport cycle of glycine transporter 1 (GlyT1/SLC6A9) and glycine transporter 2 (GlyT2/SLC6A5). GlyT2 is the only SLC6 family member known to translocate glycine, Na+, and Cl− in a 1:3:1 stoichiometry. We analyzed partial reactions in real time by electrophysiological recordings. Contrary to monoamine transporters, both GlyTs were found to have a high transport capacity driven by rapid return of the empty transporter after release of Cl− on the intracellular side. Rapid cycling of both GlyTs was further supported by highly cooperative binding of cosubstrate ions and substrate such that their forward transport mode was maintained even under conditions of elevated intracellular Na+ or Cl−. The most important differences in the transport cycle of GlyT1 and GlyT2 arose from the kinetics of charge movement and the resulting voltage-dependent rate-limiting reactions: the kinetics of GlyT1 were governed by transition of the substrate-bound transporter from outward- to inward-facing conformations, whereas the kinetics of GlyT2 were governed by Na+ binding (or a related conformational change). Kinetic modeling showed that the kinetics of GlyT1 are ideally suited for supplying the extracellular glycine levels required for NMDA receptor activation.}, author = {Erdem, Fatma Asli and Ilic, Marija and Koppensteiner, Peter and Gołacki, Jakub and Lubec, Gert and Freissmuth, Michael and Sandtner, Walter}, issn = {1540-7748}, journal = {The Journal of General Physiology}, number = {8}, pages = {1035--1050}, publisher = {Rockefeller University Press}, title = {{A comparison of the transport kinetics of glycine transporter 1 and glycine transporter 2}}, doi = {10.1085/jgp.201912318}, volume = {151}, year = {2019}, } @article{7395, abstract = {The mitochondrial electron transport chain complexes are organized into supercomplexes (SCs) of defined stoichiometry, which have been proposed to regulate electron flux via substrate channeling. We demonstrate that CoQ trapping in the isolated SC I+III2 limits complex (C)I turnover, arguing against channeling. The SC structure, resolved at up to 3.8 Å in four distinct states, suggests that CoQ oxidation may be rate limiting because of unequal access of CoQ to the active sites of CIII2. CI shows a transition between “closed” and “open” conformations, accompanied by the striking rotation of a key transmembrane helix. Furthermore, the state of CI affects the conformational flexibility within CIII2, demonstrating crosstalk between the enzymes. CoQ was identified at only three of the four binding sites in CIII2, suggesting that interaction with CI disrupts CIII2 symmetry in a functionally relevant manner. Together, these observations indicate a more nuanced functional role for the SCs.}, author = {Letts, James A and Fiedorczuk, Karol and Degliesposti, Gianluca and Skehel, Mark and Sazanov, Leonid A}, issn = {1097-2765}, journal = {Molecular Cell}, number = {6}, pages = {1131--1146.e6}, publisher = {Cell Press}, title = {{Structures of respiratory supercomplex I+III2 reveal functional and conformational crosstalk}}, doi = {10.1016/j.molcel.2019.07.022}, volume = {75}, year = {2019}, } @article{7405, abstract = {Biophysical modeling of neuronal networks helps to integrate and interpret rapidly growing and disparate experimental datasets at multiple scales. The NetPyNE tool (www.netpyne.org) provides both programmatic and graphical interfaces to develop data-driven multiscale network models in NEURON. NetPyNE clearly separates model parameters from implementation code. Users provide specifications at a high level via a standardized declarative language, for example connectivity rules, to create millions of cell-to-cell connections. NetPyNE then enables users to generate the NEURON network, run efficiently parallelized simulations, optimize and explore network parameters through automated batch runs, and use built-in functions for visualization and analysis – connectivity matrices, voltage traces, spike raster plots, local field potentials, and information theoretic measures. NetPyNE also facilitates model sharing by exporting and importing standardized formats (NeuroML and SONATA). NetPyNE is already being used to teach computational neuroscience students and by modelers to investigate brain regions and phenomena.}, author = {Dura-Bernal, Salvador and Suter, Benjamin and Gleeson, Padraig and Cantarelli, Matteo and Quintana, Adrian and Rodriguez, Facundo and Kedziora, David J and Chadderdon, George L and Kerr, Cliff C and Neymotin, Samuel A and McDougal, Robert A and Hines, Michael and Shepherd, Gordon MG and Lytton, William W}, issn = {2050-084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{NetPyNE, a tool for data-driven multiscale modeling of brain circuits}}, doi = {10.7554/elife.44494}, volume = {8}, year = {2019}, } @article{7400, abstract = {Suppressed recombination allows divergence between homologous sex chromosomes and the functionality of their genes. Here, we reveal patterns of the earliest stages of sex-chromosome evolution in the diploid dioecious herb Mercurialis annua on the basis of cytological analysis, de novo genome assembly and annotation, genetic mapping, exome resequencing of natural populations, and transcriptome analysis. The genome assembly contained 34,105 expressed genes, of which 10,076 were assigned to linkage groups. Genetic mapping and exome resequencing of individuals across the species range both identified the largest linkage group, LG1, as the sex chromosome. Although the sex chromosomes of M. annua are karyotypically homomorphic, we estimate that about one-third of the Y chromosome, containing 568 transcripts and spanning 22.3 cM in the corresponding female map, has ceased recombining. Nevertheless, we found limited evidence for Y-chromosome degeneration in terms of gene loss and pseudogenization, and most X- and Y-linked genes appear to have diverged in the period subsequent to speciation between M. annua and its sister species M. huetii, which shares the same sex-determining region. Taken together, our results suggest that the M. annua Y chromosome has at least two evolutionary strata: a small old stratum shared with M. huetii, and a more recent larger stratum that is probably unique to M. annua and that stopped recombining ∼1 MYA. Patterns of gene expression within the nonrecombining region are consistent with the idea that sexually antagonistic selection may have played a role in favoring suppressed recombination.}, author = {Veltsos, Paris and Ridout, Kate E. and Toups, Melissa A and González-Martínez, Santiago C. and Muyle, Aline and Emery, Olivier and Rastas, Pasi and Hudzieczek, Vojtech and Hobza, Roman and Vyskot, Boris and Marais, Gabriel A. B. and Filatov, Dmitry A. and Pannell, John R.}, issn = {1943-2631}, journal = {Genetics}, number = {3}, pages = {815--835}, publisher = {Genetics Society of America}, title = {{Early sex-chromosome evolution in the diploid dioecious plant Mercurialis annua}}, doi = {10.1534/genetics.119.302045}, volume = {212}, year = {2019}, } @article{7404, abstract = {The formation of neuronal dendrite branches is fundamental for the wiring and function of the nervous system. Indeed, dendrite branching enhances the coverage of the neuron's receptive field and modulates the initial processing of incoming stimuli. Complex dendrite patterns are achieved in vivo through a dynamic process of de novo branch formation, branch extension and retraction. The first step towards branch formation is the generation of a dynamic filopodium-like branchlet. The mechanisms underlying the initiation of dendrite branchlets are therefore crucial to the shaping of dendrites. Through in vivo time-lapse imaging of the subcellular localization of actin during the process of branching of Drosophila larva sensory neurons, combined with genetic analysis and electron tomography, we have identified the Actin-related protein (Arp) 2/3 complex as the major actin nucleator involved in the initiation of dendrite branchlet formation, under the control of the activator WAVE and of the small GTPase Rac1. Transient recruitment of an Arp2/3 component marks the site of branchlet initiation in vivo. These data position the activation of Arp2/3 as an early hub for the initiation of branchlet formation.}, author = {Stürner, Tomke and Tatarnikova, Anastasia and Müller, Jan and Schaffran, Barbara and Cuntz, Hermann and Zhang, Yun and Nemethova, Maria and Bogdan, Sven and Small, Vic and Tavosanis, Gaia}, issn = {1477-9129}, journal = {Development}, number = {7}, publisher = {The Company of Biologists}, title = {{Transient localization of the Arp2/3 complex initiates neuronal dendrite branching in vivo}}, doi = {10.1242/dev.171397}, volume = {146}, year = {2019}, } @inproceedings{7402, abstract = {Graph planning gives rise to fundamental algorithmic questions such as shortest path, traveling salesman problem, etc. A classical problem in discrete planning is to consider a weighted graph and construct a path that maximizes the sum of weights for a given time horizon T. However, in many scenarios, the time horizon is not fixed, but the stopping time is chosen according to some distribution such that the expected stopping time is T. If the stopping time distribution is not known, then to ensure robustness, the distribution is chosen by an adversary, to represent the worst-case scenario. A stationary plan for every vertex always chooses the same outgoing edge. For fixed horizon or fixed stopping-time distribution, stationary plans are not sufficient for optimality. Quite surprisingly we show that when an adversary chooses the stopping-time distribution with expected stopping time T, then stationary plans are sufficient. While computing optimal stationary plans for fixed horizon is NP-complete, we show that computing optimal stationary plans under adversarial stopping-time distribution can be achieved in polynomial time. Consequently, our polynomial-time algorithm for adversarial stopping time also computes an optimal plan among all possible plans.}, author = {Chatterjee, Krishnendu and Doyen, Laurent}, booktitle = {34th Annual ACM/IEEE Symposium on Logic in Computer Science}, isbn = {9781728136080}, location = {Vancouver, BC, Canada}, pages = {1--13}, publisher = {IEEE}, title = {{Graph planning with expected finite horizon}}, doi = {10.1109/lics.2019.8785706}, year = {2019}, } @article{7451, abstract = {We prove that the observable telegraph signal accompanying the bistability in the photon-blockade-breakdown regime of the driven and lossy Jaynes–Cummings model is the finite-size precursor of what in the thermodynamic limit is a genuine first-order phase transition. We construct a finite-size scaling of the system parameters to a well-defined thermodynamic limit, in which the system remains the same microscopic system, but the telegraph signal becomes macroscopic both in its timescale and intensity. The existence of such a finite-size scaling completes and justifies the classification of the photon-blockade-breakdown effect as a first-order dissipative quantum phase transition.}, author = {Vukics, A. and Dombi, A. and Fink, Johannes M and Domokos, P.}, issn = {2521-327X}, journal = {Quantum}, publisher = {Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften}, title = {{Finite-size scaling of the photon-blockade breakdown dissipative quantum phase transition}}, doi = {10.22331/q-2019-06-03-150}, volume = {3}, year = {2019}, } @inproceedings{7468, abstract = {We present a new proximal bundle method for Maximum-A-Posteriori (MAP) inference in structured energy minimization problems. The method optimizes a Lagrangean relaxation of the original energy minimization problem using a multi plane block-coordinate Frank-Wolfe method that takes advantage of the specific structure of the Lagrangean decomposition. We show empirically that our method outperforms state-of-the-art Lagrangean decomposition based algorithms on some challenging Markov Random Field, multi-label discrete tomography and graph matching problems.}, author = {Swoboda, Paul and Kolmogorov, Vladimir}, booktitle = {Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition}, isbn = {9781728132938}, issn = {10636919}, location = {Long Beach, CA, United States}, publisher = {IEEE}, title = {{Map inference via block-coordinate Frank-Wolfe algorithm}}, doi = {10.1109/CVPR.2019.01140}, volume = {2019-June}, year = {2019}, } @article{7415, author = {Morandell, Jasmin and Nicolas, Armel and Schwarz, Lena A and Novarino, Gaia}, issn = {0924-977X}, journal = {European Neuropsychopharmacology}, number = {Supplement 6}, pages = {S11--S12}, publisher = {Elsevier}, title = {{S.16.05 Illuminating the role of the e3 ubiquitin ligase cullin3 in brain development and autism}}, doi = {10.1016/j.euroneuro.2019.09.040}, volume = {29}, year = {2019}, } @article{7414, author = {Knaus, Lisa and Tarlungeanu, Dora-Clara and Novarino, Gaia}, issn = {0924-977X}, journal = {European Neuropsychopharmacology}, number = {Supplement 6}, pages = {S11}, publisher = {Elsevier}, title = {{S.16.03 A homozygous missense mutation in SLC7A5 leads to autism spectrum disorder and microcephaly}}, doi = {10.1016/j.euroneuro.2019.09.039}, volume = {29}, year = {2019}, } @article{7394, author = {Benková, Eva and Dagdas, Yasin}, issn = {1369-5266}, journal = {Current Opinion in Plant Biology}, number = {12}, pages = {A1--A2}, publisher = {Elsevier}, title = {{Editorial overview: Cell biology in the era of omics?}}, doi = {10.1016/j.pbi.2019.11.002}, volume = {52}, year = {2019}, } @inproceedings{7479, abstract = {Multi-exit architectures, in which a stack of processing layers is interleaved with early output layers, allow the processing of a test example to stop early and thus save computation time and/or energy. In this work, we propose a new training procedure for multi-exit architectures based on the principle of knowledge distillation. The method encourage searly exits to mimic later, more accurate exits, by matching their output probabilities. Experiments on CIFAR100 and ImageNet show that distillation-based training significantly improves the accuracy of early exits while maintaining state-of-the-art accuracy for late ones. The method is particularly beneficial when training data is limited and it allows a straightforward extension to semi-supervised learning,i.e. making use of unlabeled data at training time. Moreover, it takes only afew lines to implement and incurs almost no computational overhead at training time, and none at all at test time.}, author = {Bui Thi Mai, Phuong and Lampert, Christoph}, booktitle = {IEEE International Conference on Computer Vision}, isbn = {9781728148038}, issn = {15505499}, location = {Seoul, Korea}, pages = {1355--1364}, publisher = {IEEE}, title = {{Distillation-based training for multi-exit architectures}}, doi = {10.1109/ICCV.2019.00144}, volume = {2019-October}, year = {2019}, } @inproceedings{7542, abstract = {We present a novel class of convolutional neural networks (CNNs) for set functions,i.e., data indexed with the powerset of a finite set. The convolutions are derivedas linear, shift-equivariant functions for various notions of shifts on set functions.The framework is fundamentally different from graph convolutions based on theLaplacian, as it provides not one but several basic shifts, one for each element inthe ground set. Prototypical experiments with several set function classificationtasks on synthetic datasets and on datasets derived from real-world hypergraphsdemonstrate the potential of our new powerset CNNs.}, author = {Wendler, Chris and Alistarh, Dan-Adrian and Püschel, Markus}, issn = {1049-5258}, location = {Vancouver, Canada}, pages = {927--938}, publisher = {Neural Information Processing Systems Foundation}, title = {{Powerset convolutional neural networks}}, volume = {32}, year = {2019}, } @inbook{7513, abstract = {Social insects (i.e., ants, termites and the social bees and wasps) protect their colonies from disease using a combination of individual immunity and collectively performed defenses, termed social immunity. The first line of social immune defense is sanitary care, which is performed by colony members to protect their pathogen-exposed nestmates from developing an infection. If sanitary care fails and an infection becomes established, a second line of social immune defense is deployed to stop disease transmission within the colony and to protect the valuable queens, which together with the males are the reproductive individuals of the colony. Insect colonies are separated into these reproductive individuals and the sterile worker force, forming a superorganismal reproductive unit reminiscent of the differentiated germline and soma in a multicellular organism. Ultimately, the social immune response preserves the germline of the superorganism insect colony and increases overall fitness of the colony in case of disease. }, author = {Cremer, Sylvia and Kutzer, Megan}, booktitle = {Encyclopedia of Animal Behavior}, editor = {Choe, Jae}, isbn = {9780128132517}, pages = {747--755}, publisher = {Elsevier}, title = {{Social immunity}}, doi = {10.1016/B978-0-12-809633-8.90721-0}, year = {2019}, } @inproceedings{9261, abstract = {Bending-active structures are able to efficiently produce complex curved shapes starting from flat panels. The desired deformation of the panels derives from the proper selection of their elastic properties. Optimized panels, called FlexMaps, are designed such that, once they are bent and assembled, the resulting static equilibrium configuration matches a desired input 3D shape. The FlexMaps elastic properties are controlled by locally varying spiraling geometric mesostructures, which are optimized in size and shape to match the global curvature (i.e., bending requests) of the target shape. The design pipeline starts from a quad mesh representing the input 3D shape, which defines the edge size and the total amount of spirals: every quad will embed one spiral. Then, an optimization algorithm tunes the geometry of the spirals by using a simplified pre-computed rod model. This rod model is derived from a non-linear regression algorithm which approximates the non-linear behavior of solid FEM spiral models subject to hundreds of load combinations. This innovative pipeline has been applied to the project of a lightweight plywood pavilion named FlexMaps Pavilion, which is a single-layer piecewise twisted arc that fits a bounding box of 3.90x3.96x3.25 meters.}, author = {Laccone, Francesco and Malomo, Luigi and Perez Rodriguez, Jesus and Pietroni, Nico and Ponchio, Federico and Bickel, Bernd and Cignoni, Paolo}, booktitle = {IASS Symposium 2019 - 60th Anniversary Symposium of the International Association for Shell and Spatial Structures; Structural Membranes 2019 - 9th International Conference on Textile Composites and Inflatable Structures, FORM and FORCE}, isbn = {9788412110104}, issn = {2518-6582}, location = {Barcelona, Spain}, pages = {509--515}, publisher = {International Center for Numerical Methods in Engineering}, title = {{FlexMaps Pavilion: A twisted arc made of mesostructured flat flexible panels}}, year = {2019}, } @inproceedings{7640, abstract = {We propose a new model for detecting visual relationships, such as "person riding motorcycle" or "bottle on table". This task is an important step towards comprehensive structured mage understanding, going beyond detecting individual objects. Our main novelty is a Box Attention mechanism that allows to model pairwise interactions between objects using standard object detection pipelines. The resulting model is conceptually clean, expressive and relies on well-justified training and prediction procedures. Moreover, unlike previously proposed approaches, our model does not introduce any additional complex components or hyperparameters on top of those already required by the underlying detection model. We conduct an experimental evaluation on two datasets, V-COCO and Open Images, demonstrating strong quantitative and qualitative results.}, author = {Kolesnikov, Alexander and Kuznetsova, Alina and Lampert, Christoph and Ferrari, Vittorio}, booktitle = {Proceedings of the 2019 International Conference on Computer Vision Workshop}, isbn = {9781728150239}, location = {Seoul, South Korea}, publisher = {IEEE}, title = {{Detecting visual relationships using box attention}}, doi = {10.1109/ICCVW.2019.00217}, year = {2019}, } @inproceedings{7639, abstract = {Deep neural networks (DNNs) have become increasingly important due to their excellent empirical performance on a wide range of problems. However, regularization is generally achieved by indirect means, largely due to the complex set of functions defined by a network and the difficulty in measuring function complexity. There exists no method in the literature for additive regularization based on a norm of the function, as is classically considered in statistical learning theory. In this work, we study the tractability of function norms for deep neural networks with ReLU activations. We provide, to the best of our knowledge, the first proof in the literature of the NP-hardness of computing function norms of DNNs of 3 or more layers. We also highlight a fundamental difference between shallow and deep networks. In the light on these results, we propose a new regularization strategy based on approximate function norms, and show its efficiency on a segmentation task with a DNN.}, author = {Rannen-Triki, Amal and Berman, Maxim and Kolmogorov, Vladimir and Blaschko, Matthew B.}, booktitle = {Proceedings of the 2019 International Conference on Computer Vision Workshop}, isbn = {9781728150239}, location = {Seoul, South Korea}, publisher = {IEEE}, title = {{Function norms for neural networks}}, doi = {10.1109/ICCVW.2019.00097}, year = {2019}, } @inbook{8281, abstract = {We review the history of population genetics, starting with its origins a century ago from the synthesis between Mendel and Darwin's ideas, through to the recent development of sophisticated schemes of inference from sequence data, based on the coalescent. We explain the close relation between the coalescent and a diffusion process, which we illustrate by their application to understand spatial structure. We summarise the powerful methods available for analysis of multiple loci, when linkage equilibrium can be assumed, and then discuss approaches to the more challenging case, where associations between alleles require that we follow genotype, rather than allele, frequencies. Though we can hardly cover the whole of population genetics, we give an overview of the current state of the subject, and future challenges to it.}, author = {Barton, Nicholas H and Etheridge, Alison}, booktitle = {Handbook of statistical genomics}, editor = {Balding, David and Moltke, Ida and Marioni, John}, isbn = {9781119429142}, pages = {115--144}, publisher = {Wiley}, title = {{Mathematical models in population genetics}}, doi = {10.1002/9781119487845.ch4}, year = {2019}, } @unpublished{8184, abstract = {Denote by ∆N the N-dimensional simplex. A map f : ∆N → Rd is an almost r-embedding if fσ1∩. . .∩fσr = ∅ whenever σ1, . . . , σr are pairwise disjoint faces. A counterexample to the topological Tverberg conjecture asserts that if r is not a prime power and d ≥ 2r + 1, then there is an almost r-embedding ∆(d+1)(r−1) → Rd. This was improved by Blagojevi´c–Frick–Ziegler using a simple construction of higher-dimensional counterexamples by taking k-fold join power of lower-dimensional ones. We improve this further (for d large compared to r): If r is not a prime power and N := (d+ 1)r−r l d + 2 r + 1 m−2, then there is an almost r-embedding ∆N → Rd. For the r-fold van Kampen–Flores conjecture we also produce counterexamples which are stronger than previously known. Our proof is based on generalizations of the Mabillard–Wagner theorem on construction of almost r-embeddings from equivariant maps, and of the Ozaydin theorem on existence of equivariant maps. }, author = {Avvakumov, Sergey and Karasev, R. and Skopenkov, A.}, booktitle = {arXiv}, publisher = {arXiv}, title = {{Stronger counterexamples to the topological Tverberg conjecture}}, year = {2019}, } @inproceedings{6430, abstract = {A proxy re-encryption (PRE) scheme is a public-key encryption scheme that allows the holder of a key pk to derive a re-encryption key for any other key 𝑝𝑘′. This re-encryption key lets anyone transform ciphertexts under pk into ciphertexts under 𝑝𝑘′ without having to know the underlying message, while transformations from 𝑝𝑘′ to pk should not be possible (unidirectional). Security is defined in a multi-user setting against an adversary that gets the users’ public keys and can ask for re-encryption keys and can corrupt users by requesting their secret keys. Any ciphertext that the adversary cannot trivially decrypt given the obtained secret and re-encryption keys should be secure. All existing security proofs for PRE only show selective security, where the adversary must first declare the users it wants to corrupt. This can be lifted to more meaningful adaptive security by guessing the set of corrupted users among the n users, which loses a factor exponential in Open image in new window , rendering the result meaningless already for moderate Open image in new window . Jafargholi et al. (CRYPTO’17) proposed a framework that in some cases allows to give adaptive security proofs for schemes which were previously only known to be selectively secure, while avoiding the exponential loss that results from guessing the adaptive choices made by an adversary. We apply their framework to PREs that satisfy some natural additional properties. Concretely, we give a more fine-grained reduction for several unidirectional PREs, proving adaptive security at a much smaller loss. The loss depends on the graph of users whose edges represent the re-encryption keys queried by the adversary. For trees and chains the loss is quasi-polynomial in the size and for general graphs it is exponential in their depth and indegree (instead of their size as for previous reductions). Fortunately, trees and low-depth graphs cover many, if not most, interesting applications. Our results apply e.g. to the bilinear-map based PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme (STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14).}, author = {Fuchsbauer, Georg and Kamath Hosdurg, Chethan and Klein, Karen and Pietrzak, Krzysztof Z}, isbn = {9783030172589}, issn = {16113349}, location = {Beijing, China}, pages = {317--346}, publisher = {Springer Nature}, title = {{Adaptively secure proxy re-encryption}}, doi = {10.1007/978-3-030-17259-6_11}, volume = {11443}, year = {2019}, } @article{6069, abstract = {Electron transport in two-dimensional conducting materials such as graphene, with dominant electron–electron interaction, exhibits unusual vortex flow that leads to a nonlocal current-field relation (negative resistance), distinct from the classical Ohm’s law. The transport behavior of these materials is best described by low Reynolds number hydrodynamics, where the constitutive pressure–speed relation is Stoke’s law. Here we report evidence of such vortices observed in a viscous flow of Newtonian fluid in a microfluidic device consisting of a rectangular cavity—analogous to the electronic system. We extend our experimental observations to elliptic cavities of different eccentricities, and validate them by numerically solving bi-harmonic equation obtained for the viscous flow with no-slip boundary conditions. We verify the existence of a predicted threshold at which vortices appear. Strikingly, we find that a two-dimensional theoretical model captures the essential features of three-dimensional Stokes flow in experiments.}, author = {Mayzel, Jonathan and Steinberg, Victor and Varshney, Atul}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Stokes flow analogous to viscous electron current in graphene}}, doi = {10.1038/s41467-019-08916-5}, volume = {10}, year = {2019}, } @article{6014, abstract = {Speed of sound waves in gases and liquids are governed by the compressibility of the medium. There exists another type of non-dispersive wave where the wave speed depends on stress instead of elasticity of the medium. A well-known example is the Alfven wave, which propagates through plasma permeated by a magnetic field with the speed determined by magnetic tension. An elastic analogue of Alfven waves has been predicted in a flow of dilute polymer solution where the elastic stress of the stretching polymers determines the elastic wave speed. Here we present quantitative evidence of elastic Alfven waves in elastic turbulence of a viscoelastic creeping flow between two obstacles in channel flow. The key finding in the experimental proof is a nonlinear dependence of the elastic wave speed cel on the Weissenberg number Wi, which deviates from predictions based on a model of linear polymer elasticity.}, author = {Varshney, Atul and Steinberg, Victor}, issn = {2041-1723}, journal = {Nature Communications}, publisher = {Springer Nature}, title = {{Elastic alfven waves in elastic turbulence}}, doi = {10.1038/s41467-019-08551-0}, volume = {10}, year = {2019}, } @article{6451, abstract = {Epidermal growth factor receptor (EGFR) signaling controls skin development and homeostasis inmice and humans, and its deficiency causes severe skin inflammation, which might affect epidermalstem cell behavior. Here, we describe the inflammation-independent effects of EGFR deficiency dur-ing skin morphogenesis and in adult hair follicle stem cells. Expression and alternative splicing analysisof RNA sequencing data from interfollicular epidermis and outer root sheath indicate that EGFR con-trols genes involved in epidermal differentiation and also in centrosome function, DNA damage, cellcycle, and apoptosis. Genetic experiments employingp53deletion in EGFR-deficient epidermis revealthat EGFR signaling exhibitsp53-dependent functions in proliferative epidermal compartments, aswell asp53-independent functions in differentiated hair shaft keratinocytes. Loss of EGFR leads toabsence of LEF1 protein specifically in the innermost epithelial hair layers, resulting in disorganizationof medulla cells. Thus, our results uncover important spatial and temporal features of cell-autonomousEGFR functions in the epidermis.}, author = {Amberg, Nicole and Sotiropoulou, Panagiota A. and Heller, Gerwin and Lichtenberger, Beate M. and Holcmann, Martin and Camurdanoglu, Bahar and Baykuscheva-Gentscheva, Temenuschka and Blanpain, Cedric and Sibilia, Maria}, issn = {2589-0042}, journal = {iScience}, pages = {243--256}, publisher = {Elsevier}, title = {{EGFR controls hair shaft differentiation in a p53-independent manner}}, doi = {10.1016/j.isci.2019.04.018}, volume = {15}, year = {2019}, } @article{10879, abstract = {We study effects of a bounded and compactly supported perturbation on multidimensional continuum random Schrödinger operators in the region of complete localisation. Our main emphasis is on Anderson orthogonality for random Schrödinger operators. Among others, we prove that Anderson orthogonality does occur for Fermi energies in the region of complete localisation with a non-zero probability. This partially confirms recent non-rigorous findings [V. Khemani et al., Nature Phys. 11 (2015), 560–565]. The spectral shift function plays an important role in our analysis of Anderson orthogonality. We identify it with the index of the corresponding pair of spectral projections and explore the consequences thereof. All our results rely on the main technical estimate of this paper which guarantees separate exponential decay of the disorder-averaged Schatten p-norm of χa(f(H)−f(Hτ))χb in a and b. Here, Hτ is a perturbation of the random Schrödinger operator H, χa is the multiplication operator corresponding to the indicator function of a unit cube centred about a∈Rd, and f is in a suitable class of functions of bounded variation with distributional derivative supported in the region of complete localisation for H.}, author = {Dietlein, Adrian M and Gebert, Martin and Müller, Peter}, issn = {1664-039X}, journal = {Journal of Spectral Theory}, keywords = {Random Schrödinger operators, spectral shift function, Anderson orthogonality}, number = {3}, pages = {921--965}, publisher = {European Mathematical Society Publishing House}, title = {{Perturbations of continuum random Schrödinger operators with applications to Anderson orthogonality and the spectral shift function}}, doi = {10.4171/jst/267}, volume = {9}, year = {2019}, } @article{10878, abstract = {Starting from a microscopic model for a system of neurons evolving in time which individually follow a stochastic integrate-and-fire type model, we study a mean-field limit of the system. Our model is described by a system of SDEs with discontinuous coefficients for the action potential of each neuron and takes into account the (random) spatial configuration of neurons allowing the interaction to depend on it. In the limit as the number of particles tends to infinity, we obtain a nonlinear Fokker-Planck type PDE in two variables, with derivatives only with respect to one variable and discontinuous coefficients. We also study strong well-posedness of the system of SDEs and prove the existence and uniqueness of a weak measure-valued solution to the PDE, obtained as the limit of the laws of the empirical measures for the system of particles.}, author = {Flandoli, Franco and Priola, Enrico and Zanco, Giovanni A}, issn = {1553-5231}, journal = {Discrete and Continuous Dynamical Systems}, keywords = {Applied Mathematics, Discrete Mathematics and Combinatorics, Analysis}, number = {6}, pages = {3037--3067}, publisher = {American Institute of Mathematical Sciences}, title = {{A mean-field model with discontinuous coefficients for neurons with spatial interaction}}, doi = {10.3934/dcds.2019126}, volume = {39}, year = {2019}, } @inproceedings{6935, abstract = {This paper investigates the power of preprocessing in the CONGEST model. Schmid and Suomela (ACM HotSDN 2013) introduced the SUPPORTED CONGEST model to study the application of distributed algorithms in Software-Defined Networks (SDNs). In this paper, we show that a large class of lower bounds in the CONGEST model still hold in the SUPPORTED model, highlighting the robustness of these bounds. This also raises the question how much does preprocessing help in the CONGEST model.}, author = {Foerster, Klaus-Tycho and Korhonen, Janne and Rybicki, Joel and Schmid, Stefan}, booktitle = {Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing}, isbn = {9781450362177}, location = {Toronto, ON, Canada}, pages = {259--261}, publisher = {ACM}, title = {{Does preprocessing help under congestion?}}, doi = {10.1145/3293611.3331581}, year = {2019}, } @article{138, abstract = {Autoregulation is the direct modulation of gene expression by the product of the corresponding gene. Autoregulation of bacterial gene expression has been mostly studied at the transcriptional level, when a protein acts as the cognate transcriptional repressor. A recent study investigating dynamics of the bacterial toxin–antitoxin MazEF system has shown how autoregulation at both the transcriptional and post-transcriptional levels affects the heterogeneity of Escherichia coli populations. Toxin–antitoxin systems hold a crucial but still elusive part in bacterial response to stress. This perspective highlights how these modules can also serve as a great model system for investigating basic concepts in gene regulation. However, as the genomic background and environmental conditions substantially influence toxin activation, it is important to study (auto)regulation of toxin–antitoxin systems in well-defined setups as well as in conditions that resemble the environmental niche.}, author = {Nikolic, Nela}, journal = {Current Genetics}, number = {1}, pages = {133--138}, publisher = {Springer}, title = {{Autoregulation of bacterial gene expression: lessons from the MazEF toxin–antitoxin system}}, doi = {10.1007/s00294-018-0879-8}, volume = {65}, year = {2019}, } @article{151, abstract = {We construct planar bi-Sobolev mappings whose local volume distortion is bounded from below by a given function f∈Lp with p>1. More precisely, for any 1<q<(p+1)/2 we construct W1,q-bi-Sobolev maps with identity boundary conditions; for f∈L∞, we provide bi-Lipschitz maps. The basic building block of our construction are bi-Lipschitz maps which stretch a given compact subset of the unit square by a given factor while preserving the boundary. The construction of these stretching maps relies on a slight strengthening of the celebrated covering result of Alberti, Csörnyei, and Preiss for measurable planar sets in the case of compact sets. We apply our result to a model functional in nonlinear elasticity, the integrand of which features fast blowup as the Jacobian determinant of the deformation becomes small. For such functionals, the derivation of the equilibrium equations for minimizers requires an additional regularization of test functions, which our maps provide.}, author = {Fischer, Julian L and Kneuss, Olivier}, journal = {Journal of Differential Equations}, number = {1}, pages = {257 -- 311}, publisher = {Elsevier}, title = {{Bi-Sobolev solutions to the prescribed Jacobian inequality in the plane with L p data and applications to nonlinear elasticity}}, doi = {10.1016/j.jde.2018.07.045}, volume = {266}, year = {2019}, } @article{27, abstract = {The cerebral cortex is composed of a large variety of distinct cell-types including projection neurons, interneurons and glial cells which emerge from distinct neural stem cell (NSC) lineages. The vast majority of cortical projection neurons and certain classes of glial cells are generated by radial glial progenitor cells (RGPs) in a highly orchestrated manner. Recent studies employing single cell analysis and clonal lineage tracing suggest that NSC and RGP lineage progression are regulated in a profound deterministic manner. In this review we focus on recent advances based mainly on correlative phenotypic data emerging from functional genetic studies in mice. We establish hypotheses to test in future research and outline a conceptual framework how epigenetic cues modulate the generation of cell-type diversity during cortical development. This article is protected by copyright. All rights reserved.}, author = {Amberg, Nicole and Laukoter, Susanne and Hippenmeyer, Simon}, journal = {Journal of Neurochemistry}, number = {1}, pages = {12--26}, publisher = {Wiley}, title = {{Epigenetic cues modulating the generation of cell type diversity in the cerebral cortex}}, doi = {10.1111/jnc.14601}, volume = {149}, year = {2019}, } @article{5789, abstract = {Tissue morphogenesis is driven by mechanical forces that elicit changes in cell size, shape and motion. The extent by which forces deform tissues critically depends on the rheological properties of the recipient tissue. Yet, whether and how dynamic changes in tissue rheology affect tissue morphogenesis and how they are regulated within the developing organism remain unclear. Here, we show that blastoderm spreading at the onset of zebrafish morphogenesis relies on a rapid, pronounced and spatially patterned tissue fluidization. Blastoderm fluidization is temporally controlled by mitotic cell rounding-dependent cell–cell contact disassembly during the last rounds of cell cleavages. Moreover, fluidization is spatially restricted to the central blastoderm by local activation of non-canonical Wnt signalling within the blastoderm margin, increasing cell cohesion and thereby counteracting the effect of mitotic rounding on contact disassembly. Overall, our results identify a fluidity transition mediated by loss of cell cohesion as a critical regulator of embryo morphogenesis.}, author = {Petridou, Nicoletta and Grigolon, Silvia and Salbreux, Guillaume and Hannezo, Edouard B and Heisenberg, Carl-Philipp J}, issn = {14657392}, journal = {Nature Cell Biology}, pages = {169–178}, publisher = {Nature Publishing Group}, title = {{Fluidization-mediated tissue spreading by mitotic cell rounding and non-canonical Wnt signalling}}, doi = {10.1038/s41556-018-0247-4}, volume = {21}, year = {2019}, } @article{196, abstract = {The abelian sandpile serves as a model to study self-organized criticality, a phenomenon occurring in biological, physical and social processes. The identity of the abelian group is a fractal composed of self-similar patches, and its limit is subject of extensive collaborative research. Here, we analyze the evolution of the sandpile identity under harmonic fields of different orders. We show that this evolution corresponds to periodic cycles through the abelian group characterized by the smooth transformation and apparent conservation of the patches constituting the identity. The dynamics induced by second and third order harmonics resemble smooth stretchings, respectively translations, of the identity, while the ones induced by fourth order harmonics resemble magnifications and rotations. Starting with order three, the dynamics pass through extended regions of seemingly random configurations which spontaneously reassemble into accentuated patterns. We show that the space of harmonic functions projects to the extended analogue of the sandpile group, thus providing a set of universal coordinates identifying configurations between different domains. Since the original sandpile group is a subgroup of the extended one, this directly implies that it admits a natural renormalization. Furthermore, we show that the harmonic fields can be induced by simple Markov processes, and that the corresponding stochastic dynamics show remarkable robustness over hundreds of periods. Finally, we encode information into seemingly random configurations, and decode this information with an algorithm requiring minimal prior knowledge. Our results suggest that harmonic fields might split the sandpile group into sub-sets showing different critical coefficients, and that it might be possible to extend the fractal structure of the identity beyond the boundaries of its domain. }, author = {Lang, Moritz and Shkolnikov, Mikhail}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, number = {8}, pages = {2821--2830}, publisher = {National Academy of Sciences}, title = {{Harmonic dynamics of the Abelian sandpile}}, doi = {10.1073/pnas.1812015116}, volume = {116}, year = {2019}, } @article{5817, abstract = {We theoretically study the shapes of lipid vesicles confined to a spherical cavity, elaborating a framework based on the so-called limiting shapes constructed from geometrically simple structural elements such as double-membrane walls and edges. Partly inspired by numerical results, the proposed non-compartmentalized and compartmentalized limiting shapes are arranged in the bilayer-couple phase diagram which is then compared to its free-vesicle counterpart. We also compute the area-difference-elasticity phase diagram of the limiting shapes and we use it to interpret shape transitions experimentally observed in vesicles confined within another vesicle. The limiting-shape framework may be generalized to theoretically investigate the structure of certain cell organelles such as the mitochondrion.}, author = {Kavcic, Bor and Sakashita, A. and Noguchi, H. and Ziherl, P.}, issn = {1744-6848}, journal = {Soft Matter}, number = {4}, pages = {602--614}, publisher = {Royal Society of Chemistry}, title = {{Limiting shapes of confined lipid vesicles}}, doi = {10.1039/c8sm01956h}, volume = {15}, year = {2019}, } @article{73, abstract = {We consider the space of probability measures on a discrete set X, endowed with a dynamical optimal transport metric. Given two probability measures supported in a subset Y⊆X, it is natural to ask whether they can be connected by a constant speed geodesic with support in Y at all times. Our main result answers this question affirmatively, under a suitable geometric condition on Y introduced in this paper. The proof relies on an extension result for subsolutions to discrete Hamilton-Jacobi equations, which is of independent interest.}, author = {Erbar, Matthias and Maas, Jan and Wirth, Melchior}, issn = {09442669}, journal = {Calculus of Variations and Partial Differential Equations}, number = {1}, publisher = {Springer}, title = {{On the geometry of geodesics in discrete optimal transport}}, doi = {10.1007/s00526-018-1456-1}, volume = {58}, year = {2019}, } @article{6982, abstract = {We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ϕ : G → M of a graph G into a 2-manifold M maps the vertices in V(G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to the same point or overlapping arcs due to data compression or low resolution. This raises the computational problem of deciding whether a given map ϕ : G → M comes from an embedding. A map ϕ : G → M is a weak embedding if it can be perturbed into an embedding ψ ϵ : G → M with ‖ ϕ − ψ ϵ ‖ < ϵ for every ϵ > 0, where ‖.‖ is the unform norm. A polynomial-time algorithm for recognizing weak embeddings has recently been found by Fulek and Kynčl. It reduces the problem to solving a system of linear equations over Z2. It runs in O(n2ω)≤ O(n4.75) time, where ω ∈ [2,2.373) is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler: We perform a sequence of local operations that gradually “untangles” the image ϕ(G) into an embedding ψ(G) or reports that ϕ is not a weak embedding. It combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations. }, author = {Akitaya, Hugo and Fulek, Radoslav and Tóth, Csaba}, journal = {ACM Transactions on Algorithms}, number = {4}, publisher = {ACM}, title = {{Recognizing weak embeddings of graphs}}, doi = {10.1145/3344549}, volume = {15}, year = {2019}, } @phdthesis{6894, abstract = {Hybrid automata combine finite automata and dynamical systems, and model the interaction of digital with physical systems. Formal analysis that can guarantee the safety of all behaviors or rigorously witness failures, while unsolvable in general, has been tackled algorithmically using, e.g., abstraction, bounded model-checking, assisted theorem proving. Nevertheless, very few methods have addressed the time-unbounded reachability analysis of hybrid automata and, for current sound and automatic tools, scalability remains critical. We develop methods for the polyhedral abstraction of hybrid automata, which construct coarse overapproximations and tightens them incrementally, in a CEGAR fashion. We use template polyhedra, i.e., polyhedra whose facets are normal to a given set of directions. While, previously, directions were given by the user, we introduce (1) the first method for computing template directions from spurious counterexamples, so as to generalize and eliminate them. The method applies naturally to convex hybrid automata, i.e., hybrid automata with (possibly non-linear) convex constraints on derivatives only, while for linear ODE requires further abstraction. Specifically, we introduce (2) the conic abstractions, which, partitioning the state space into appropriate (possibly non-uniform) cones, divide curvy trajectories into relatively straight sections, suitable for polyhedral abstractions. Finally, we introduce (3) space-time interpolation, which, combining interval arithmetic and template refinement, computes appropriate (possibly non-uniform) time partitioning and template directions along spurious trajectories, so as to eliminate them. We obtain sound and automatic methods for the reachability analysis over dense and unbounded time of convex hybrid automata and hybrid automata with linear ODE. We build prototype tools and compare—favorably—our methods against the respective state-of-the-art tools, on several benchmarks.}, author = {Giacobbe, Mirco}, issn = {2663-337X}, pages = {132}, publisher = {Institute of Science and Technology Austria}, title = {{Automatic time-unbounded reachability analysis of hybrid systems}}, doi = {10.15479/AT:ISTA:6894}, year = {2019}, } @misc{9805, abstract = {The spread of adaptive alleles is fundamental to evolution, and in theory, this process is well‐understood. However, only rarely can we follow this process—whether it originates from the spread of a new mutation, or by introgression from another population. In this issue of Molecular Ecology, Hanemaaijer et al. (2018) report on a 25‐year long study of the mosquitoes Anopheles gambiae (Figure 1) and Anopheles coluzzi in Mali, based on genotypes at 15 single‐nucleotide polymorphism (SNP). The species are usually reproductively isolated from each other, but in 2002 and 2006, bursts of hybridization were observed, when F1 hybrids became abundant. Alleles backcrossed from A. gambiae into A. coluzzi, but after the first event, these declined over the following years. In contrast, after 2006, an insecticide resistance allele that had established in A. gambiae spread into A. coluzzi, and rose to high frequency there, over 6 years (~75 generations). Whole genome sequences of 74 individuals showed that A. gambiae SNP from across the genome had become common in the A. coluzzi population, but that most of these were clustered in 34 genes around the resistance locus. A new set of SNP from 25 of these genes were assayed over time; over the 4 years since near‐fixation of the resistance allele; some remained common, whereas others declined. What do these patterns tell us about this introgression event?}, author = {Barton, Nicholas H}, publisher = {Dryad}, title = {{Data from: The consequences of an introgression event}}, doi = {10.5061/dryad.2kb6fh4}, year = {2019}, } @article{8, abstract = {Despite their different origins, Drosophila glia and hemocytes are related cell populations that provide an immune function. Drosophila hemocytes patrol the body cavity and act as macrophages outside the nervous system whereas glia originate from the neuroepithelium and provide the scavenger population of the nervous system. Drosophila glia are hence the functional orthologs of vertebrate microglia, even though the latter are cells of immune origin that subsequently move into the brain during development. Interestingly, the Drosophila immune cells within (glia) and outside the nervous system (hemocytes) require the same transcription factor Glide/Gcm for their development. This raises the issue of how do glia specifically differentiate in the nervous system and hemocytes in the procephalic mesoderm. The Repo homeodomain transcription factor and pan-glial direct target of Glide/Gcm is known to ensure glial terminal differentiation. Here we show that Repo also takes center stage in the process that discriminates between glia and hemocytes. First, Repo expression is repressed in the hemocyte anlagen by mesoderm-specific factors. Second, Repo ectopic activation in the procephalic mesoderm is sufficient to repress the expression of hemocyte-specific genes. Third, the lack of Repo triggers the expression of hemocyte markers in glia. Thus, a complex network of tissue-specific cues biases the potential of Glide/Gcm. These data allow us to revise the concept of fate determinants and help us understand the bases of cell specification. Both sexes were analyzed.SIGNIFICANCE STATEMENTDistinct cell types often require the same pioneer transcription factor, raising the issue of how does one factor trigger different fates. In Drosophila, glia and hemocytes provide a scavenger activity within and outside the nervous system, respectively. While they both require the Glide/Gcm transcription factor, glia originate from the ectoderm, hemocytes from the mesoderm. Here we show that tissue-specific factors inhibit the gliogenic potential of Glide/Gcm in the mesoderm by repressing the expression of the homeodomain protein Repo, a major glial-specific target of Glide/Gcm. Repo expression in turn inhibits the expression of hemocyte-specific genes in the nervous system. These cell-specific networks secure the establishment of the glial fate only in the nervous system and allow cell diversification.}, author = {Trébuchet, Guillaume and Cattenoz, Pierre B and Zsámboki, János and Mazaud, David and Siekhaus, Daria E and Fanto, Manolis and Giangrande, Angela}, journal = {Journal of Neuroscience}, number = {2}, pages = {238--255}, publisher = {Society for Neuroscience}, title = {{The Repo homeodomain transcription factor suppresses hematopoiesis in Drosophila and preserves the glial fate}}, doi = {10.1523/JNEUROSCI.1059-18.2018}, volume = {39}, year = {2019}, }