TY - JOUR AB - X and Y chromosomes can diverge when rearrangements block recombination between them. Here we present the first genomic view of a reciprocal translocation that causes two physically unconnected pairs of chromosomes to be coinherited as sex chromosomes. In a population of the common frog (Rana temporaria), both pairs of X and Y chromosomes show extensive sequence differentiation, but not degeneration of the Y chromosomes. A new method based on gene trees shows both chromosomes are sex‐linked. Furthermore, the gene trees from the two Y chromosomes have identical topologies, showing they have been coinherited since the reciprocal translocation occurred. Reciprocal translocations can thus reshape sex linkage on a much greater scale compared with inversions, the type of rearrangement that is much better known in sex chromosome evolution, and they can greatly amplify the power of sexually antagonistic selection to drive genomic rearrangement. Two more populations show evidence of other rearrangements, suggesting that this species has unprecedented structural polymorphism in its sex chromosomes. AU - Toups, Melissa A AU - Rodrigues, Nicolas AU - Perrin, Nicolas AU - Kirkpatrick, Mark ID - 7421 IS - 8 JF - Molecular Ecology SN - 0962-1083 TI - A reciprocal translocation radically reshapes sex‐linked inheritance in the common frog VL - 28 ER - TY - CONF AB - Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving a statement χ and a time parameter T computes a proof ϕ(χ,T) which is efficiently and publicly verifiable. The proof can be computed in T sequential steps, but not much less, even by a malicious party having large parallelism. A PoSW thus serves as a proof that T units of time have passed since χ was received. PoSW were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical construction was only recently proposed by Cohen and Pietrzak [CP18]. In this work we construct a new simple PoSW in the random permutation model which is almost as simple and efficient as [CP18] but conceptually very different. Whereas the structure underlying [CP18] is a hash tree, our construction is based on skip lists and has the interesting property that computing the PoSW is a reversible computation. The fact that the construction is reversible can potentially be used for new applications like constructing proofs of replication. We also show how to “embed” the sloth function of Lenstra and Weselowski [LW17] into our PoSW to get a PoSW where one additionally can verify correctness of the output much more efficiently than recomputing it (though recent constructions of “verifiable delay functions” subsume most of the applications this construction was aiming at). AU - Abusalah, Hamza M AU - Kamath Hosdurg, Chethan AU - Klein, Karen AU - Pietrzak, Krzysztof Z AU - Walter, Michael ID - 7411 SN - 0302-9743 T2 - Advances in Cryptology – EUROCRYPT 2019 TI - Reversible proofs of sequential work VL - 11477 ER - TY - JOUR AB - Background Synaptic vesicles (SVs) are an integral part of the neurotransmission machinery, and isolation of SVs from their host neuron is necessary to reveal their most fundamental biochemical and functional properties in in vitro assays. Isolated SVs from neurons that have been genetically engineered, e.g. to introduce genetically encoded indicators, are not readily available but would permit new insights into SV structure and function. Furthermore, it is unclear if cultured neurons can provide sufficient starting material for SV isolation procedures. New method Here, we demonstrate an efficient ex vivo procedure to obtain functional SVs from cultured rat cortical neurons after genetic engineering with a lentivirus. Results We show that ∼108 plated cortical neurons allow isolation of suitable SV amounts for functional analysis and imaging. We found that SVs isolated from cultured neurons have neurotransmitter uptake comparable to that of SVs isolated from intact cortex. Using total internal reflection fluorescence (TIRF) microscopy, we visualized an exogenous SV-targeted marker protein and demonstrated the high efficiency of SV modification. Comparison with existing methods Obtaining SVs from genetically engineered neurons currently generally requires the availability of transgenic animals, which is constrained by technical (e.g. cost and time) and biological (e.g. developmental defects and lethality) limitations. Conclusions These results demonstrate the modification and isolation of functional SVs using cultured neurons and viral transduction. The ability to readily obtain SVs from genetically engineered neurons will permit linking in situ studies to in vitro experiments in a variety of genetic contexts. AU - Mckenzie, Catherine AU - Spanova, Miroslava AU - Johnson, Alexander J AU - Kainrath, Stephanie AU - Zheden, Vanessa AU - Sitte, Harald H. AU - Janovjak, Harald L ID - 7406 JF - Journal of Neuroscience Methods SN - 0165-0270 TI - Isolation of synaptic vesicles from genetically engineered cultured neurons VL - 312 ER - TY - CONF AB - Most of today's distributed machine learning systems assume reliable networks: whenever two machines exchange information (e.g., gradients or models), the network should guarantee the delivery of the message. At the same time, recent work exhibits the impressive tolerance of machine learning algorithms to errors or noise arising from relaxed communication or synchronization. In this paper, we connect these two trends, and consider the following question: Can we design machine learning systems that are tolerant to network unreliability during training? With this motivation, we focus on a theoretical problem of independent interest-given a standard distributed parameter server architecture, if every communication between the worker and the server has a non-zero probability p of being dropped, does there exist an algorithm that still converges, and at what speed? The technical contribution of this paper is a novel theoretical analysis proving that distributed learning over unreliable network can achieve comparable convergence rate to centralized or distributed learning over reliable networks. Further, we prove that the influence of the packet drop rate diminishes with the growth of the number of parameter servers. We map this theoretical result onto a real-world scenario, training deep neural networks over an unreliable network layer, and conduct network simulation to validate the system improvement by allowing the networks to be unreliable. AU - Yu, Chen AU - Tang, Hanlin AU - Renggli, Cedric AU - Kassing, Simon AU - Singla, Ankit AU - Alistarh, Dan-Adrian AU - Zhang, Ce AU - Liu, Ji ID - 7437 SN - 9781510886988 T2 - 36th International Conference on Machine Learning, ICML 2019 TI - Distributed learning over unreliable networks VL - 2019-June ER - TY - JOUR AB - We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while (we hope) not introducing many new violations. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lovász local lemma (LLL), a nonconstructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement, and one needs to step outside the class. Here we introduce the notion of measure distortion and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary algorithm of such type and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure. AU - Achlioptas, Dimitris AU - Iliopoulos, Fotis AU - Kolmogorov, Vladimir ID - 7412 IS - 5 JF - SIAM Journal on Computing SN - 0097-5397 TI - A local lemma for focused stochastical algorithms VL - 48 ER - TY - JOUR AB - Multiple importance sampling (MIS) has become an indispensable tool in Monte Carlo rendering, widely accepted as a near-optimal solution for combining different sampling techniques. But an MIS combination, using the common balance or power heuristics, often results in an overly defensive estimator, leading to high variance. We show that by generalizing the MIS framework, variance can be substantially reduced. Specifically, we optimize one of the combined sampling techniques so as to decrease the overall variance of the resulting MIS estimator. We apply the approach to the computation of direct illumination due to an HDR environment map and to the computation of global illumination using a path guiding algorithm. The implementation can be as simple as subtracting a constant value from the tabulated sampling density done entirely in a preprocessing step. This produces a consistent noise reduction in all our tests with no negative influence on run time, no artifacts or bias, and no failure cases. AU - Karlík, Ondřej AU - Šik, Martin AU - Vévoda, Petr AU - Skrivan, Tomas AU - Křivánek, Jaroslav ID - 7418 IS - 6 JF - ACM Transactions on Graphics SN - 0730-0301 TI - MIS compensation: Optimizing sampling techniques in multiple importance sampling VL - 38 ER - TY - JOUR AB - We consider Bose gases consisting of N particles trapped in a box with volume one and interacting through a repulsive potential with scattering length of order N−1 (Gross–Pitaevskii regime). We determine the ground state energy and the low-energy excitation spectrum, up to errors vanishing as N→∞. Our results confirm Bogoliubov’s predictions. AU - Boccato, Chiara AU - Brennecke, Christian AU - Cenatiempo, Serena AU - Schlein, Benjamin ID - 7413 IS - 2 JF - Acta Mathematica SN - 0001-5962 TI - Bogoliubov theory in the Gross–Pitaevskii limit VL - 222 ER - TY - JOUR AB - The study of parallel ecological divergence provides important clues to the operation of natural selection. Parallel divergence often occurs in heterogeneous environments with different kinds of environmental gradients in different locations, but the genomic basis underlying this process is unknown. We investigated the genomics of rapid parallel adaptation in the marine snail Littorina saxatilis in response to two independent environmental axes (crab-predation versus wave-action and low-shore versus high-shore). Using pooled whole-genome resequencing, we show that sharing of genomic regions of high differentiation between environments is generally low but increases at smaller spatial scales. We identify different shared genomic regions of divergence for each environmental axis and show that most of these regions overlap with candidate chromosomal inversions. Several inversion regions are divergent and polymorphic across many localities. We argue that chromosomal inversions could store shared variation that fuels rapid parallel adaptation to heterogeneous environments, possibly as balanced polymorphism shared by adaptive gene flow. AU - Morales, Hernán E. AU - Faria, Rui AU - Johannesson, Kerstin AU - Larsson, Tomas AU - Panova, Marina AU - Westram, Anja M AU - Butlin, Roger K. ID - 7393 IS - 12 JF - Science Advances SN - 2375-2548 TI - Genomic architecture of parallel ecological divergence: Beyond a single environmental contrast VL - 5 ER - TY - JOUR AB - Polymer additives can substantially reduce the drag of turbulent flows and the upperlimit, the so called “maximum drag reduction” (MDR) asymptote is universal, i.e. inde-pendent of the type of polymer and solvent used. Until recently, the consensus was that,in this limit, flows are in a marginal state where only a minimal level of turbulence activ-ity persists. Observations in direct numerical simulations using minimal sized channelsappeared to support this view and reported long “hibernation” periods where turbu-lence is marginalized. In simulations of pipe flow we find that, indeed, with increasingWeissenberg number (Wi), turbulence expresses long periods of hibernation if the domainsize is small. However, with increasing pipe length, the temporal hibernation continuouslyalters to spatio-temporal intermittency and here the flow consists of turbulent puffs sur-rounded by laminar flow. Moreover, upon an increase in Wi, the flow fully relaminarises,in agreement with recent experiments. At even larger Wi, a different instability is en-countered causing a drag increase towards MDR. Our findings hence link earlier minimalflow unit simulations with recent experiments and confirm that the addition of polymersinitially suppresses Newtonian turbulence and leads to a reverse transition. The MDRstate on the other hand results from a separate instability and the underlying dynamicscorresponds to the recently proposed state of elasto-inertial-turbulence (EIT). AU - Lopez Alonso, Jose M AU - Choueiri, George H AU - Hof, Björn ID - 7397 JF - Journal of Fluid Mechanics SN - 0022-1120 TI - Dynamics of viscoelastic pipe flow at low Reynolds numbers in the maximum drag reduction limit VL - 874 ER - TY - JOUR AB - The order-k Voronoi tessellation of a locally finite set 𝑋⊆ℝ𝑛 decomposes ℝ𝑛 into convex domains whose points have the same k nearest neighbors in X. Assuming X is a stationary Poisson point process, we give explicit formulas for the expected number and total area of faces of a given dimension per unit volume of space. We also develop a relaxed version of discrete Morse theory and generalize by counting only faces, for which the k nearest points in X are within a given distance threshold. AU - Edelsbrunner, Herbert AU - Nikitenko, Anton ID - 5678 IS - 4 JF - Discrete and Computational Geometry SN - 01795376 TI - Poisson–Delaunay Mosaics of Order k VL - 62 ER - TY - JOUR AB - Hippocampus is needed for both spatial working and reference memories. Here, using a radial eight-arm maze, we examined how the combined demand on these memories influenced CA1 place cell assemblies while reference memories were partially updated. This was contrasted with control tasks requiring only working memory or the update of reference memory. Reference memory update led to the reward-directed place field shifts at newly rewarded arms and to the gradual strengthening of firing in passes between newly rewarded arms but not between those passes that included a familiar-rewarded arm. At the maze center, transient network synchronization periods preferentially replayed trajectories of the next chosen arm in reference memory tasks but the previously visited arm in the working memory task. Hence, reference memory demand was uniquely associated with a gradual, goal novelty-related reorganization of place cell assemblies and with trajectory replay that reflected the animal's decision of which arm to visit next. AU - Xu, Haibing AU - Baracskay, Peter AU - O'Neill, Joseph AU - Csicsvari, Jozsef L ID - 5828 IS - 1 JF - Neuron SN - 10974199 TI - Assembly responses of hippocampal CA1 place cells predict learned behavior in goal-directed spatial tasks on the radial eight-arm maze VL - 101 ER - TY - JOUR AB - We give a bound on the ground-state energy of a system of N non-interacting fermions in a three-dimensional cubic box interacting with an impurity particle via point interactions. We show that the change in energy compared to the system in the absence of the impurity is bounded in terms of the gas density and the scattering length of the interaction, independently of N. Our bound holds as long as the ratio of the mass of the impurity to the one of the gas particles is larger than a critical value m∗ ∗≈ 0.36 , which is the same regime for which we recently showed stability of the system. AU - Moser, Thomas AU - Seiringer, Robert ID - 5856 IS - 4 JF - Annales Henri Poincare SN - 14240637 TI - Energy contribution of a point-interacting impurity in a Fermi gas VL - 20 ER - TY - THES AB - In many shear flows like pipe flow, plane Couette flow, plane Poiseuille flow, etc. turbulence emerges subcritically. Here, when subjected to strong enough perturbations, the flow becomes turbulent in spite of the laminar base flow being linearly stable. The nature of this instability has puzzled the scientific community for decades. At onset, turbulence appears in localized patches and flows are spatio-temporally intermittent. In pipe flow the localized turbulent structures are referred to as puffs and in planar flows like plane Couette and channel flow, patches arise in the form of localized oblique bands. In this thesis, we study the onset of turbulence in channel flow in direct numerical simulations from a dynamical system theory perspective, as well as by performing experiments in a large aspect ratio channel. The aim of the experimental work is to determine the critical Reynolds number where turbulence first becomes sustained. Recently, the onset of turbulence has been described in analogy to absorbing state phase transition (i.e. directed percolation). In particular, it has been shown that the critical point can be estimated from the competition between spreading and decay processes. Here, by performing experiments, we identify the mechanisms underlying turbulence proliferation in channel flow and find the critical Reynolds number, above which turbulence becomes sustained. Above the critical point, the continuous growth at the tip of the stripes outweighs the stochastic shedding of turbulent patches at the tail and the stripes expand. For growing stripes, the probability to decay decreases while the probability of stripe splitting increases. Consequently, and unlike for the puffs in pipe flow, neither of these two processes is time-independent i.e. memoryless. Coupling between stripe expansion and creation of new stripes via splitting leads to a significantly lower critical point ($Re_c=670+/-10$) than most earlier studies suggest. While the above approach sheds light on how turbulence first becomes sustained, it provides no insight into the origin of the stripes themselves. In the numerical part of the thesis we investigate how turbulent stripes form from invariant solutions of the Navier-Stokes equations. The origin of these turbulent stripes can be identified by applying concepts from the dynamical system theory. In doing so, we identify the exact coherent structures underlying stripes and their bifurcations and how they give rise to the turbulent attractor in phase space. We first report a family of localized nonlinear traveling wave solutions of the Navier-Stokes equations in channel flow. These solutions show structural similarities with turbulent stripes in experiments like obliqueness, quasi-streamwise streaks and vortices, etc. A parametric study of these traveling wave solution is performed, with parameters like Reynolds number, stripe tilt angle and domain size, including the stability of the solutions. These solutions emerge through saddle-node bifurcations and form a phase space skeleton for the turbulent stripes observed in the experiments. The lower branches of these TW solutions at different tilt angles undergo Hopf bifurcation and new solutions branches of relative periodic orbits emerge. These RPO solutions do not belong to the same family and therefore the routes to chaos for different angles are different. In shear flows, turbulence at onset is transient in nature. Consequently,turbulence can not be tracked to lower Reynolds numbers, where the dynamics may simplify. Before this happens, turbulence becomes short-lived and laminarizes. In the last part of the thesis, we show that using numerical simulations we can continue turbulent stripes in channel flow past the 'relaminarization barrier' all the way to their origin. Here, turbulent stripe dynamics simplifies and the fluctuations are no longer stochastic and the stripe settles down to a relative periodic orbit. This relative periodic orbit originates from the aforementioned traveling wave solutions. Starting from the relative periodic orbit, a small increase in speed i.e. Reynolds number gives rise to chaos and the attractor dimension sharply increases in contrast to the classical transition scenario where the instabilities affect the flow globally and give rise to much more gradual route to turbulence. AU - Paranjape, Chaitanya S ID - 6957 KW - Instabilities KW - Turbulence KW - Nonlinear dynamics TI - Onset of turbulence in plane Poiseuille flow ER - TY - JOUR AB - We consider large random matrices with a general slowly decaying correlation among its entries. We prove universality of the local eigenvalue statistics and optimal local laws for the resolvent away from the spectral edges, generalizing the recent result of Ajanki et al. [‘Stability of the matrix Dyson equation and random matrices with correlations’, Probab. Theory Related Fields 173(1–2) (2019), 293–373] to allow slow correlation decay and arbitrary expectation. The main novel tool is a systematic diagrammatic control of a multivariate cumulant expansion. AU - Erdös, László AU - Krüger, Torben H AU - Schröder, Dominik J ID - 6182 JF - Forum of Mathematics, Sigma TI - Random matrices with slow correlation decay VL - 7 ER - TY - JOUR AB - We prove that the local eigenvalue statistics of real symmetric Wigner-type matrices near the cusp points of the eigenvalue density are universal. Together with the companion paper [arXiv:1809.03971], which proves the same result for the complex Hermitian symmetry class, this completes the last remaining case of the Wigner-Dyson-Mehta universality conjecture after bulk and edge universalities have been established in the last years. We extend the recent Dyson Brownian motion analysis at the edge [arXiv:1712.03881] to the cusp regime using the optimal local law from [arXiv:1809.03971] and the accurate local shape analysis of the density from [arXiv:1506.05095, arXiv:1804.07752]. We also present a PDE-based method to improve the estimate on eigenvalue rigidity via the maximum principle of the heat flow related to the Dyson Brownian motion. AU - Cipolloni, Giorgio AU - Erdös, László AU - Krüger, Torben H AU - Schröder, Dominik J ID - 6186 IS - 4 JF - Pure and Applied Analysis SN - 2578-5893 TI - Cusp universality for random matrices, II: The real symmetric case VL - 1 ER - TY - JOUR AB - Across diverse biological systems—ranging from neural networks to intracellular signaling and genetic regulatory networks—the information about changes in the environment is frequently encoded in the full temporal dynamics of the network nodes. A pressing data-analysis challenge has thus been to efficiently estimate the amount of information that these dynamics convey from experimental data. Here we develop and evaluate decoding-based estimation methods to lower bound the mutual information about a finite set of inputs, encoded in single-cell high-dimensional time series data. For biological reaction networks governed by the chemical Master equation, we derive model-based information approximations and analytical upper bounds, against which we benchmark our proposed model-free decoding estimators. In contrast to the frequently-used k-nearest-neighbor estimator, decoding-based estimators robustly extract a large fraction of the available information from high-dimensional trajectories with a realistic number of data samples. We apply these estimators to previously published data on Erk and Ca2+ signaling in mammalian cells and to yeast stress-response, and find that substantial amount of information about environmental state can be encoded by non-trivial response statistics even in stationary signals. We argue that these single-cell, decoding-based information estimates, rather than the commonly-used tests for significant differences between selected population response statistics, provide a proper and unbiased measure for the performance of biological signaling networks. AU - Cepeda Humerez, Sarah A AU - Ruess, Jakob AU - Tkačik, Gašper ID - 6900 IS - 9 JF - PLoS computational biology TI - Estimating information in time-varying signals VL - 15 ER - TY - JOUR AB - Clathrin-mediated endocytosis (CME) is a highly conserved and essential cellular process in eukaryotic cells, but its dynamic and vital nature makes it challenging to study using classical genetics tools. In contrast, although small molecules can acutely and reversibly perturb CME, the few chemical CME inhibitors that have been applied to plants are either ineffective or show undesirable side effects. Here, we identify the previously described endosidin9 (ES9) as an inhibitor of clathrin heavy chain (CHC) function in both Arabidopsis and human cells through affinity-based target isolation, in vitro binding studies and X-ray crystallography. Moreover, we present a chemically improved ES9 analog, ES9-17, which lacks the undesirable side effects of ES9 while retaining the ability to target CHC. ES9 and ES9-17 have expanded the chemical toolbox used to probe CHC function, and present chemical scaffolds for further design of more specific and potent CHC inhibitors across different systems. AU - Dejonghe, Wim AU - Sharma, Isha AU - Denoo, Bram AU - De Munck, Steven AU - Lu, Qing AU - Mishev, Kiril AU - Bulut, Haydar AU - Mylle, Evelien AU - De Rycke, Riet AU - Vasileva, Mina K AU - Savatin, Daniel V. AU - Nerinckx, Wim AU - Staes, An AU - Drozdzecki, Andrzej AU - Audenaert, Dominique AU - Yperman, Klaas AU - Madder, Annemieke AU - Friml, Jiří AU - Van Damme, Daniël AU - Gevaert, Kris AU - Haucke, Volker AU - Savvides, Savvas N. AU - Winne, Johan AU - Russinova, Eugenia ID - 6377 IS - 6 JF - Nature Chemical Biology SN - 15524450 TI - Disruption of endocytosis through chemical inhibition of clathrin heavy chain function VL - 15 ER - TY - THES AB - Tissue morphogenesis in developmental or physiological processes is regulated by molecular and mechanical signals. While the molecular signaling cascades are increasingly well described, the mechanical signals affecting tissue shape changes have only recently been studied in greater detail. To gain more insight into the mechanochemical and biophysical basis of an epithelial spreading process (epiboly) in early zebrafish development, we studied cell-cell junction formation and actomyosin network dynamics at the boundary between surface layer epithelial cells (EVL) and the yolk syncytial layer (YSL). During zebrafish epiboly, the cell mass sitting on top of the yolk cell spreads to engulf the yolk cell by the end of gastrulation. It has been previously shown that an actomyosin ring residing within the YSL pulls on the EVL tissue through a cable-constriction and a flow-friction motor, thereby dragging the tissue vegetal wards. Pulling forces are likely transmitted from the YSL actomyosin ring to EVL cells; however, the nature and formation of the junctional structure mediating this process has not been well described so far. Therefore, our main aim was to determine the nature, dynamics and potential function of the EVL-YSL junction during this epithelial tissue spreading. Specifically, we show that the EVL-YSL junction is a mechanosensitive structure, predominantly made of tight junction (TJ) proteins. The process of TJ mechanosensation depends on the retrograde flow of non-junctional, phase-separated Zonula Occludens-1 (ZO-1) protein clusters towards the EVL-YSL boundary. Interestingly, we could demonstrate that ZO-1 is present in a non-junctional pool on the surface of the yolk cell, and ZO-1 undergoes a phase separation process that likely renders the protein responsive to flows. These flows are directed towards the junction and mediate proper tension-dependent recruitment of ZO-1. Upon reaching the EVL-YSL junction ZO-1 gets incorporated into the junctional pool mediated through its direct actin-binding domain. When the non-junctional pool and/or ZO-1 direct actin binding is absent, TJs fail in their proper mechanosensitive responses resulting in slower tissue spreading. We could further demonstrate that depletion of ZO proteins within the YSL results in diminished actomyosin ring formation. This suggests that a mechanochemical feedback loop is at work during zebrafish epiboly: ZO proteins help in proper actomyosin ring formation and actomyosin contractility and flows positively influence ZO-1 junctional recruitment. Finally, such a mesoscale polarization process mediated through the flow of phase-separated protein clusters might have implications for other processes such as immunological synapse formation, C. elegans zygote polarization and wound healing. AU - Schwayer, Cornelia ID - 7186 SN - 2663-337X TI - Mechanosensation of tight junctions depends on ZO-1 phase separation and flow ER - TY - THES AB - The first part of the thesis considers the computational aspects of the homotopy groups πd(X) of a topological space X. It is well known that there is no algorithm to decide whether the fundamental group π1(X) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π1(X) trivial), compute the higher homotopy group πd(X) for any given d ≥ 2. However, these algorithms come with a caveat: They compute the isomorphism type of πd(X), d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πd(X). We present an algorithm that, given a simply connected space X, computes πd(X) and represents its elements as simplicial maps from suitable triangulations of the d-sphere Sd to X. For fixed d, the algorithm runs in time exponential in size(X), the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2, we construct a family of simply connected spaces X such that for any simplicial map representing a generator of πd(X), the size of the triangulation of S d on which the map is defined, is exponential in size(X). In the second part of the thesis, we prove that the following question is algorithmically undecidable for d < ⌊3(k+1)/2⌋, k ≥ 5 and (k, d) ̸= (5, 7), which covers essentially everything outside the meta-stable range: Given a finite simplicial complex K of dimension k, decide whether there exists a piecewise-linear (i.e., linear on an arbitrarily fine subdivision of K) embedding f : K ↪→ Rd of K into a d-dimensional Euclidean space. AU - Zhechev, Stephan Y ID - 6681 SN - 2663-337X TI - Algorithmic aspects of homotopy theory and embeddability ER - TY - GEN AB - 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. AU - Avvakumov, Sergey AU - Kudrya, Sergey ID - 8182 T2 - arXiv TI - Vanishing of all equivariant obstructions and the mapping degree ER - TY - GEN AB - 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. AU - Avvakumov, Sergey AU - Karasev, Roman ID - 8185 T2 - arXiv TI - Envy-free division using mapping degree ER - TY - GEN AB - 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$. AU - Deuchert, Andreas AU - Mayer, Simon AU - Seiringer, Robert ID - 7524 T2 - arXiv:1910.03372 TI - The free energy of the two-dimensional dilute Bose gas. I. Lower bound ER - TY - JOUR AB - 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. AU - Edelsbrunner, Herbert AU - Ölsböck, Katharina ID - 6608 JF - Computer Aided Geometric Design TI - Holes and dependences in an ordered complex VL - 73 ER - TY - CONF AB - 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). AU - Choudhuri, Arka Rai AU - Hubáček, Pavel AU - Kamath Hosdurg, Chethan AU - Pietrzak, Krzysztof Z AU - Rosen, Alon AU - Rothblum, Guy N. ID - 6677 SN - 9781450367059 T2 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019 TI - Finding a Nash equilibrium is no easier than breaking Fiat-Shamir ER - TY - JOUR AB - 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. AU - Lubiw, Anna AU - Masárová, Zuzana AU - Wagner, Uli ID - 5986 IS - 4 JF - Discrete & Computational Geometry SN - 0179-5376 TI - A proof of the orbit conjecture for flipping edge-labelled triangulations VL - 61 ER - TY - JOUR AB - 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. AU - Li, Xiang AU - Bighin, Giacomo AU - Yakaboylu, Enderalp AU - Lemeshko, Mikhail ID - 5886 JF - Molecular Physics SN - 00268976 TI - Variational approaches to quantum impurities: from the Fröhlich polaron to the angulon ER - TY - CONF AB - 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. AU - Huszár, Kristóf AU - Spreer, Jonathan ID - 6556 KW - computational 3-manifold topology KW - fixed-parameter tractability KW - layered triangulations KW - structural graph theory KW - treewidth KW - cutwidth KW - Heegaard genus SN - 1868-8969 T2 - 35th International Symposium on Computational Geometry TI - 3-manifold triangulations with small treewidth VL - 129 ER - TY - JOUR AB - 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)). AU - Huszár, Kristóf AU - Spreer, Jonathan AU - Wagner, Uli ID - 7093 IS - 2 JF - Journal of Computational Geometry SN - 1920-180X TI - On the treewidth of triangulated 3-manifolds VL - 10 ER - TY - JOUR AB - 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. AU - Dos Santos Caldas, Paulo R AU - Lopez Pelegrin, Maria D AU - Pearce, Daniel J. G. AU - Budanur, Nazmi B AU - Brugués, Jan AU - Loose, Martin ID - 7197 JF - Nature Communications SN - 2041-1723 TI - Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA VL - 10 ER - TY - JOUR AB - 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. AU - Tkadlec, Josef AU - Pavlogiannis, Andreas AU - Chatterjee, Krishnendu AU - Nowak, Martin A. ID - 7210 JF - Communications Biology SN - 2399-3642 TI - Population structure determines the tradeoff between fixation probability and fixation time VL - 2 ER - TY - CONF AB - 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. AU - Chatterjee, Krishnendu AU - Pavlogiannis, Andreas AU - Toman, Viktor ID - 10190 KW - safety KW - risk KW - reliability and quality KW - software T2 - Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications TI - Value-centric dynamic partial order reduction VL - 3 ER - TY - CONF AB - 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. AU - Alistarh, Dan-Adrian AU - Nadiradze, Giorgi AU - Koval, Nikita ID - 6673 SN - 9781450361842 T2 - 31st ACM Symposium on Parallelism in Algorithms and Architectures TI - Efficiency guarantees for parallel incremental algorithms under relaxed schedulers ER - TY - JOUR AB - 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. AU - Erdem, Fatma Asli AU - Ilic, Marija AU - Koppensteiner, Peter AU - Gołacki, Jakub AU - Lubec, Gert AU - Freissmuth, Michael AU - Sandtner, Walter ID - 7398 IS - 8 JF - The Journal of General Physiology SN - 0022-1295 TI - A comparison of the transport kinetics of glycine transporter 1 and glycine transporter 2 VL - 151 ER - TY - JOUR AB - 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. AU - Letts, James A AU - Fiedorczuk, Karol AU - Degliesposti, Gianluca AU - Skehel, Mark AU - Sazanov, Leonid A ID - 7395 IS - 6 JF - Molecular Cell SN - 1097-2765 TI - Structures of respiratory supercomplex I+III2 reveal functional and conformational crosstalk VL - 75 ER - TY - JOUR AB - 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. AU - Dura-Bernal, Salvador AU - Suter, Benjamin AU - Gleeson, Padraig AU - Cantarelli, Matteo AU - Quintana, Adrian AU - Rodriguez, Facundo AU - Kedziora, David J AU - Chadderdon, George L AU - Kerr, Cliff C AU - Neymotin, Samuel A AU - McDougal, Robert A AU - Hines, Michael AU - Shepherd, Gordon MG AU - Lytton, William W ID - 7405 JF - eLife SN - 2050-084X TI - NetPyNE, a tool for data-driven multiscale modeling of brain circuits VL - 8 ER - TY - JOUR AB - 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. AU - Veltsos, Paris AU - Ridout, Kate E. AU - Toups, Melissa A AU - González-Martínez, Santiago C. AU - Muyle, Aline AU - Emery, Olivier AU - Rastas, Pasi AU - Hudzieczek, Vojtech AU - Hobza, Roman AU - Vyskot, Boris AU - Marais, Gabriel A. B. AU - Filatov, Dmitry A. AU - Pannell, John R. ID - 7400 IS - 3 JF - Genetics SN - 0016-6731 TI - Early sex-chromosome evolution in the diploid dioecious plant Mercurialis annua VL - 212 ER - TY - JOUR AB - 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. AU - Stürner, Tomke AU - Tatarnikova, Anastasia AU - Müller, Jan AU - Schaffran, Barbara AU - Cuntz, Hermann AU - Zhang, Yun AU - Nemethova, Maria AU - Bogdan, Sven AU - Small, Vic AU - Tavosanis, Gaia ID - 7404 IS - 7 JF - Development SN - 0950-1991 TI - Transient localization of the Arp2/3 complex initiates neuronal dendrite branching in vivo VL - 146 ER - TY - CONF AB - 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. AU - Chatterjee, Krishnendu AU - Doyen, Laurent ID - 7402 SN - 9781728136080 T2 - 34th Annual ACM/IEEE Symposium on Logic in Computer Science TI - Graph planning with expected finite horizon ER - TY - JOUR AB - 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. AU - Vukics, A. AU - Dombi, A. AU - Fink, Johannes M AU - Domokos, P. ID - 7451 JF - Quantum SN - 2521-327X TI - Finite-size scaling of the photon-blockade breakdown dissipative quantum phase transition VL - 3 ER - TY - CONF AB - 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. AU - Swoboda, Paul AU - Kolmogorov, Vladimir ID - 7468 SN - 10636919 T2 - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition TI - Map inference via block-coordinate Frank-Wolfe algorithm VL - 2019-June ER - TY - JOUR AU - Morandell, Jasmin AU - Nicolas, Armel AU - Schwarz, Lena A AU - Novarino, Gaia ID - 7415 IS - Supplement 6 JF - European Neuropsychopharmacology SN - 0924-977X TI - S.16.05 Illuminating the role of the e3 ubiquitin ligase cullin3 in brain development and autism VL - 29 ER - TY - JOUR AU - Knaus, Lisa AU - Tarlungeanu, Dora-Clara AU - Novarino, Gaia ID - 7414 IS - Supplement 6 JF - European Neuropsychopharmacology SN - 0924-977X TI - S.16.03 A homozygous missense mutation in SLC7A5 leads to autism spectrum disorder and microcephaly VL - 29 ER - TY - JOUR AU - Benková, Eva AU - Dagdas, Yasin ID - 7394 IS - 12 JF - Current Opinion in Plant Biology SN - 1369-5266 TI - Editorial overview: Cell biology in the era of omics? VL - 52 ER - TY - CONF AB - 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. AU - Bui Thi Mai, Phuong AU - Lampert, Christoph ID - 7479 SN - 15505499 T2 - IEEE International Conference on Computer Vision TI - Distillation-based training for multi-exit architectures VL - 2019-October ER - TY - CONF AB - 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. AU - Wendler, Chris AU - Alistarh, Dan-Adrian AU - Püschel, Markus ID - 7542 SN - 1049-5258 TI - Powerset convolutional neural networks VL - 32 ER - TY - CHAP AB - 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. AU - Cremer, Sylvia AU - Kutzer, Megan ED - Choe, Jae ID - 7513 SN - 9780128132517 T2 - Encyclopedia of Animal Behavior TI - Social immunity ER - TY - CONF AB - 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. AU - Laccone, Francesco AU - Malomo, Luigi AU - Perez Rodriguez, Jesus AU - Pietroni, Nico AU - Ponchio, Federico AU - Bickel, Bernd AU - Cignoni, Paolo ID - 9261 SN - 2518-6582 T2 - 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 TI - FlexMaps Pavilion: A twisted arc made of mesostructured flat flexible panels ER - TY - CONF AB - 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. AU - Kolesnikov, Alexander AU - Kuznetsova, Alina AU - Lampert, Christoph AU - Ferrari, Vittorio ID - 7640 SN - 9781728150239 T2 - Proceedings of the 2019 International Conference on Computer Vision Workshop TI - Detecting visual relationships using box attention ER - TY - CONF AB - 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. AU - Rannen-Triki, Amal AU - Berman, Maxim AU - Kolmogorov, Vladimir AU - Blaschko, Matthew B. ID - 7639 SN - 9781728150239 T2 - Proceedings of the 2019 International Conference on Computer Vision Workshop TI - Function norms for neural networks ER - TY - CHAP AB - 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. AU - Barton, Nicholas H AU - Etheridge, Alison ED - Balding, David ED - Moltke, Ida ED - Marioni, John ID - 8281 SN - 9781119429142 T2 - Handbook of statistical genomics TI - Mathematical models in population genetics ER -