TY - JOUR AB - In a recent article (Jentzen et al. 2016 Commun. Math. Sci. 14, 1477–1500 (doi:10.4310/CMS.2016.v14. n6.a1)), it has been established that, for every arbitrarily slow convergence speed and every natural number d ? {4, 5, . . .}, there exist d-dimensional stochastic differential equations with infinitely often differentiable and globally bounded coefficients such that no approximation method based on finitely many observations of the driving Brownian motion can converge in absolute mean to the solution faster than the given speed of convergence. In this paper, we strengthen the above result by proving that this slow convergence phenomenon also arises in two (d = 2) and three (d = 3) space dimensions. AU - Gerencser, Mate AU - Jentzen, Arnulf AU - Salimova, Diyora ID - 560 IS - 2207 JF - Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences SN - 13645021 TI - On stochastic differential equations with arbitrarily slow convergence rates for strong approximation in two space dimensions VL - 473 ER - TY - BOOK AB - This book is a concise and self-contained introduction of recent techniques to prove local spectral universality for large random matrices. Random matrix theory is a fast expanding research area, and this book mainly focuses on the methods that the authors participated in developing over the past few years. Many other interesting topics are not included, and neither are several new developments within the framework of these methods. The authors have chosen instead to present key concepts that they believe are the core of these methods and should be relevant for future applications. They keep technicalities to a minimum to make the book accessible to graduate students. With this in mind, they include in this book the basic notions and tools for high-dimensional analysis, such as large deviation, entropy, Dirichlet form, and the logarithmic Sobolev inequality. AU - Erdös, László AU - Yau, Horng ID - 567 SN - 9-781-4704-3648-3 TI - A Dynamical Approach to Random Matrix Theory VL - 28 ER - TY - JOUR AB - We study robust properties of zero sets of continuous maps f: X → ℝn. Formally, we analyze the family Z< r(f) := (g-1(0): ||g - f|| < r) of all zero sets of all continuous maps g closer to f than r in the max-norm. All of these sets are outside A := (x: |f(x)| ≥ r) and we claim that Z< r(f) is fully determined by A and an element of a certain cohomotopy group which (by a recent result) is computable whenever the dimension of X is at most 2n - 3. By considering all r > 0 simultaneously, the pointed cohomotopy groups form a persistence module-a structure leading to persistence diagrams as in the case of persistent homology or well groups. Eventually, we get a descriptor of persistent robust properties of zero sets that has better descriptive power (Theorem A) and better computability status (Theorem B) than the established well diagrams. Moreover, if we endow every point of each zero set with gradients of the perturbation, the robust description of the zero sets by elements of cohomotopy groups is in some sense the best possible (Theorem C). AU - Franek, Peter AU - Krcál, Marek ID - 568 IS - 2 JF - Homology, Homotopy and Applications SN - 15320073 TI - Persistence of zero sets VL - 19 ER - TY - JOUR AB - Most phenotypes are determined by molecular systems composed of specifically interacting molecules. However, unlike for individual components, little is known about the distributions of mutational effects of molecular systems as a whole. We ask how the distribution of mutational effects of a transcriptional regulatory system differs from the distributions of its components, by first independently, and then simultaneously, mutating a transcription factor and the associated promoter it represses. We find that the system distribution exhibits increased phenotypic variation compared to individual component distributions - an effect arising from intermolecular epistasis between the transcription factor and its DNA-binding site. In large part, this epistasis can be qualitatively attributed to the structure of the transcriptional regulatory system and could therefore be a common feature in prokaryotes. Counter-intuitively, intermolecular epistasis can alleviate the constraints of individual components, thereby increasing phenotypic variation that selection could act on and facilitating adaptive evolution. AU - Lagator, Mato AU - Sarikas, Srdjan AU - Acar, Hande AU - Bollback, Jonathan P AU - Guet, Calin C ID - 570 JF - eLife SN - 2050084X TI - Regulatory network structure determines patterns of intermolecular epistasis VL - 6 ER - TY - JOUR AB - The actomyosin ring generates force to ingress the cytokinetic cleavage furrow in animal cells, yet its filament organization and the mechanism of contractility is not well understood. We quantified actin filament order in human cells using fluorescence polarization microscopy and found that cleavage furrow ingression initiates by contraction of an equatorial actin network with randomly oriented filaments. The network subsequently gradually reoriented actin filaments along the cell equator. This strictly depended on myosin II activity, suggesting local network reorganization by mechanical forces. Cortical laser microsurgery revealed that during cytokinesis progression, mechanical tension increased substantially along the direction of the cell equator, while the network contracted laterally along the pole-to-pole axis without a detectable increase in tension. Our data suggest that an asymmetric increase in cortical tension promotes filament reorientation along the cytokinetic cleavage furrow, which might have implications for diverse other biological processes involving actomyosin rings. AU - Spira, Felix AU - Cuylen Haering, Sara AU - Mehta, Shalin AU - Samwer, Matthias AU - Reversat, Anne AU - Verma, Amitabh AU - Oldenbourg, Rudolf AU - Sixt, Michael K AU - Gerlich, Daniel ID - 569 JF - eLife SN - 2050084X TI - Cytokinesis in vertebrate cells initiates by contraction of an equatorial actomyosin network composed of randomly oriented filaments VL - 6 ER - TY - JOUR AB - Blood platelets are critical for hemostasis and thrombosis and play diverse roles during immune responses. Despite these versatile tasks in mammalian biology, their skills on a cellular level are deemed limited, mainly consisting in rolling, adhesion, and aggregate formation. Here, we identify an unappreciated asset of platelets and show that adherent platelets use adhesion receptors to mechanically probe the adhesive substrate in their local microenvironment. When actomyosin-dependent traction forces overcome substrate resistance, platelets migrate and pile up the adhesive substrate together with any bound particulate material. They use this ability to act as cellular scavengers, scanning the vascular surface for potential invaders and collecting deposited bacteria. Microbe collection by migrating platelets boosts the activity of professional phagocytes, exacerbating inflammatory tissue injury in sepsis. This assigns platelets a central role in innate immune responses and identifies them as potential targets to dampen inflammatory tissue damage in clinical scenarios of severe systemic infection. In addition to their role in thrombosis and hemostasis, platelets can also migrate to sites of infection to help trap bacteria and clear the vascular surface. AU - Gärtner, Florian R AU - Ahmad, Zerkah AU - Rosenberger, Gerhild AU - Fan, Shuxia AU - Nicolai, Leo AU - Busch, Benjamin AU - Yavuz, Gökce AU - Luckner, Manja AU - Ishikawa Ankerhold, Hellen AU - Hennel, Roman AU - Benechet, Alexandre AU - Lorenz, Michael AU - Chandraratne, Sue AU - Schubert, Irene AU - Helmer, Sebastian AU - Striednig, Bianca AU - Stark, Konstantin AU - Janko, Marek AU - Böttcher, Ralph AU - Verschoor, Admar AU - Leon, Catherine AU - Gachet, Christian AU - Gudermann, Thomas AU - Mederos Y Schnitzler, Michael AU - Pincus, Zachary AU - Iannacone, Matteo AU - Haas, Rainer AU - Wanner, Gerhard AU - Lauber, Kirsten AU - Sixt, Michael K AU - Massberg, Steffen ID - 571 IS - 6 JF - Cell Press SN - 00928674 TI - Migrating platelets are mechano scavengers that collect and bundle bacteria VL - 171 ER - TY - JOUR AB - In this review, we summarize the different biosynthesis-related pathways that contribute to the regulation of endogenous auxin in plants. We demonstrate that all known genes involved in auxin biosynthesis also have a role in root formation, from the initiation of a root meristem during embryogenesis to the generation of a functional root system with a primary root, secondary lateral root branches and adventitious roots. Furthermore, the versatile adaptation of root development in response to environmental challenges is mediated by both local and distant control of auxin biosynthesis. In conclusion, auxin homeostasis mediated by spatial and temporal regulation of auxin biosynthesis plays a central role in determining root architecture. AU - Olatunji, Damilola AU - Geelen, Danny AU - Verstraeten, Inge ID - 572 IS - 12 JF - International Journal of Molecular Sciences TI - Control of endogenous auxin levels in plant root development VL - 18 ER - TY - CONF AB - Tunneling of a particle through a potential barrier remains one of the most remarkable quantum phenomena. Owing to advances in laser technology, electric fields comparable to those electrons experience in atoms are readily generated and open opportunities to dynamically investigate the process of electron tunneling through the potential barrier formed by the superposition of both laser and atomic fields. Attosecond-time and angstrom-space resolution of the strong laser-field technique allow to address fundamental questions related to tunneling, which are still open and debated: Which time is spent under the barrier and what momentum is picked up by the particle in the meantime? In this combined experimental and theoretical study we demonstrate that for strong-field ionization the leading quantum mechanical Wigner treatment for the time resolved description of tunneling is valid. We achieve a high sensitivity on the tunneling barrier and unambiguously isolate its effects by performing a differential study of two systems with almost identical tunneling geometry. Moreover, working with a low frequency laser, we essentially limit the non-adiabaticity of the process as a major source of uncertainty. The agreement between experiment and theory implies two substantial corrections with respect to the widely employed quasiclassical treatment: In addition to a non-vanishing longitudinal momentum along the laser field-direction we provide clear evidence for a non-zero tunneling time delay. This addresses also the fundamental question how the transition occurs from the tunnel barrier to free space classical evolution of the ejected electron. AU - Camus, Nicolas AU - Yakaboylu, Enderalp AU - Fechner, Lutz AU - Klaiber, Michael AU - Laux, Martin AU - Mi, Yonghao AU - Hatsagortsyan, Karen AU - Pfeifer, Thomas AU - Keitel, Cristoph AU - Moshammer, Robert ID - 313 IS - 1 SN - 17426588 TI - Experimental evidence for Wigner's tunneling time VL - 999 ER - TY - JOUR AB - The first hundred attoseconds of the electron dynamics during strong field tunneling ionization are investigated. We quantify theoretically how the electron’s classical trajectories in the continuum emerge from the tunneling process and test the results with those achieved in parallel from attoclock measurements. An especially high sensitivity on the tunneling barrier is accomplished here by comparing the momentum distributions of two atomic species of slightly deviating atomic potentials (argon and krypton) being ionized under absolutely identical conditions with near-infrared laser pulses (1300 nm). The agreement between experiment and theory provides clear evidence for a nonzero tunneling time delay and a nonvanishing longitudinal momentum of the electron at the “tunnel exit.” AU - Camus, Nicolas AU - Yakaboylu, Enderalp AU - Fechner, Lutz AU - Klaiber, Michael AU - Laux, Martin AU - Mi, Yonghao AU - Hatsagortsyan, Karen Z. AU - Pfeifer, Thomas AU - Keitel, Christoph H. AU - Moshammer, Robert ID - 6013 IS - 2 JF - Physical Review Letters SN - 0031-9007 TI - Experimental evidence for quantum tunneling time VL - 119 ER - TY - CONF AB - Position based cryptography (PBC), proposed in the seminal work of Chandran, Goyal, Moriarty, and Ostrovsky (SIAM J. Computing, 2014), aims at constructing cryptographic schemes in which the identity of the user is his geographic position. Chandran et al. construct PBC schemes for secure positioning and position-based key agreement in the bounded-storage model (Maurer, J. Cryptology, 1992). Apart from bounded memory, their security proofs need a strong additional restriction on the power of the adversary: he cannot compute joint functions of his inputs. Removing this assumption is left as an open problem. We show that an answer to this question would resolve a long standing open problem in multiparty communication complexity: finding a function that is hard to compute with low communication complexity in the simultaneous message model, but easy to compute in the fully adaptive model. On a more positive side: we also show some implications in the other direction, i.e.: we prove that lower bounds on the communication complexity of certain multiparty problems imply existence of PBC primitives. Using this result we then show two attractive ways to “bypass” our hardness result: the first uses the random oracle model, the second weakens the locality requirement in the bounded-storage model to online computability. The random oracle construction is arguably one of the simplest proposed so far in this area. Our results indicate that constructing improved provably secure protocols for PBC requires a better understanding of multiparty communication complexity. This is yet another example where negative results in one area (in our case: lower bounds in multiparty communication complexity) can be used to construct secure cryptographic schemes. AU - Brody, Joshua AU - Dziembowski, Stefan AU - Faust, Sebastian AU - Pietrzak, Krzysztof Z ED - Kalai, Yael ED - Reyzin, Leonid ID - 605 SN - 978-331970499-9 TI - Position based cryptography and multiparty communication complexity VL - 10677 ER - TY - CHAP AB - In several settings of physics and chemistry one has to deal with molecules interacting with some kind of an external environment, be it a gas, a solution, or a crystal surface. Understanding molecular processes in the presence of such a many-particle bath is inherently challenging, and usually requires large-scale numerical computations. Here, we present an alternative approach to the problem, based on the notion of the angulon quasiparticle. We show that molecules rotating inside superfluid helium nanodroplets and Bose–Einstein condensates form angulons, and therefore can be described by straightforward solutions of a simple microscopic Hamiltonian. Casting the problem in the language of angulons allows us not only to greatly simplify it, but also to gain insights into the origins of the observed phenomena and to make predictions for future experimental studies. AU - Lemeshko, Mikhail AU - Schmidt, Richard ED - Dulieu, Oliver ED - Osterwalder, Andreas ID - 604 SN - 20413181 T2 - Cold Chemistry: Molecular Scattering and Reactivity Near Absolute Zero TI - Molecular impurities interacting with a many-particle environment: From ultracold gases to helium nanodroplets VL - 11 ER - TY - CONF AB - Several cryptographic schemes and applications are based on functions that are both reasonably efficient to compute and moderately hard to invert, including client puzzles for Denial-of-Service protection, password protection via salted hashes, or recent proof-of-work blockchain systems. Despite their wide use, a definition of this concept has not yet been distilled and formalized explicitly. Instead, either the applications are proven directly based on the assumptions underlying the function, or some property of the function is proven, but the security of the application is argued only informally. The goal of this work is to provide a (universal) definition that decouples the efforts of designing new moderately hard functions and of building protocols based on them, serving as an interface between the two. On a technical level, beyond the mentioned definitions, we instantiate the model for four different notions of hardness. We extend the work of Alwen and Serbinenko (STOC 2015) by providing a general tool for proving security for the first notion of memory-hard functions that allows for provably secure applications. The tool allows us to recover all of the graph-theoretic techniques developed for proving security under the older, non-composable, notion of security used by Alwen and Serbinenko. As an application of our definition of moderately hard functions, we prove the security of two different schemes for proofs of effort (PoE). We also formalize and instantiate the concept of a non-interactive proof of effort (niPoE), in which the proof is not bound to a particular communication context but rather any bit-string chosen by the prover. AU - Alwen, Joel F AU - Tackmann, Björn ED - Kalai, Yael ED - Reyzin, Leonid ID - 609 SN - 978-331970499-9 TI - Moderately hard functions: Definition, instantiations, and applications VL - 10677 ER - TY - JOUR AB - The fact that the complete graph K5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph Kn embeds in a closed surface M (other than the Klein bottle) if and only if (n−3)(n−4) ≤ 6b1(M), where b1(M) is the first Z2-Betti number of M. On the other hand, van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of Kn+1) embeds in R2k if and only if n ≤ 2k + 1. Two decades ago, Kühnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k − 1)-connected 2k-manifold with kth Z2-Betti number bk only if the following generalized Heawood inequality holds: (k+1 n−k−1) ≤ (k+1 2k+1)bk. This is a common generalization of the case of graphs on surfaces as well as the van Kampen–Flores theorem. In the spirit of Kühnel’s conjecture, we prove that if the k-skeleton of the n-simplex embeds in a compact 2k-manifold with kth Z2-Betti number bk, then n ≤ 2bk(k 2k+2)+2k+4. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k−1)-connected. Our results generalize to maps without q-covered points, in the spirit of Tverberg’s theorem, for q a prime power. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition. AU - Goaoc, Xavier AU - Mabillard, Isaac AU - Paták, Pavel AU - Patakova, Zuzana AU - Tancer, Martin AU - Wagner, Uli ID - 610 IS - 2 JF - Israel Journal of Mathematics TI - On generalized Heawood inequalities for manifolds: A van Kampen–Flores type nonembeddability result VL - 222 ER - TY - JOUR AB - Small RNAs (sRNAs) regulate genes in plants and animals. Here, we show that population-wide differences in color patterns in snapdragon flowers are caused by an inverted duplication that generates sRNAs. The complexity and size of the transcripts indicate that the duplication represents an intermediate on the pathway to microRNA evolution. The sRNAs repress a pigment biosynthesis gene, creating a yellow highlight at the site of pollinator entry. The inverted duplication exhibits steep clines in allele frequency in a natural hybrid zone, showing that the allele is under selection. Thus, regulatory interactions of evolutionarily recent sRNAs can be acted upon by selection and contribute to the evolution of phenotypic diversity. AU - Bradley, Desmond AU - Xu, Ping AU - Mohorianu, Irina AU - Whibley, Annabel AU - Field, David AU - Tavares, Hugo AU - Couchman, Matthew AU - Copsey, Lucy AU - Carpenter, Rosemary AU - Li, Miaomiao AU - Li, Qun AU - Xue, Yongbiao AU - Dalmay, Tamas AU - Coen, Enrico ID - 611 IS - 6365 JF - Science SN - 00368075 TI - Evolution of flower color pattern through selection on regulatory small RNAs VL - 358 ER - TY - JOUR AB - Bacteria in groups vary individually, and interact with other bacteria and the environment to produce population-level patterns of gene expression. Investigating such behavior in detail requires measuring and controlling populations at the single-cell level alongside precisely specified interactions and environmental characteristics. Here we present an automated, programmable platform that combines image-based gene expression and growth measurements with on-line optogenetic expression control for hundreds of individual Escherichia coli cells over days, in a dynamically adjustable environment. This integrated platform broadly enables experiments that bridge individual and population behaviors. We demonstrate: (i) population structuring by independent closed-loop control of gene expression in many individual cells, (ii) cell-cell variation control during antibiotic perturbation, (iii) hybrid bio-digital circuits in single cells, and freely specifiable digital communication between individual bacteria. These examples showcase the potential for real-time integration of theoretical models with measurement and control of many individual cells to investigate and engineer microbial population behavior. AU - Chait, Remy P AU - Ruess, Jakob AU - Bergmiller, Tobias AU - Tkacik, Gasper AU - Guet, Calin C ID - 613 IS - 1 JF - Nature Communications SN - 20411723 TI - Shaping bacterial population behavior through computer interfaced control of individual cells VL - 8 ER - TY - JOUR AB - We show that the Dyson Brownian Motion exhibits local universality after a very short time assuming that local rigidity and level repulsion of the eigenvalues hold. These conditions are verified, hence bulk spectral universality is proven, for a large class of Wigner-like matrices, including deformed Wigner ensembles and ensembles with non-stochastic variance matrices whose limiting densities differ from Wigner's semicircle law. AU - Erdös, László AU - Schnelli, Kevin ID - 615 IS - 4 JF - Annales de l'institut Henri Poincare (B) Probability and Statistics SN - 02460203 TI - Universality for random matrix flows with time dependent density VL - 53 ER - TY - CHAP AB - Genetic factors might be largely responsible for the development of autism spectrum disorder (ASD) that alone or in combination with specific environmental risk factors trigger the pathology. Multiple mutations identified in ASD patients that impair synaptic function in the central nervous system are well studied in animal models. How these mutations might interact with other risk factors is not fully understood though. Additionally, how systems outside of the brain are altered in the context of ASD is an emerging area of research. Extracerebral influences on the physiology could begin in utero and contribute to changes in the brain and in the development of other body systems and further lead to epigenetic changes. Therefore, multiple recent studies have aimed at elucidating the role of gene-environment interactions in ASD. Here we provide an overview on the extracerebral systems that might play an important associative role in ASD and review evidence regarding the potential roles of inflammation, trace metals, metabolism, genetic susceptibility, enteric nervous system function and the microbiota of the gastrointestinal (GI) tract on the development of endophenotypes in animal models of ASD. By influencing environmental conditions, it might be possible to reduce or limit the severity of ASD pathology. AU - Hill Yardin, Elisa AU - Mckeown, Sonja AU - Novarino, Gaia AU - Grabrucker, Andreas ED - Schmeisser, Michael ED - Boekers, Tobias ID - 623 SN - 03015556 T2 - Translational Anatomy and Cell Biology of Autism Spectrum Disorder TI - Extracerebral dysfunction in animal models of autism spectrum disorder VL - 224 ER - TY - JOUR AB - Our focus here is on the infinitesimal model. In this model, one or several quantitative traits are described as the sum of a genetic and a non-genetic component, the first being distributed within families as a normal random variable centred at the average of the parental genetic components, and with a variance independent of the parental traits. Thus, the variance that segregates within families is not perturbed by selection, and can be predicted from the variance components. This does not necessarily imply that the trait distribution across the whole population should be Gaussian, and indeed selection or population structure may have a substantial effect on the overall trait distribution. One of our main aims is to identify some general conditions on the allelic effects for the infinitesimal model to be accurate. We first review the long history of the infinitesimal model in quantitative genetics. Then we formulate the model at the phenotypic level in terms of individual trait values and relationships between individuals, but including different evolutionary processes: genetic drift, recombination, selection, mutation, population structure, …. We give a range of examples of its application to evolutionary questions related to stabilising selection, assortative mating, effective population size and response to selection, habitat preference and speciation. We provide a mathematical justification of the model as the limit as the number M of underlying loci tends to infinity of a model with Mendelian inheritance, mutation and environmental noise, when the genetic component of the trait is purely additive. We also show how the model generalises to include epistatic effects. We prove in particular that, within each family, the genetic components of the individual trait values in the current generation are indeed normally distributed with a variance independent of ancestral traits, up to an error of order 1∕M. Simulations suggest that in some cases the convergence may be as fast as 1∕M. AU - Barton, Nicholas H AU - Etheridge, Alison AU - Véber, Amandine ID - 626 JF - Theoretical Population Biology SN - 00405809 TI - The infinitesimal model: Definition derivation and implications VL - 118 ER - TY - CHAP AB - In the analysis of reactive systems a quantitative objective assigns a real value to every trace of the system. The value decision problem for a quantitative objective requires a trace whose value is at least a given threshold, and the exact value decision problem requires a trace whose value is exactly the threshold. We compare the computational complexity of the value and exact value decision problems for classical quantitative objectives, such as sum, discounted sum, energy, and mean-payoff for two standard models of reactive systems, namely, graphs and graph games. AU - Chatterjee, Krishnendu AU - Doyen, Laurent AU - Henzinger, Thomas A ED - Aceto, Luca ED - Bacci, Giorgio ED - Ingólfsdóttir, Anna ED - Legay, Axel ED - Mardare, Radu ID - 625 SN - 0302-9743 T2 - Models, Algorithms, Logics and Tools TI - The cost of exactness in quantitative reachability VL - 10460 ER - TY - JOUR AB - Bacteria adapt to adverse environmental conditions by altering gene expression patterns. Recently, a novel stress adaptation mechanism has been described that allows Escherichia coli to alter gene expression at the post-transcriptional level. The key player in this regulatory pathway is the endoribonuclease MazF, the toxin component of the toxin-antitoxin module mazEF that is triggered by various stressful conditions. In general, MazF degrades the majority of transcripts by cleaving at ACA sites, which results in the retardation of bacterial growth. Furthermore, MazF can process a small subset of mRNAs and render them leaderless by removing their ribosome binding site. MazF concomitantly modifies ribosomes, making them selective for the translation of leaderless mRNAs. In this study, we employed fluorescent reporter-systems to investigate mazEF expression during stressful conditions, and to infer consequences of the mRNA processing mediated by MazF on gene expression at the single-cell level. Our results suggest that mazEF transcription is maintained at low levels in single cells encountering adverse conditions, such as antibiotic stress or amino acid starvation. Moreover, using the grcA mRNA as a model for MazF-mediated mRNA processing, we found that MazF activation promotes heterogeneity in the grcA reporter expression, resulting in a subpopulation of cells with increased levels of GrcA reporter protein. AU - Nikolic, Nela AU - Didara, Zrinka AU - Moll, Isabella ID - 624 IS - 9 JF - PeerJ SN - 21678359 TI - MazF activation promotes translational heterogeneity of the grcA mRNA in Escherichia coli populations VL - 2017 ER - TY - CONF AB - We consider the problem of developing automated techniques for solving recurrence relations to aid the expected-runtime analysis of programs. The motivation is that several classical textbook algorithms have quite efficient expected-runtime complexity, whereas the corresponding worst-case bounds are either inefficient (e.g., Quick-Sort), or completely ineffective (e.g., Coupon-Collector). Since the main focus of expected-runtime analysis is to obtain efficient bounds, we consider bounds that are either logarithmic, linear or almost-linear (O(log n), O(n), O(n · log n), respectively, where n represents the input size). Our main contribution is an efficient (simple linear-time algorithm) sound approach for deriving such expected-runtime bounds for the analysis of recurrence relations induced by randomized algorithms. The experimental results show that our approach can efficiently derive asymptotically optimal expected-runtime bounds for recurrences of classical randomized algorithms, including Randomized-Search, Quick-Sort, Quick-Select, Coupon-Collector, where the worst-case bounds are either inefficient (such as linear as compared to logarithmic expected-runtime complexity, or quadratic as compared to linear or almost-linear expected-runtime complexity), or ineffective. AU - Chatterjee, Krishnendu AU - Fu, Hongfei AU - Murhekar, Aniket ED - Majumdar, Rupak ED - Kunčak, Viktor ID - 628 SN - 978-331963386-2 TI - Automated recurrence analysis for almost linear expected runtime bounds VL - 10426 ER - TY - CHAP AB - Even simple cells like bacteria have precisely regulated cellular anatomies, which allow them to grow, divide and to respond to internal or external cues with high fidelity. How spatial and temporal intracellular organization in prokaryotic cells is achieved and maintained on the basis of locally interacting proteins still remains largely a mystery. Bulk biochemical assays with purified components and in vivo experiments help us to approach key cellular processes from two opposite ends, in terms of minimal and maximal complexity. However, to understand how cellular phenomena emerge, that are more than the sum of their parts, we have to assemble cellular subsystems step by step from the bottom up. Here, we review recent in vitro reconstitution experiments with proteins of the bacterial cell division machinery and illustrate how they help to shed light on fundamental cellular mechanisms that constitute spatiotemporal order and regulate cell division. AU - Loose, Martin AU - Zieske, Katja AU - Schwille, Petra ID - 629 T2 - Prokaryotic Cytoskeletons TI - Reconstitution of protein dynamics involved in bacterial cell division VL - 84 ER - TY - CONF AB - Background: Standards have become available to share semantically encoded vital parameters from medical devices, as required for example by personal healthcare records. Standardised sharing of biosignal data largely remains open. Objectives: The goal of this work is to explore available biosignal file format and data exchange standards and profiles, and to conceptualise end-To-end solutions. Methods: The authors reviewed and discussed available biosignal file format standards with other members of international standards development organisations (SDOs). Results: A raw concept for standards based acquisition, storage, archiving and sharing of biosignals was developed. The GDF format may serve for storing biosignals. Signals can then be shared using FHIR resources and may be stored on FHIR servers or in DICOM archives, with DICOM waveforms as one possible format. Conclusion: Currently a group of international SDOs (e.g. HL7, IHE, DICOM, IEEE) is engaged in intensive discussions. This discussion extends existing work that already was adopted by large implementer communities. The concept presented here only reports the current status of the discussion in Austria. The discussion will continue internationally, with results to be expected over the coming years. AU - Sauermann, Stefan AU - David, Veronika AU - Schlögl, Alois AU - Egelkraut, Reinhard AU - Frohner, Matthias AU - Pohn, Birgit AU - Urbauer, Philipp AU - Mense, Alexander ID - 630 SN - 978-161499758-0 TI - Biosignals standards and FHIR: The way to go VL - 236 ER - TY - JOUR AB - We consider a 2D quantum system of N bosons in a trapping potential |x|s, interacting via a pair potential of the form N2β−1 w(Nβ x). We show that for all 0 < β < (s + 1)/(s + 2), the leading order behavior of ground states of the many-body system is described in the large N limit by the corresponding cubic nonlinear Schrödinger energy functional. Our result covers the focusing case (w < 0) where even the stability of the many-body system is not obvious. This answers an open question mentioned by X. Chen and J. Holmer for harmonic traps (s = 2). Together with the BBGKY hierarchy approach used by these authors, our result implies the convergence of the many-body quantum dynamics to the focusing NLS equation with harmonic trap for all 0 < β < 3/4. AU - Lewin, Mathieu AU - Nam, Phan AU - Rougerie, Nicolas ID - 632 IS - 6 JF - Proceedings of the American Mathematical Society TI - A note on 2D focusing many boson systems VL - 145 ER - TY - CHAP AB - As autism spectrum disorder (ASD) is largely regarded as a neurodevelopmental condition, long-time consensus was that its hallmark features are irreversible. However, several studies from recent years using defined mouse models of ASD have provided clear evidence that in mice neurobiological and behavioural alterations can be ameliorated or even reversed by genetic restoration or pharmacological treatment either before or after symptom onset. Here, we review findings on genetic and pharmacological reversibility of phenotypes in mouse models of ASD. Our review should give a comprehensive overview on both aspects and encourage future studies to better understand the underlying molecular mechanisms that might be translatable from animals to humans. AU - Schroeder, Jan AU - Deliu, Elena AU - Novarino, Gaia AU - Schmeisser, Michael ED - Schmeisser, Michael ED - Boekers, Tobias ID - 634 T2 - Translational Anatomy and Cell Biology of Autism Spectrum Disorder TI - Genetic and pharmacological reversibility of phenotypes in mouse models of autism spectrum disorder VL - 224 ER - TY - CONF AB - A Rapidly-exploring Random Tree (RRT) is an algorithm which can search a non-convex region of space by incrementally building a space-filling tree. The tree is constructed from random points drawn from system’s state space and is biased to grow towards large unexplored areas in the system. RRT can provide better coverage of a system’s possible behaviors compared with random simulations, but is more lightweight than full reachability analysis. In this paper, we explore some of the design decisions encountered while implementing a hybrid extension of the RRT algorithm, which have not been elaborated on before. In particular, we focus on handling non-determinism, which arises due to discrete transitions. We introduce the notion of important points to account for this phenomena. We showcase our ideas using heater and navigation benchmarks. AU - Bak, Stanley AU - Bogomolov, Sergiy AU - Henzinger, Thomas A AU - Kumar, Aviral ED - Abate, Alessandro ED - Bodo, Sylvie ID - 633 SN - 978-331963500-2 TI - Challenges and tool implementation of hybrid rapidly exploring random trees VL - 10381 ER - TY - CONF AB - Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is dominated by memory cost. As memory, unlike computation, costs about the same across different platforms, MHFs cannot be evaluated at significantly lower cost on dedicated hardware like ASICs. MHFs have found widespread applications including password hashing, key derivation, and proofs-of-work. This paper focuses on scrypt, a simple candidate MHF designed by Percival, and described in RFC 7914. It has been used within a number of cryptocurrencies (e.g., Litecoin and Dogecoin) and has been an inspiration for Argon2d, one of the winners of the recent password-hashing competition. Despite its popularity, no rigorous lower bounds on its memory complexity are known. We prove that scrypt is optimally memory-hard, i.e., its cumulative memory complexity (cmc) in the parallel random oracle model is Ω(n2w), where w and n are the output length and number of invocations of the underlying hash function, respectively. High cmc is a strong security target for MHFs introduced by Alwen and Serbinenko (STOC’15) which implies high memory cost even for adversaries who can amortize the cost over many evaluations and evaluate the underlying hash functions many times in parallel. Our proof is the first showing optimal memory-hardness for any MHF. Our result improves both quantitatively and qualitatively upon the recent work by Alwen et al. (EUROCRYPT’16) who proved a weaker lower bound of Ω(n2w/ log2 n) for a restricted class of adversaries. AU - Alwen, Joel F AU - Chen, Binchi AU - Pietrzak, Krzysztof Z AU - Reyzin, Leonid AU - Tessaro, Stefano ED - Coron, Jean-Sébastien ED - Buus Nielsen, Jesper ID - 635 SN - 978-331956616-0 TI - Scrypt is maximally memory hard VL - 10212 ER - TY - CONF AB - Signal regular expressions can specify sequential properties of real-valued signals based on threshold conditions, regular operations, and duration constraints. In this paper we endow them with a quantitative semantics which indicates how robustly a signal matches or does not match a given expression. First, we show that this semantics is a safe approximation of a distance between the signal and the language defined by the expression. Then, we consider the robust matching problem, that is, computing the quantitative semantics of every segment of a given signal relative to an expression. We present an algorithm that solves this problem for piecewise-constant and piecewise-linear signals and show that for such signals the robustness map is a piecewise-linear function. The availability of an indicator describing how robustly a signal segment matches some regular pattern provides a general framework for quantitative monitoring of cyber-physical systems. AU - Bakhirkin, Alexey AU - Ferrere, Thomas AU - Maler, Oded AU - Ulus, Dogan ED - Abate, Alessandro ED - Geeraerts, Gilles ID - 636 SN - 978-331965764-6 TI - On the quantitative semantics of regular expressions over real-valued signals VL - 10419 ER - TY - GEN AB - This book constitutes the refereed proceedings of the 9th InternationalWorkshop on Numerical Software Verification, NSV 2016, held in Toronto, ON, Canada in July 2011 - colocated with CAV 2016, the 28th International Conference on Computer Aided Verification. The NSV workshop is dedicated to the development of logical and mathematical techniques for the reasoning about programmability and reliability. ED - Bogomolov, Sergiy ED - Martel, Matthieu ED - Prabhakar, Pavithra ID - 638 SN - 0302-9743 TI - Numerical Software Verification VL - 10152 ER - TY - CONF AB - Data-independent Memory Hard Functions (iMHFS) are finding a growing number of applications in security; especially in the domain of password hashing. An important property of a concrete iMHF is specified by fixing a directed acyclic graph (DAG) Gn on n nodes. The quality of that iMHF is then captured by the following two pebbling complexities of Gn: – The parallel cumulative pebbling complexity Π∥cc(Gn) must be as high as possible (to ensure that the amortized cost of computing the function on dedicated hardware is dominated by the cost of memory). – The sequential space-time pebbling complexity Πst(Gn) should be as close as possible to Π∥cc(Gn) (to ensure that using many cores in parallel and amortizing over many instances does not give much of an advantage). In this paper we construct a family of DAGs with best possible parameters in an asymptotic sense, i.e., where Π∥cc(Gn) = Ω(n2/ log(n)) (which matches a known upper bound) and Πst(Gn) is within a constant factor of Π∥cc(Gn). Our analysis relies on a new connection between the pebbling complexity of a DAG and its depth-robustness (DR) – a well studied combinatorial property. We show that high DR is sufficient for high Π∥cc. Alwen and Blocki (CRYPTO’16) showed that high DR is necessary and so, together, these results fully characterize DAGs with high Π∥cc in terms of DR. Complementing these results, we provide new upper and lower bounds on the Π∥cc of several important candidate iMHFs from the literature. We give the first lower bounds on the memory hardness of the Catena and Balloon Hashing functions in a parallel model of computation and we give the first lower bounds of any kind for (a version) of Argon2i. Finally we describe a new class of pebbling attacks improving on those of Alwen and Blocki (CRYPTO’16). By instantiating these attacks we upperbound the Π∥cc of the Password Hashing Competition winner Argon2i and one of the Balloon Hashing functions by O (n1.71). We also show an upper bound of O(n1.625) for the Catena functions and the two remaining Balloon Hashing functions. AU - Alwen, Joel F AU - Blocki, Jeremiah AU - Pietrzak, Krzysztof Z ED - Coron, Jean-Sébastien ED - Buus Nielsen, Jesper ID - 640 SN - 978-331956616-0 TI - Depth-robust graphs and their cumulative memory complexity VL - 10212 ER - TY - CONF AB - We introduce two novel methods for learning parameters of graphical models for image labelling. The following two tasks underline both methods: (i) perturb model parameters based on given features and ground truth labelings, so as to exactly reproduce these labelings as optima of the local polytope relaxation of the labelling problem; (ii) train a predictor for the perturbed model parameters so that improved model parameters can be applied to the labelling of novel data. Our first method implements task (i) by inverse linear programming and task (ii) using a regressor e.g. a Gaussian process. Our second approach simultaneously solves tasks (i) and (ii) in a joint manner, while being restricted to linearly parameterised predictors. Experiments demonstrate the merits of both approaches. AU - Trajkovska, Vera AU - Swoboda, Paul AU - Åström, Freddie AU - Petra, Stefanie ED - Lauze, François ED - Dong, Yiqiu ED - Bjorholm Dahl, Anders ID - 641 SN - 978-331958770-7 TI - Graphical model parameter learning by inverse linear programming VL - 10302 ER - TY - GEN AB - Synchronous programs are easy to specify because the side effects of an operation are finished by the time the invocation of the operation returns to the caller. Asynchronous programs, on the other hand, are difficult to specify because there are side effects due to pending computation scheduled as a result of the invocation of an operation. They are also difficult to verify because of the large number of possible interleavings of concurrent asynchronous computation threads. We show that specifications and correctness proofs for asynchronous programs can be structured by introducing the fiction, for proof purposes, that intermediate, non-quiescent states of asynchronous operations can be ignored. Then, the task of specification becomes relatively simple and the task of verification can be naturally decomposed into smaller sub-tasks. The sub-tasks iteratively summarize, guided by the structure of an asynchronous program, the atomic effect of non-atomic operations and the synchronous effect of asynchronous operations. This structuring of specifications and proofs corresponds to the introduction of multiple layers of stepwise refinement for asynchronous programs. We present the first proof rule, called synchronization, to reduce asynchronous invocations on a lower layer to synchronous invocations on a higher layer. We implemented our proof method in CIVL and evaluated it on a collection of benchmark programs. AU - Henzinger, Thomas A AU - Kragl, Bernhard AU - Qadeer, Shaz ID - 6426 SN - 2664-1690 TI - Synchronizing the asynchronous ER - TY - JOUR AB - It has been reported that nicotinamide-overload induces oxidative stress associated with insulin resistance, the key feature of type 2 diabetes mellitus (T2DM). This study aimed to investigate the effects of B vitamins in T2DM. Glucose tolerance tests (GTT) were carried out in adult Sprague-Dawley rats treated with or without cumulative doses of B vitamins. More specifically, insulin tolerance tests (ITT) were also carried out in adult Sprague-Dawley rats treated with or without cumulative doses of Vitamin B3. We found that cumulative Vitamin B1 and Vitamin B3 administration significantly increased the plasma H2O2 levels associated with high insulin levels. Only Vitamin B3 reduced muscular and hepatic glycogen contents. Cumulative administration of nicotinic acid, another form of Vitamin B3, also significantly increased plasma insulin level and H2O2 generation. Moreover, cumulative administration of nicotinic acid or nicotinamide impaired glucose metabolism. This study suggested that excess Vitamin B1 and Vitamin B3 caused oxidative stress and insulin resistance. AU - Sun, Wuping AU - Zhai, Ming-Zhu AU - Zhou, Qian AU - Qian, Chengrui AU - Jiang, Changyu ID - 643 IS - 4 JF - Chinese Journal of Physiology SN - 03044920 TI - Effects of B vitamins overload on plasma insulin level and hydrogen peroxide generation in rats VL - 60 ER - TY - JOUR AB - Cauchy problems with SPDEs on the whole space are localized to Cauchy problems on a ball of radius R. This localization reduces various kinds of spatial approximation schemes to finite dimensional problems. The error is shown to be exponentially small. As an application, a numerical scheme is presented which combines the localization and the space and time discretization, and thus is fully implementable. AU - Gerencser, Mate AU - Gyöngy, István ID - 642 IS - 307 JF - Mathematics of Computation SN - 00255718 TI - Localization errors in solving stochastic partial differential equations in the whole space VL - 86 ER - TY - CONF AB - Markov decision processes (MDPs) are standard models for probabilistic systems with non-deterministic behaviours. Long-run average rewards provide a mathematically elegant formalism for expressing long term performance. Value iteration (VI) is one of the simplest and most efficient algorithmic approaches to MDPs with other properties, such as reachability objectives. Unfortunately, a naive extension of VI does not work for MDPs with long-run average rewards, as there is no known stopping criterion. In this work our contributions are threefold. (1) We refute a conjecture related to stopping criteria for MDPs with long-run average rewards. (2) We present two practical algorithms for MDPs with long-run average rewards based on VI. First, we show that a combination of applying VI locally for each maximal end-component (MEC) and VI for reachability objectives can provide approximation guarantees. Second, extending the above approach with a simulation-guided on-demand variant of VI, we present an anytime algorithm that is able to deal with very large models. (3) Finally, we present experimental results showing that our methods significantly outperform the standard approaches on several benchmarks. AU - Ashok, Pranav AU - Chatterjee, Krishnendu AU - Daca, Przemyslaw AU - Kretinsky, Jan AU - Meggendorfer, Tobias ED - Majumdar, Rupak ED - Kunčak, Viktor ID - 645 SN - 978-331963386-2 TI - Value iteration for long run average reward in markov decision processes VL - 10426 ER - TY - JOUR AB - An instance of the valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. We study, assuming that P 6= NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in f0;1g corresponds to ordinary CSPs, where one deals only with the feasibility issue, and there is no optimization. This case is the subject of the algebraic CSP dichotomy conjecture predicting for which constraint languages CSPs are tractable (i.e., solvable in polynomial time) and for which they are NP-hard. The case when all allowed functions take only finite values corresponds to a finitevalued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Živný. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e., the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs. AU - Kolmogorov, Vladimir AU - Krokhin, Andrei AU - Rolinek, Michal ID - 644 IS - 3 JF - SIAM Journal on Computing TI - The complexity of general-valued CSPs VL - 46 ER - TY - CONF AB - We present a novel convex relaxation and a corresponding inference algorithm for the non-binary discrete tomography problem, that is, reconstructing discrete-valued images from few linear measurements. In contrast to state of the art approaches that split the problem into a continuous reconstruction problem for the linear measurement constraints and a discrete labeling problem to enforce discrete-valued reconstructions, we propose a joint formulation that addresses both problems simultaneously, resulting in a tighter convex relaxation. For this purpose a constrained graphical model is set up and evaluated using a novel relaxation optimized by dual decomposition. We evaluate our approach experimentally and show superior solutions both mathematically (tighter relaxation) and experimentally in comparison to previously proposed relaxations. AU - Kuske, Jan AU - Swoboda, Paul AU - Petra, Stefanie ED - Lauze, François ED - Dong, Yiqiu ED - Bjorholm Dahl, Anders ID - 646 SN - 978-331958770-7 TI - A novel convex relaxation for non binary discrete tomography VL - 10302 ER - TY - CONF AB - Pseudoentropy has found a lot of important applications to cryptography and complexity theory. In this paper we focus on the foundational problem that has not been investigated so far, namely by how much pseudoentropy (the amount seen by computationally bounded attackers) differs from its information-theoretic counterpart (seen by unbounded observers), given certain limits on attacker’s computational power? We provide the following answer for HILL pseudoentropy, which exhibits a threshold behavior around the size exponential in the entropy amount:– If the attacker size (s) and advantage () satisfy s (formula presented) where k is the claimed amount of pseudoentropy, then the pseudoentropy boils down to the information-theoretic smooth entropy. – If s (formula presented) then pseudoentropy could be arbitrarily bigger than the information-theoretic smooth entropy. Besides answering the posted question, we show an elegant application of our result to the complexity theory, namely that it implies the clas-sical result on the existence of functions hard to approximate (due to Pippenger). In our approach we utilize non-constructive techniques: the duality of linear programming and the probabilistic method. AU - Skórski, Maciej ED - Jäger, Gerhard ED - Steila, Silvia ID - 648 SN - 978-331955910-0 TI - On the complexity of breaking pseudoentropy VL - 10185 ER - TY - CHAP AB - We give a short overview on a recently developed notion of Ricci curvature for discrete spaces. This notion relies on geodesic convexity properties of the relative entropy along geodesics in the space of probability densities, for a metric which is similar to (but different from) the 2-Wasserstein metric. The theory can be considered as a discrete counterpart to the theory of Ricci curvature for geodesic measure spaces developed by Lott–Sturm–Villani. AU - Maas, Jan ED - Najman, Laurent ED - Romon, Pascal ID - 649 SN - 978-3-319-58001-2 T2 - Modern Approaches to Discrete Curvature TI - Entropic Ricci curvature for discrete spaces VL - 2184 ER - TY - CONF AB - In this work we present a short and unified proof for the Strong and Weak Regularity Lemma, based on the cryptographic tech-nique called low-complexity approximations. In short, both problems reduce to a task of finding constructively an approximation for a certain target function under a class of distinguishers (test functions), where dis-tinguishers are combinations of simple rectangle-indicators. In our case these approximations can be learned by a simple iterative procedure, which yields a unified and simple proof, achieving for any graph with density d and any approximation parameter the partition size. The novelty in our proof is: (a) a simple approach which yields both strong and weaker variant, and (b) improvements when d = o(1). At an abstract level, our proof can be seen a refinement and simplification of the “analytic” proof given by Lovasz and Szegedy. AU - Skórski, Maciej ED - Jäger, Gerhard ED - Steila, Silvia ID - 650 SN - 03029743 TI - A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds VL - 10185 ER - TY - CONF AB - Graph games with omega-regular winning conditions provide a mathematical framework to analyze a wide range of problems in the analysis of reactive systems and programs (such as the synthesis of reactive systems, program repair, and the verification of branching time properties). Parity conditions are canonical forms to specify omega-regular winning conditions. Graph games with parity conditions are equivalent to mu-calculus model checking, and thus a very important algorithmic problem. Symbolic algorithms are of great significance because they provide scalable algorithms for the analysis of large finite-state systems, as well as algorithms for the analysis of infinite-state systems with finite quotient. A set-based symbolic algorithm uses the basic set operations and the one-step predecessor operators. We consider graph games with n vertices and parity conditions with c priorities (equivalently, a mu-calculus formula with c alternations of least and greatest fixed points). While many explicit algorithms exist for graph games with parity conditions, for set-based symbolic algorithms there are only two algorithms (notice that we use space to refer to the number of sets stored by a symbolic algorithm): (a) the basic algorithm that requires O(n^c) symbolic operations and linear space; and (b) an improved algorithm that requires O(n^{c/2+1}) symbolic operations but also O(n^{c/2+1}) space (i.e., exponential space). In this work we present two set-based symbolic algorithms for parity games: (a) our first algorithm requires O(n^{c/2+1}) symbolic operations and only requires linear space; and (b) developing on our first algorithm, we present an algorithm that requires O(n^{c/3+1}) symbolic operations and only linear space. We also present the first linear space set-based symbolic algorithm for parity games that requires at most a sub-exponential number of symbolic operations. AU - Chatterjee, Krishnendu AU - Dvorák, Wolfgang AU - Henzinger, Monika H AU - Loitzenbauer, Veronika ID - 6519 TI - Improved set-based symbolic algorithms for parity games VL - 82 ER - TY - CONF AB - A (possibly degenerate) drawing of a graph G in the plane is approximable by an embedding if it can be turned into an embedding by an arbitrarily small perturbation. We show that testing, whether a drawing of a planar graph G in the plane is approximable by an embedding, can be carried out in polynomial time, if a desired embedding of G belongs to a fixed isotopy class, i.e., the rotation system (or equivalently the faces) of the embedding of G and the choice of outer face are fixed. In other words, we show that c-planarity with embedded pipes is tractable for graphs with fixed embeddings. To the best of our knowledge an analogous result was previously known essentially only when G is a cycle. AU - Fulek, Radoslav ID - 6517 TI - Embedding graphs into embedded graphs VL - 92 ER - TY - CONF AB - We present an approach that enables robots to self-organize their sensorimotor behavior from scratch without providing specific information about neither the robot nor its environment. This is achieved by a simple neural control law that increases the consistency between external sensor dynamics and internal neural dynamics of the utterly simple controller. In this way, the embodiment and the agent-environment coupling are the only source of individual development. We show how an anthropomorphic tendon driven arm-shoulder system develops different behaviors depending on that coupling. For instance: Given a bottle half-filled with water, the arm starts to shake it, driven by the physical response of the water. When attaching a brush, the arm can be manipulated into wiping a table, and when connected to a revolvable wheel it finds out how to rotate it. Thus, the robot may be said to discover the affordances of the world. When allowing two (simulated) humanoid robots to interact physically, they engage into a joint behavior development leading to, for instance, spontaneous cooperation. More social effects are observed if the robots can visually perceive each other. Although, as an observer, it is tempting to attribute an apparent intentionality, there is nothing of the kind put in. As a conclusion, we argue that emergent behavior may be much less rooted in explicit intentions, internal motivations, or specific reward systems than is commonly believed. AU - Der, Ralf AU - Martius, Georg S ID - 652 SN - 978-150905069-7 TI - Dynamical self consistency leads to behavioral development and emergent social interactions in robots ER - TY - JOUR AB - Superhydrophobic surfaces reduce the frictional drag between water and solid materials, but this effect is often temporary. The realization of sustained drag reduction has applications for water vehicles and pipeline flows. AU - Hof, Björn ID - 651 IS - 7636 JF - Nature SN - 00280836 TI - Fluid dynamics: Water flows out of touch VL - 541 ER - TY - JOUR AB - The extent of heterogeneity among driver gene mutations present in naturally occurring metastases - that is, treatment-naive metastatic disease - is largely unknown. To address this issue, we carried out 60× whole-genome sequencing of 26 metastases from four patients with pancreatic cancer. We found that identical mutations in known driver genes were present in every metastatic lesion for each patient studied. Passenger gene mutations, which do not have known or predicted functional consequences, accounted for all intratumoral heterogeneity. Even with respect to these passenger mutations, our analysis suggests that the genetic similarity among the founding cells of metastases was higher than that expected for any two cells randomly taken from a normal tissue. The uniformity of known driver gene mutations among metastases in the same patient has critical and encouraging implications for the success of future targeted therapies in advanced-stage disease. AU - Makohon Moore, Alvin AU - Zhang, Ming AU - Reiter, Johannes AU - Božić, Ivana AU - Allen, Benjamin AU - Kundu, Deepanjan AU - Chatterjee, Krishnendu AU - Wong, Fay AU - Jiao, Yuchen AU - Kohutek, Zachary AU - Hong, Jungeui AU - Attiyeh, Marc AU - Javier, Breanna AU - Wood, Laura AU - Hruban, Ralph AU - Nowak, Martin AU - Papadopoulos, Nickolas AU - Kinzler, Kenneth AU - Vogelstein, Bert AU - Iacobuzio Donahue, Christine ID - 653 IS - 3 JF - Nature Genetics SN - 10614036 TI - Limited heterogeneity of known driver gene mutations among the metastases of individual patients with pancreatic cancer VL - 49 ER - TY - CONF AB - A memory-hard function (MHF) ƒn with parameter n can be computed in sequential time and space n. Simultaneously, a high amortized parallel area-time complexity (aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate at which an adversary (using a custom computational device) can evaluate a security sensitive function that still occasionally needs to be evaluated by honest users (using an off-the-shelf general purpose device). The most prevalent examples of such sensitive functions are Key Derivation Functions (KDFs) and password hashing algorithms where rate limits help mitigate off-line dictionary attacks. As the honest users' inputs to these functions are often (low-entropy) passwords special attention is given to a class of side-channel resistant MHFs called iMHFs. Essentially all iMHFs can be viewed as some mode of operation (making n calls to some round function) given by a directed acyclic graph (DAG) with very low indegree. Recently, a combinatorial property of a DAG has been identified (called "depth-robustness") which results in good provable security for an iMHF based on that DAG. Depth-robust DAGs have also proven useful in other cryptographic applications. Unfortunately, up till now, all known very depth-robust DAGs are impractically complicated and little is known about their exact (i.e. non-asymptotic) depth-robustness both in theory and in practice. In this work we build and analyze (both formally and empirically) several exceedingly simple and efficient to navigate practical DAGs for use in iMHFs and other applications. For each DAG we: *Prove that their depth-robustness is asymptotically maximal. *Prove bounds of at least 3 orders of magnitude better on their exact depth-robustness compared to known bounds for other practical iMHF. *Implement and empirically evaluate their depth-robustness and aAT against a variety of state-of-the art (and several new) depth-reduction and low aAT attacks. We find that, against all attacks, the new DAGs perform significantly better in practice than Argon2i, the most widely deployed iMHF in practice. Along the way we also improve the best known empirical attacks on the aAT of Argon2i by implementing and testing several heuristic versions of a (hitherto purely theoretical) depth-reduction attack. Finally, we demonstrate practicality of our constructions by modifying the Argon2i code base to use one of the new high aAT DAGs. Experimental benchmarks on a standard off-the-shelf CPU show that the new modifications do not adversely affect the impressive throughput of Argon2i (despite seemingly enjoying significantly higher aAT). AU - Alwen, Joel F AU - Blocki, Jeremiah AU - Harsha, Ben ID - 6527 SN - 9781450349468 T2 - Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security TI - Practical graphs for optimal side-channel resistant memory-hard functions ER - TY - JOUR AB - In November 2016, developmental biologists, synthetic biologists and engineers gathered in Paris for a meeting called ‘Engineering the embryo’. The participants shared an interest in exploring how synthetic systems can reveal new principles of embryonic development, and how the in vitro manipulation and modeling of development using stem cells can be used to integrate ideas and expertise from physics, developmental biology and tissue engineering. As we review here, the conference pinpointed some of the challenges arising at the intersection of these fields, along with great enthusiasm for finding new approaches and collaborations. AU - Kicheva, Anna AU - Rivron, Nicolas ID - 654 IS - 5 JF - Development SN - 09501991 TI - Creating to understand – developmental biology meets engineering in Paris VL - 144 ER - TY - CONF AB - This paper studies the complexity of estimating Rényi divergences of discrete distributions: p observed from samples and the baseline distribution q known a priori. Extending the results of Acharya et al. (SODA'15) on estimating Rényi entropy, we present improved estimation techniques together with upper and lower bounds on the sample complexity. We show that, contrarily to estimating Rényi entropy where a sublinear (in the alphabet size) number of samples suffices, the sample complexity is heavily dependent on events occurring unlikely in q, and is unbounded in general (no matter what an estimation technique is used). For any divergence of integer order bigger than 1, we provide upper and lower bounds on the number of samples dependent on probabilities of p and q (the lower bounds hold for non-integer orders as well). We conclude that the worst-case sample complexity is polynomial in the alphabet size if and only if the probabilities of q are non-negligible. This gives theoretical insights into heuristics used in the applied literature to handle numerical instability, which occurs for small probabilities of q. Our result shows that they should be handled with care not only because of numerical issues, but also because of a blow up in the sample complexity. AU - Skórski, Maciej ID - 6526 SN - 9781509040964 T2 - 2017 IEEE International Symposium on Information Theory (ISIT) TI - On the complexity of estimating Rènyi divergences ER - TY - JOUR AB - The bacterial flagellum is a self-assembling nanomachine. The external flagellar filament, several times longer than a bacterial cell body, is made of a few tens of thousands subunits of a single protein: flagellin. A fundamental problem concerns the molecular mechanism of how the flagellum grows outside the cell, where no discernible energy source is available. Here, we monitored the dynamic assembly of individual flagella using in situ labelling and real-time immunostaining of elongating flagellar filaments. We report that the rate of flagellum growth, initially ~1,700 amino acids per second, decreases with length and that the previously proposed chain mechanism does not contribute to the filament elongation dynamics. Inhibition of the proton motive force-dependent export apparatus revealed a major contribution of substrate injection in driving filament elongation. The combination of experimental and mathematical evidence demonstrates that a simple, injection-diffusion mechanism controls bacterial flagella growth outside the cell. AU - Renault, Thibaud AU - Abraham, Anthony AU - Bergmiller, Tobias AU - Paradis, Guillaume AU - Rainville, Simon AU - Charpentier, Emmanuelle AU - Guet, Calin C AU - Tu, Yuhai AU - Namba, Keiichi AU - Keener, James AU - Minamino, Tohru AU - Erhardt, Marc ID - 655 JF - eLife SN - 2050084X TI - Bacterial flagella grow through an injection diffusion mechanism VL - 6 ER - TY - JOUR AB - Plant organs are typically organized into three main tissue layers. The middle ground tissue layer comprises the majority of the plant body and serves a wide range of functions, including photosynthesis, selective nutrient uptake and storage, and gravity sensing. Ground tissue patterning and maintenance in Arabidopsis are controlled by a well-established gene network revolving around the key regulator SHORT-ROOT (SHR). In contrast, it is completely unknown how ground tissue identity is first specified from totipotent precursor cells in the embryo. The plant signaling molecule auxin, acting through AUXIN RESPONSE FACTOR (ARF) transcription factors, is critical for embryo patterning. The auxin effector ARF5/MONOPTEROS (MP) acts both cell-autonomously and noncell-autonomously to control embryonic vascular tissue formation and root initiation, respectively. Here we show that auxin response and ARF activity cell-autonomously control the asymmetric division of the first ground tissue cells. By identifying embryonic target genes, we show that MP transcriptionally initiates the ground tissue lineage and acts upstream of the regulatory network that controls ground tissue patterning and maintenance. Strikingly, whereas the SHR network depends on MP, this MP function is, at least in part, SHR independent. Our study therefore identifies auxin response as a regulator of ground tissue specification in the embryonic root, and reveals that ground tissue initiation and maintenance use different regulators and mechanisms. Moreover, our data provide a framework for the simultaneous formation of multiple cell types by the same transcriptional regulator. AU - Möller, Barbara AU - Ten Hove, Colette AU - Xiang, Daoquan AU - Williams, Nerys AU - López, Lorena AU - Yoshida, Saiko AU - Smit, Margot AU - Datla, Raju AU - Weijers, Dolf ID - 657 IS - 12 JF - PNAS SN - 00278424 TI - Auxin response cell autonomously controls ground tissue initiation in the early arabidopsis embryo VL - 114 ER -