TY - JOUR AB - We characterize absorption in finite idempotent algebras by means of Jónsson absorption and cube term blockers. As an application we show that it is decidable whether a given subset is an absorbing subuniverse of an algebra given by the tables of its basic operations. AU - Barto, Libor AU - Kazda, Alexandr ID - 1353 IS - 5 JF - International Journal of Algebra and Computation TI - Deciding absorption VL - 26 ER - TY - CONF AB - When aiming to seamlessly integrate a fluid simulation into a larger scenario (like an open ocean), careful attention must be paid to boundary conditions. In particular, one must implement special "non-reflecting" boundary conditions, which dissipate out-going waves as they exit the simulation. Unfortunately, the state of the art in non-reflecting boundary conditions (perfectly-matched layers, or PMLs) only permits trivially simple inflow/outflow conditions, so there is no reliable way to integrate a fluid simulation into a more complicated environment like a stormy ocean or a turbulent river. This paper introduces the first method for combining nonreflecting boundary conditions based on PMLs with inflow/outflow boundary conditions that vary arbitrarily throughout space and time. Our algorithm is a generalization of stateof- the-art mean-flow boundary conditions in the computational fluid dynamics literature, and it allows for seamless integration of a fluid simulation into much more complicated environments. Our method also opens the door for previously-unseen postprocess effects like retroactively changing the location of solid obstacles, and locally increasing the visual detail of a pre-existing simulation. AU - Bojsen-Hansen, Morten AU - Wojtan, Christopher J ID - 1363 IS - 4 TI - Generalized non-reflecting boundaries for fluid re-simulation VL - 35 ER - TY - CONF AB - We present a computational method for designing wire sculptures consisting of interlocking wires. Our method allows the computation of aesthetically pleasing structures that are structurally stable, efficiently fabricatable with a 2D wire bending machine, and assemblable without the need of additional connectors. Starting from a set of planar contours provided by the user, our method automatically tests for the feasibility of a design, determines a discrete ordering of wires at intersection points, and optimizes for the rest shape of the individual wires to maximize structural stability under frictional contact. In addition to their application to art, wire sculptures present an extremely efficient and fast alternative for low-fidelity rapid prototyping because manufacturing time and required material linearly scales with the physical size of objects. We demonstrate the effectiveness of our approach on a varied set of examples, all of which we fabricated. AU - Miguel Villalba, Eder AU - Lepoutre, Mathias AU - Bickel, Bernd ID - 1364 IS - 4 TI - Computational design of stable planar-rod structures VL - 35 ER - TY - CONF AB - We propose a novel surface-only technique for simulating incompressible, inviscid and uniform-density liquids with surface tension in three dimensions. The liquid surface is captured by a triangle mesh on which a Lagrangian velocity field is stored. Because advection of the velocity field may violate the incompressibility condition, we devise an orthogonal projection technique to remove the divergence while requiring the evaluation of only two boundary integrals. The forces of surface tension, gravity, and solid contact are all treated by a boundary element solve, allowing us to perform detailed simulations of a wide range of liquid phenomena, including waterbells, droplet and jet collisions, fluid chains, and crown splashes. AU - Da, Fang AU - Hahn, David AU - Batty, Christopher AU - Wojtan, Christopher J AU - Grinspun, Eitan ID - 1361 IS - 4 TI - Surface only liquids VL - 35 ER - TY - CONF AB - A memory-hard function (MHF) f is equipped with a space cost σ and time cost τ parameter such that repeatedly computing fσ,τ on an application specific integrated circuit (ASIC) is not economically advantageous relative to a general purpose computer. Technically we would like that any (generalized) circuit for evaluating an iMHF fσ,τ has area × time (AT) complexity at Θ(σ2 ∗ τ). A data-independent MHF (iMHF) has the added property that it can be computed with almost optimal memory and time complexity by an algorithm which accesses memory in a pattern independent of the input value. Such functions can be specified by fixing a directed acyclic graph (DAG) G on n = Θ(σ ∗ τ) nodes representing its computation graph. In this work we develop new tools for analyzing iMHFs. First we define and motivate a new complexity measure capturing the amount of energy (i.e. electricity) required to compute a function. We argue that, in practice, this measure is at least as important as the more traditional AT-complexity. Next we describe an algorithm A for repeatedly evaluating an iMHF based on an arbitrary DAG G. We upperbound both its energy and AT complexities per instance evaluated in terms of a certain combinatorial property of G. Next we instantiate our attack for several general classes of DAGs which include those underlying many of the most important iMHF candidates in the literature. In particular, we obtain the following results which hold for all choices of parameters σ and τ (and thread-count) such that n = σ ∗ τ. -The Catena-Dragonfly function of [FLW13] has AT and energy complexities O(n1.67). -The Catena-Butterfly function of [FLW13] has complexities is O(n1.67). -The Double-Buffer and the Linear functions of [CGBS16] both have complexities in O(n1.67). -The Argon2i function of [BDK15] (winner of the Password Hashing Competition [PHC]) has complexities O(n7/4 log(n)). -The Single-Buffer function of [CGBS16] has complexities O(n7/4 log(n)). -Any iMHF can be computed by an algorithm with complexities O(n2/ log1 −ε(n)) for all ε > 0. In particular when τ = 1 this shows that the goal of constructing an iMHF with AT-complexity Θ(σ2 ∗ τ ) is unachievable. Along the way we prove a lemma upper-bounding the depth-robustness of any DAG which may prove to be of independent interest. AU - Alwen, Joel F AU - Blocki, Jeremiah ID - 1365 TI - Efficiently computing data-independent memory-hard functions VL - 9815 ER - TY - CONF AB - We study the problem of devising provably secure PRNGs with input based on the sponge paradigm. Such constructions are very appealing, as efficient software/hardware implementations of SHA-3 can easily be translated into a PRNG in a nearly black-box way. The only existing sponge-based construction, proposed by Bertoni et al. (CHES 2010), fails to achieve the security notion of robustness recently considered by Dodis et al. (CCS 2013), for two reasons: (1) The construction is deterministic, and thus there are high-entropy input distributions on which the construction fails to extract random bits, and (2) The construction is not forward secure, and presented solutions aiming at restoring forward security have not been rigorously analyzed. We propose a seeded variant of Bertoni et al.’s PRNG with input which we prove secure in the sense of robustness, delivering in particular concrete security bounds. On the way, we make what we believe to be an important conceptual contribution, developing a variant of the security framework of Dodis et al. tailored at the ideal permutation model that captures PRNG security in settings where the weakly random inputs are provided from a large class of possible adversarial samplers which are also allowed to query the random permutation. As a further application of our techniques, we also present an efficient sponge-based key-derivation function (which can be instantiated from SHA-3 in a black-box fashion), which we also prove secure when fed with samples from permutation-dependent distributions. AU - Gazi, Peter AU - Tessaro, Stefano ID - 1366 TI - Provably robust sponge-based PRNGs and KDFs VL - 9665 ER - TY - JOUR AB - We apply the technique of Károly Bezdek and Daniel Bezdek to study billiard trajectories in convex bodies, when the length is measured with a (possibly asymmetric) norm. We prove a lower bound for the length of the shortest closed billiard trajectory, related to the non-symmetric Mahler problem. With this technique we are able to give short and elementary proofs to some known results. AU - Akopyan, Arseniy AU - Balitskiy, Alexey AU - Karasev, Roman AU - Sharipova, Anastasia ID - 1360 IS - 10 JF - Proceedings of the American Mathematical Society TI - Elementary approach to closed billiard trajectories in asymmetric normed spaces VL - 144 ER - TY - JOUR AB - Redirection of intercellular auxin fluxes via relocalization of the PIN-FORMED 3 (PIN3) and PIN7 auxin efflux carriers has been suggested to be necessary for the root gravitropic response. Cytokinins have also been proposed to play a role in controlling root gravitropism, but conclusive evidence is lacking. We present a detailed study of the dynamics of root bending early after gravistimulation, which revealed a delayed gravitropic response in transgenic lines with depleted endogenous cytokinins (Pro35S:AtCKX) and cytokinin signaling mutants. Pro35S:AtCKX lines, as well as a cytokinin receptor mutant ahk3, showed aberrations in the auxin response distribution in columella cells consistent with defects in the auxin transport machinery. Using in vivo real-time imaging of PIN3-GFP and PIN7-GFP in AtCKX3 overexpression and ahk3 backgrounds, we observed wild-type-like relocalization of PIN proteins in the columella early after gravistimulation, with gravity-induced relocalization of PIN7 faster than that of PIN3. Nonetheless, the cellular distribution of PIN3 and PIN7 and expression of PIN7 and the auxin influx carrier AUX1 was affected in AtCKX overexpression lines. Based on the retained cytokinin sensitivity in pin3 pin4 pin7 mutant, we propose the AUX1-mediated auxin transport rather than columella-located PIN proteins as a target of endogenous cytokinins in the control of root gravitropism. AU - Pernisová, Markéta AU - Prat, Tomas AU - Grones, Peter AU - Haruštiaková, Danka AU - Matonohova, Martina AU - Spíchal, Lukáš AU - Nodzyński, Tomasz AU - Friml, Jirí AU - Hejátko, Jan ID - 1372 IS - 2 JF - New Phytologist TI - Cytokinins influence root gravitropism via differential regulation of auxin transporter expression and localization in Arabidopsis VL - 212 ER - TY - CONF AB - We introduce a new loss function for the weakly-supervised training of semantic image segmentation models based on three guiding principles: to seed with weak localization cues, to expand objects based on the information about which classes can occur in an image, and to constrain the segmentations to coincide with object boundaries. We show experimentally that training a deep convolutional neural network using the proposed loss function leads to substantially better segmentations than previous state-of-the-art methods on the challenging PASCAL VOC 2012 dataset. We furthermore give insight into the working mechanism of our method by a detailed experimental study that illustrates how the segmentation quality is affected by each term of the proposed loss function as well as their combinations. AU - Kolesnikov, Alexander AU - Lampert, Christoph ID - 1369 TI - Seed, expand and constrain: Three principles for weakly-supervised image segmentation VL - 9908 ER - TY - JOUR AB - Superconductivity in heavy-fermion systems has an unconventional nature and is considered to originate from the universal features of the electronic structure. Here, the Anderson lattice model is studied by means of the full variational Gutzwiller wave function incorporating nonlocal effects of the on-site interaction. We show that the d-wave superconducting ground state can be driven solely by interelectronic correlations. The proposed microscopic mechanism leads to a multigap superconductivity with the dominant contribution due to f electrons and in the dx2−y2-wave channel. Our results rationalize several important observations for CeCoIn5. AU - Wysokiński, Marcin AU - Kaczmarczyk, Jan AU - Spałek, Jozef ID - 1368 IS - 2 JF - Physical Review B - Condensed Matter and Materials Physics TI - Correlation driven d wave superconductivity in Anderson lattice model: Two gaps VL - 94 ER - TY - JOUR AB - Living cells can maintain their internal states, react to changing environments, grow, differentiate, divide, etc. All these processes are tightly controlled by what can be called a regulatory program. The logic of the underlying control can sometimes be guessed at by examining the network of influences amongst genetic components. Some associated gene regulatory networks have been studied in prokaryotes and eukaryotes, unveiling various structural features ranging from broad distributions of out-degrees to recurrent "motifs", that is small subgraphs having a specific pattern of interactions. To understand what factors may be driving such structuring, a number of groups have introduced frameworks to model the dynamics of gene regulatory networks. In that context, we review here such in silico approaches and show how selection for phenotypes, i.e., network function, can shape network structure. AU - Martin, Olivier AU - Krzywicki, André AU - Zagórski, Marcin P ID - 1371 JF - Physics of Life Reviews TI - Drivers of structural features in gene regulatory networks: From biophysical constraints to biological function VL - 17 ER - TY - JOUR AB - We study coherent phonon oscillations and tunneling between two coupled nonlinear nanomechanical resonators. We show that the coupling between two nanomechanical resonators creates an effective phonon Josephson junction, which exhibits two different dynamical behaviors: Josephson oscillation (phonon-Rabi oscillation) and macroscopic self-trapping (phonon blockade). Self-trapping originates from mechanical nonlinearities, meaning that when the nonlinearity exceeds its critical value, the energy exchange between the two resonators is suppressed, and phonon Josephson oscillations between them are completely blocked. An effective classical Hamiltonian for the phonon Josephson junction is derived and its mean-field dynamics is studied in phase space. Finally, we study the phonon-phonon coherence quantified by the mean fringe visibility, and show that the interaction between the two resonators may lead to the loss of coherence in the phononic junction. AU - Barzanjeh, Shabir AU - Vitali, David ID - 1370 IS - 3 JF - Physical Review A - Atomic, Molecular, and Optical Physics TI - Phonon Josephson junction with nanomechanical resonators VL - 93 ER - TY - JOUR AU - Martin, Olivier AU - Zagórski, Marcin P ID - 1373 JF - Physics of Life Reviews TI - Network architectures and operating principles. Reply to comments on "Drivers of structural features in gene regulatory networks: From biophysical constraints to biological function" VL - 17 ER - TY - JOUR AB - We consider the problem of minimizing the continuous valued total variation subject to different unary terms on trees and propose fast direct algorithms based on dynamic programming to solve these problems. We treat both the convex and the nonconvex case and derive worst-case complexities that are equal to or better than existing methods. We show applications to total variation based two dimensional image processing and computer vision problems based on a Lagrangian decomposition approach. The resulting algorithms are very effcient, offer a high degree of parallelism, and come along with memory requirements which are only in the order of the number of image pixels. AU - Kolmogorov, Vladimir AU - Pock, Thomas AU - Rolinek, Michal ID - 1377 IS - 2 JF - SIAM Journal on Imaging Sciences TI - Total variation on a tree VL - 9 ER - TY - CONF AB - Motivated by Tverberg-type problems in topological combinatorics and by classical results about embeddings (maps without double points), we study the question whether a finite simplicial complex K can be mapped into double-struck Rd without higher-multiplicity intersections. We focus on conditions for the existence of almost r-embeddings, i.e., maps f : K → double-struck Rd such that f(σ1) ∩ ⋯ ∩ f(σr) = ∅ whenever σ1, ..., σr are pairwise disjoint simplices of K. Generalizing the classical Haefliger-Weber embeddability criterion, we show that a well-known necessary deleted product condition for the existence of almost r-embeddings is sufficient in a suitable r-metastable range of dimensions: If rd ≥ (r + 1) dim K + 3, then there exists an almost r-embedding K → double-struck Rd if and only if there exists an equivariant map (K)Δ r → Sr Sd(r-1)-1, where (K)Δ r is the deleted r-fold product of K, the target Sd(r-1)-1 is the sphere of dimension d(r - 1) - 1, and Sr is the symmetric group. This significantly extends one of the main results of our previous paper (which treated the special case where d = rk and dim K = (r - 1)k for some k ≥ 3), and settles an open question raised there. AU - Mabillard, Isaac AU - Wagner, Uli ID - 1381 TI - Eliminating higher-multiplicity intersections, II. The deleted product criterion in the r-metastable range VL - 51 ER - TY - JOUR AB - We consider higher-dimensional versions of Kannan and Lipton's Orbit Problem - determining whether a target vector space V may be reached from a starting point x under repeated applications of a linear transformation A. Answering two questions posed by Kannan and Lipton in the 1980s, we show that when V has dimension one, this problem is solvable in polynomial time, and when V has dimension two or three, the problem is in NPRP. AU - Chonev, Ventsislav K AU - Ouaknine, Joël AU - Worrell, James ID - 1380 IS - 3 JF - Journal of the ACM TI - On the complexity of the orbit problem VL - 63 ER - TY - CONF AB - The continuous evolution of a wide variety of systems, including continous-time Markov chains and linear hybrid automata, can be described in terms of linear differential equations. In this paper we study the decision problem of whether the solution x(t) of a system of linear differential equations dx/dt = Ax reaches a target halfspace infinitely often. This recurrent reachability problem can equivalently be formulated as the following Infinite Zeros Problem: does a real-valued function f:R≥0 --> R satisfying a given linear differential equation have infinitely many zeros? Our main decidability result is that if the differential equation has order at most 7, then the Infinite Zeros Problem is decidable. On the other hand, we show that a decision procedure for the Infinite Zeros Problem at order 9 (and above) would entail a major breakthrough in Diophantine Approximation, specifically an algorithm for computing the Lagrange constants of arbitrary real algebraic numbers to arbitrary precision. AU - Chonev, Ventsislav K AU - Ouaknine, Joël AU - Worrell, James ID - 1389 T2 - LICS '16 TI - On recurrent reachability for continuous linear dynamical systems ER - TY - CONF AB - The goal of automatic program repair is to identify a set of syntactic changes that can turn a program that is incorrect with respect to a given specification into a correct one. Existing program repair techniques typically aim to find any program that meets the given specification. Such “best-effort” strategies can end up generating a program that is quite different from the original one. Novel techniques have been proposed to compute syntactically minimal program fixes, but the smallest syntactic fix to a program can still significantly alter the original program’s behaviour. We propose a new approach to program repair based on program distances, which can quantify changes not only to the program syntax but also to the program semantics. We call this the quantitative program repair problem where the “optimal” repair is derived using multiple distances. We implement a solution to the quantitative repair problem in a prototype tool called Qlose (Quantitatively close), using the program synthesizer Sketch. We evaluate the effectiveness of different distances in obtaining desirable repairs by evaluating Qlose on programs taken from educational tools such as CodeHunt and edX. AU - D'Antoni, Loris AU - Samanta, Roopsha AU - Singh, Rishabh ID - 1390 TI - QLOSE: Program repair with quantitative objectives VL - 9780 ER - TY - JOUR AB - The solution space of genome-scale models of cellular metabolism provides a map between physically viable flux configurations and cellular metabolic phenotypes described, at the most basic level, by the corresponding growth rates. By sampling the solution space of E. coliʼs metabolic network, we show that empirical growth rate distributions recently obtained in experiments at single-cell resolution can be explained in terms of a trade-off between the higher fitness of fast-growing phenotypes and the higher entropy of slow-growing ones. Based on this, we propose a minimal model for the evolution of a large bacterial population that captures this trade-off. The scaling relationships observed in experiments encode, in such frameworks, for the same distance from the maximum achievable growth rate, the same degree of growth rate maximization, and/or the same rate of phenotypic change. Being grounded on genome-scale metabolic network reconstructions, these results allow for multiple implications and extensions in spite of the underlying conceptual simplicity. AU - De Martino, Daniele AU - Capuani, Fabrizio AU - De Martino, Andrea ID - 1394 IS - 3 JF - Physical Biology TI - Growth against entropy in bacterial metabolism: the phenotypic trade-off behind empirical growth rate distributions in E. coli VL - 13 ER - TY - JOUR AB - Combining high-resolution level set surface tracking with lower resolution physics is an inexpensive method for achieving highly detailed liquid animations. Unfortunately, the inherent resolution mismatch introduces several types of disturbing visual artifacts. We identify the primary sources of these artifacts and present simple, efficient, and practical solutions to address them. First, we propose an unconditionally stable filtering method that selectively removes sub-grid surface artifacts not seen by the fluid physics, while preserving fine detail in dynamic splashing regions. It provides comparable results to recent error-correction techniques at lower cost, without substepping, and with better scaling behavior. Second, we show how a modified narrow-band scheme can ensure accurate free surface boundary conditions in the presence of large resolution mismatches. Our scheme preserves the efficiency of the narrow-band methodology, while eliminating objectionable stairstep artifacts observed in prior work. Third, we demonstrate that the use of linear interpolation of velocity during advection of the high-resolution level set surface is responsible for visible grid-aligned kinks; we therefore advocate higher-order velocity interpolation, and show that it dramatically reduces this artifact. While these three contributions are orthogonal, our results demonstrate that taken together they efficiently address the dominant sources of visual artifacts arising with high-resolution embedded liquid surfaces; the proposed approach offers improved visual quality, a straightforward implementation, and substantially greater scalability than competing methods. AU - Goldade, Ryan AU - Batty, Christopher AU - Wojtan, Christopher J ID - 1412 IS - 2 JF - Computer Graphics Forum TI - A practical method for high-resolution embedded liquid surfaces VL - 35 ER - TY - JOUR AB - The pollen grains arise after meiosis of pollen mother cells within the anthers. A series of complex structural changes follows, generating mature pollen grains capable of performing the double fertilization of the female megasporophyte. Several signaling molecules, including hormones and lipids, have been involved in the regulation and appropriate control of pollen development. Phosphatidylinositol 4-phophate 5-kinases (PIP5K), which catalyze the biosynthesis of the phosphoinositide PtdIns(4,5)P2, are important for tip polar growth of root hairs and pollen tubes, embryo development, vegetative plant growth, and responses to the environment. Here, we report a role of PIP5Ks during microgametogenesis. PIP5K1 and PIP5K2 are expressed during early stages of pollen development and their transcriptional activity respond to auxin in pollen grains. Early male gametophytic lethality to certain grade was observed in both pip5k1-/- and pip5k2-/- single mutants. The number of pip5k mutant alleles is directly related to the frequency of aborted pollen grains suggesting the two genes are involved in the same function. Indeed PIP5K1 and PIP5K2 are functionally redundant since homozygous double mutants did not render viable pollen grains. The loss of function of PIP5K1 and PIP5K2results in defects in vacuole morphology in pollen at the later stages and epidermal root cells. Our results show that PIP5K1, PIP5K2 and phosphoinositide signaling are important cues for early developmental stages and vacuole formation during microgametogenesis. AU - Ugalde, José AU - Rodríguez Furlán, Cecilia AU - De Rycke, Riet AU - Norambuena, Lorena AU - Friml, Jirí AU - León, Gabriel AU - Tejos, Ricardo ID - 1410 JF - Plant Science TI - Phosphatidylinositol 4-phosphate 5-kinases 1 and 2 are involved in the regulation of vacuole morphology during Arabidopsis thaliana pollen development VL - 250 ER - TY - JOUR AU - Abbott, Richard AU - Barton, Nicholas H AU - Good, Jeffrey ID - 1409 IS - 11 JF - Molecular Ecology TI - Genomics of hybridization and its evolutionary consequences VL - 25 ER - TY - JOUR AB - This paper generalizes the well-known Diffusion Curves Images (DCI), which are composed of a set of Bezier curves with colors specified on either side. These colors are diffused as Laplace functions over the image domain, which results in smooth color gradients interrupted by the Bezier curves. Our new formulation allows for more color control away from the boundary, providing a similar expressive power as recent Bilaplace image models without introducing associated issues and computational costs. The new model is based on a special Laplace function blending and a new edge blur formulation. We demonstrate that given some user-defined boundary curves over an input raster image, fitting colors and edge blur from the image to the new model and subsequent editing and animation is equally convenient as with DCIs. Numerous examples and comparisons to DCIs are presented. AU - Jeschke, Stefan ID - 1413 IS - 2 JF - Computer Graphics Forum TI - Generalized diffusion curves: An improved vector representation for smooth-shaded images VL - 35 ER - TY - JOUR AB - In this paper, we present a method to model hyperelasticity that is well suited for representing the nonlinearity of real-world objects, as well as for estimating it from deformation examples. Previous approaches suffer several limitations, such as lack of integrability of elastic forces, failure to enforce energy convexity, lack of robustness of parameter estimation, or difficulty to model cross-modal effects. Our method avoids these problems by relying on a general energy-based definition of elastic properties. The accuracy of the resulting elastic model is maximized by defining an additive model of separable energy terms, which allow progressive parameter estimation. In addition, our method supports efficient modeling of extreme nonlinearities thanks to energy-limiting constraints. We combine our energy-based model with an optimization method to estimate model parameters from force-deformation examples, and we show successful modeling of diverse deformable objects, including cloth, human finger skin, and internal human anatomy in a medical imaging application. AU - Miguel Villalba, Eder AU - Miraut, David AU - Otaduy, Miguel ID - 1414 IS - 2 JF - Computer Graphics Forum TI - Modeling and estimation of energy-based hyperelastic objects VL - 35 ER - TY - JOUR AB - Plant development mediated by the phytohormone auxin depends on tightly controlled cellular auxin levels at its target tissue that are largely established by intercellular and intracellular auxin transport mediated by PIN auxin transporters. Among the eight members of the Arabidopsis PIN family, PIN6 is the least characterized candidate. In this study we generated functional, fluorescent protein-tagged PIN6 proteins and performed comprehensive analysis of their subcellular localization and also performed a detailed functional characterization of PIN6 and its developmental roles. The localization study of PIN6 revealed a dual localization at the plasma membrane (PM) and endoplasmic reticulum (ER). Transport and metabolic profiling assays in cultured cells and Arabidopsis strongly suggest that PIN6 mediates both auxin transport across the PM and intracellular auxin homeostasis, including the regulation of free auxin and auxin conjugates levels. As evidenced by the loss- and gain-of-function analysis, the complex function of PIN6 in auxin transport and homeostasis is required for auxin distribution during lateral and adventitious root organogenesis and for progression of these developmental processes. These results illustrate a unique position of PIN6 within the family of PIN auxin transporters and further add complexity to the developmentally crucial process of auxin transport. AU - Simon, Sibu AU - Skůpa, Petr AU - Viaene, Tom AU - Zwiewka, Marta AU - Tejos, Ricardo AU - Klíma, Petr AU - Čarná, Mária AU - Rolčík, Jakub AU - De Rycke, Riet AU - Moreno, Ignacio AU - Dobrev, Petre AU - Orellana, Ariel AU - Zažímalová, Eva AU - Friml, Jirí ID - 1417 IS - 1 JF - New Phytologist TI - PIN6 auxin transporter at endoplasmic reticulum and plasma membrane mediates auxin homeostasis and organogenesis in Arabidopsis VL - 211 ER - TY - JOUR AB - The Fluid Implicit Particle method (FLIP) for liquid simulations uses particles to reduce numerical dissipation and provide important visual cues for events like complex splashes and small-scale features near the liquid surface. Unfortunately, FLIP simulations can be computationally expensive, because they require a dense sampling of particles to fill the entire liquid volume. Furthermore, the vast majority of these FLIP particles contribute nothing to the fluid's visual appearance, especially for larger volumes of liquid. We present a method that only uses FLIP particles within a narrow band of the liquid surface, while efficiently representing the remaining inner volume on a regular grid. We show that a naïve realization of this idea introduces unstable and uncontrollable energy fluctuations, and we propose a novel coupling scheme between FLIP particles and regular grid which overcomes this problem. Our method drastically reduces the particle count and simulation times while yielding results that are nearly indistinguishable from regular FLIP simulations. Our approach is easy to integrate into any existing FLIP implementation. AU - Ferstl, Florian AU - Ando, Ryoichi AU - Wojtan, Christopher J AU - Westermann, Rüdiger AU - Thuerey, Nils ID - 1415 IS - 2 JF - Computer Graphics Forum TI - Narrow band FLIP for liquid simulations VL - 35 ER - TY - JOUR AB - Anisotropic dipole-dipole interactions between ultracold dipolar fermions break the symmetry of the Fermi surface and thereby deform it. Here we demonstrate that such a Fermi surface deformation induces a topological phase transition - the so-called Lifshitz transition - in the regime accessible to present-day experiments. We describe the impact of the Lifshitz transition on observable quantities such as the Fermi surface topology, the density-density correlation function, and the excitation spectrum of the system. The Lifshitz transition in ultracold atoms can be controlled by tuning the dipole orientation and, in contrast to the transition studied in crystalline solids, is completely interaction driven. AU - Van Loon, Erik AU - Katsnelson, Mikhail AU - Chomaz, Lauriane AU - Lemeshko, Mikhail ID - 1416 IS - 19 JF - Physical Review B - Condensed Matter and Materials Physics TI - Interaction-driven Lifshitz transition with dipolar fermions in optical lattices VL - 93 ER - TY - JOUR AB - We study the superconducting phase of the Hubbard model using the Gutzwiller variational wave function (GWF) and the recently proposed diagrammatic expansion technique (DE-GWF). The DE-GWF method works on the level of the full GWF and in the thermodynamic limit. Here, we consider a finite-size system to study the accuracy of the results as a function of the system size (which is practically unrestricted). We show that the finite-size scaling used, e.g. in the variational Monte Carlo method can lead to significant, uncontrolled errors. The presented research is the first step towards applying the DE-GWF method in studies of inhomogeneous situations, including systems with impurities, defects, inhomogeneous phases, or disorder. AU - Tomski, Andrzej AU - Kaczmarczyk, Jan ID - 1419 IS - 17 JF - Journal of Physics: Condensed Matter TI - Gutzwiller wave function for finite systems: Superconductivity in the Hubbard model VL - 28 ER - TY - JOUR AB - Changes in gene expression are an important mode of evolution; however, the proximate mechanism of these changes is poorly understood. In particular, little is known about the effects of mutations within cis binding sites for transcription factors, or the nature of epistatic interactions between these mutations. Here, we tested the effects of single and double mutants in two cis binding sites involved in the transcriptional regulation of the Escherichia coli araBAD operon, a component of arabinose metabolism, using a synthetic system. This system decouples transcriptional control from any posttranslational effects on fitness, allowing a precise estimate of the effect of single and double mutations, and hence epistasis, on gene expression. We found that epistatic interactions between mutations in the araBAD cis-regulatory element are common, and that the predominant form of epistasis is negative. The magnitude of the interactions depended on whether the mutations are located in the same or in different operator sites. Importantly, these epistatic interactions were dependent on the presence of arabinose, a native inducer of the araBAD operon in vivo, with some interactions changing in sign (e.g., from negative to positive) in its presence. This study thus reveals that mutations in even relatively simple cis-regulatory elements interact in complex ways such that selection on the level of gene expression in one environment might perturb regulation in the other environment in an unpredictable and uncorrelated manner. AU - Lagator, Mato AU - Igler, Claudia AU - Moreno, Anaisa AU - Guet, Calin C AU - Bollback, Jonathan P ID - 1427 IS - 3 JF - Molecular Biology and Evolution TI - Epistatic interactions in the arabinose cis-regulatory element VL - 33 ER - TY - CONF AB - We report on a mathematically rigorous analysis of the superfluid properties of a Bose- Einstein condensate in the many-body ground state of a one-dimensional model of interacting bosons in a random potential. AU - Könenberg, Martin AU - Moser, Thomas AU - Seiringer, Robert AU - Yngvason, Jakob ID - 1428 IS - 1 T2 - Journal of Physics: Conference Series TI - Superfluidity and BEC in a Model of Interacting Bosons in a Random Potential VL - 691 ER - TY - JOUR AB - Brood parasites exploit their host in order to increase their own fitness. Typically, this results in an arms race between parasite trickery and host defence. Thus, it is puzzling to observe hosts that accept parasitism without any resistance. The ‘mafia’ hypothesis suggests that these hosts accept parasitism to avoid retaliation. Retaliation has been shown to evolve when the hosts condition their response to mafia parasites, who use depredation as a targeted response to rejection. However, it is unclear if acceptance would also emerge when ‘farming’ parasites are present in the population. Farming parasites use depredation to synchronize the timing with the host, destroying mature clutches to force the host to re-nest. Herein, we develop an evolutionary model to analyse the interaction between depredatory parasites and their hosts. We show that coevolutionary cycles between farmers and mafia can still induce host acceptance of brood parasites. However, this equilibrium is unstable and in the long-run the dynamics of this host–parasite interaction exhibits strong oscillations: when farmers are the majority, accepters conditional to mafia (the host will reject first and only accept after retaliation by the parasite) have a higher fitness than unconditional accepters (the host always accepts parasitism). This leads to an increase in mafia parasites’ fitness and in turn induce an optimal environment for accepter hosts. AU - Chakra, Maria AU - Hilbe, Christian AU - Traulsen, Arne ID - 1426 IS - 5 JF - Royal Society Open Science TI - Coevolutionary interactions between farmers and mafia induce host acceptance of avian brood parasites VL - 3 ER - TY - JOUR AB - Direct reciprocity is a mechanism for the evolution of cooperation based on repeated interactions. When individuals meet repeatedly, they can use conditional strategies to enforce cooperative outcomes that would not be feasible in one-shot social dilemmas. Direct reciprocity requires that individuals keep track of their past interactions and find the right response. However, there are natural bounds on strategic complexity: Humans find it difficult to remember past interactions accurately, especially over long timespans. Given these limitations, it is natural to ask how complex strategies need to be for cooperation to evolve. Here, we study stochastic evolutionary game dynamics in finite populations to systematically compare the evolutionary performance of reactive strategies, which only respond to the co-player's previous move, and memory-one strategies, which take into account the own and the co-player's previous move. In both cases, we compare deterministic strategy and stochastic strategy spaces. For reactive strategies and small costs, we find that stochasticity benefits cooperation, because it allows for generous-tit-for-tat. For memory one strategies and small costs, we find that stochasticity does not increase the propensity for cooperation, because the deterministic rule of win-stay, lose-shift works best. For memory one strategies and large costs, however, stochasticity can augment cooperation. AU - Baek, Seung AU - Jeong, Hyeongchai AU - Hilbe, Christian AU - Nowak, Martin ID - 1423 JF - Scientific Reports TI - Comparing reactive and memory-one strategies of direct reciprocity VL - 6 ER - TY - JOUR AB - We study the time-dependent Bogoliubov–de-Gennes equations for generic translation-invariant fermionic many-body systems. For initial states that are close to thermal equilibrium states at temperatures near the critical temperature, we show that the magnitude of the order parameter stays approximately constant in time and, in particular, does not follow a time-dependent Ginzburg–Landau equation, which is often employed as a phenomenological description and predicts a decay of the order parameter in time. The full non-linear structure of the equations is necessary to understand this behavior. AU - Frank, Rupert AU - Hainzl, Christian AU - Schlein, Benjamin AU - Seiringer, Robert ID - 1422 IS - 7 JF - Letters in Mathematical Physics TI - Incompatibility of time-dependent Bogoliubov–de-Gennes and Ginzburg–Landau equations VL - 106 ER - TY - CONF AB - Hybridization methods enable the analysis of hybrid automata with complex, nonlinear dynamics through a sound abstraction process. Complex dynamics are converted to simpler ones with added noise, and then analysis is done using a reachability method for the simpler dynamics. Several such recent approaches advocate that only "dynamic" hybridization techniquesi.e., those where the dynamics are abstracted on-The-fly during a reachability computation are effective. In this paper, we demonstrate this is not the case, and create static hybridization methods that are more scalable than earlier approaches. The main insight in our approach is that quick, numeric simulations can be used to guide the process, eliminating the need for an exponential number of hybridization domains. Transitions between domains are generally timetriggered, avoiding accumulated error from geometric intersections. We enhance our static technique by combining time-Triggered transitions with occasional space-Triggered transitions, and demonstrate the benefits of the combined approach in what we call mixed-Triggered hybridization. Finally, error modes are inserted to confirm that the reachable states stay within the hybridized regions. The developed techniques can scale to higher dimensions than previous static approaches, while enabling the parallelization of the main performance bottleneck for many dynamic hybridization approaches: The nonlinear optimization required for sound dynamics abstraction. We implement our method as a model transformation pass in the HYST tool, and perform reachability analysis and evaluation using an unmodified version of SpaceEx on nonlinear models with up to six dimensions. AU - Bak, Stanley AU - Bogomolov, Sergiy AU - Henzinger, Thomas A AU - Johnson, Taylor AU - Prakash, Pradyot ID - 1421 TI - Scalable static hybridization methods for analysis of nonlinear systems ER - TY - JOUR AB - Selection, mutation, and random drift affect the dynamics of allele frequencies and consequently of quantitative traits. While the macroscopic dynamics of quantitative traits can be measured, the underlying allele frequencies are typically unobserved. Can we understand how the macroscopic observables evolve without following these microscopic processes? This problem has been studied previously by analogy with statistical mechanics: the allele frequency distribution at each time point is approximated by the stationary form, which maximizes entropy. We explore the limitations of this method when mutation is small (4Nμ < 1) so that populations are typically close to fixation, and we extend the theory in this regime to account for changes in mutation strength. We consider a single diallelic locus either under directional selection or with overdominance and then generalize to multiple unlinked biallelic loci with unequal effects. We find that the maximum-entropy approximation is remarkably accurate, even when mutation and selection change rapidly. AU - Bod'ová, Katarína AU - Tkacik, Gasper AU - Barton, Nicholas H ID - 1420 IS - 4 JF - Genetics TI - A general approximation for the dynamics of quantitative traits VL - 202 ER - TY - JOUR AB - Solitons are localized waves formed by a balance of focusing and defocusing effects. These nonlinear waves exist in diverse forms of matter yet exhibit similar properties including stability, periodic recurrence and particle-like trajectories. One important property is soliton fission, a process by which an energetic higher-order soliton breaks apart due to dispersive or nonlinear perturbations. Here we demonstrate through both experiment and theory that nonlinear photocarrier generation can induce soliton fission. Using near-field measurements, we directly observe the nonlinear spatial and temporal evolution of optical pulses in situ in a nanophotonic semiconductor waveguide. We develop an analytic formalism describing the free-carrier dispersion (FCD) perturbation and show the experiment exceeds the minimum threshold by an order of magnitude. We confirm these observations with a numerical nonlinear Schrödinger equation model. These results provide a fundamental explanation and physical scaling of optical pulse evolution in free-carrier media and could enable improved supercontinuum sources in gas based and integrated semiconductor waveguides. AU - Husko, Chad AU - Wulf, Matthias AU - Lefrançois, Simon AU - Combrié, Sylvain AU - Lehoucq, Gaëlle AU - De Rossi, Alfredo AU - Eggleton, Benjamin AU - Kuipers, Laurens ID - 1429 JF - Nature Communications TI - Free-carrier-induced soliton fission unveiled by in situ measurements in nanophotonic waveguides VL - 7 ER - TY - JOUR AB - The rare socially parasitic butterfly Maculinea alcon occurs in two forms, which are characteristic of hygric or xeric habitats and which exploit different host plants and host ants. The status of these two forms has been the subject of considerable controversy. Populations of the two forms are usually spatially distinct, but at Răscruci in Romania both forms occur on the same site (syntopically). We examined the genetic differentiation between the two forms using eight microsatellite markers, and compared with a nearby hygric site, Şardu. Our results showed that while the two forms are strongly differentiated at Răscruci, it is the xeric form there that is most similar to the hygric form at Şardu, and Bayesian clustering algorithms suggest that these two populations have exchanged genes relatively recently. We found strong evidence for population substructuring, caused by high within host ant nest relatedness, indicating very limited dispersal of most ovipositing females, but not association with particular host ant species. Our results are consistent with the results of larger scale phylogeographic studies that suggest that the two forms represent local ecotypes specialising on different host plants, each with a distinct flowering phenology, providing a temporal rather than spatial barrier to gene flow. AU - Tartally, András AU - Kelager, Andreas AU - Fürst, Matthias AU - Nash, David ID - 1431 IS - 3 JF - PeerJ TI - Host plant use drives genetic differentiation in syntopic populations of Maculinea alcon VL - 2016 ER - TY - JOUR AB - We prove that the system of subordination equations, defining the free additive convolution of two probability measures, is stable away from the edges of the support and blow-up singularities by showing that the recent smoothness condition of Kargin is always satisfied. As an application, we consider the local spectral statistics of the random matrix ensemble A+UBU⁎A+UBU⁎, where U is a Haar distributed random unitary or orthogonal matrix, and A and B are deterministic matrices. In the bulk regime, we prove that the empirical spectral distribution of A+UBU⁎A+UBU⁎ concentrates around the free additive convolution of the spectral distributions of A and B on scales down to N−2/3N−2/3. AU - Bao, Zhigang AU - Erdös, László AU - Schnelli, Kevin ID - 1434 IS - 3 JF - Journal of Functional Analysis TI - Local stability of the free additive convolution VL - 271 ER - TY - JOUR AB - We study the time evolution of a system of N spinless fermions in R3 which interact through a pair potential, e.g., the Coulomb potential. We compare the dynamics given by the solution to Schrödinger's equation with the time-dependent Hartree-Fock approximation, and we give an estimate for the accuracy of this approximation in terms of the kinetic energy of the system. This leads, in turn, to bounds in terms of the initial total energy of the system. AU - Bach, Volker AU - Breteaux, Sébastien AU - Petrat, Sören P AU - Pickl, Peter AU - Tzaneteas, Tim ID - 1436 IS - 1 JF - Journal de Mathématiques Pures et Appliquées TI - Kinetic energy estimates for the accuracy of the time-dependent Hartree-Fock approximation with Coulomb interaction VL - 105 ER - TY - JOUR AB - ATP released from neurons and astrocytes during neuronal activity or under pathophysiological circumstances is able to influence information flow in neuronal circuits by activation of ionotropic P2X and metabotropic P2Y receptors and subsequent modulation of cellular excitability, synaptic strength, and plasticity. In the present paper we review cellular and network effects of P2Y receptors in the brain. We show that P2Y receptors inhibit the release of neurotransmitters, modulate voltage- and ligand-gated ion channels, and differentially influence the induction of synaptic plasticity in the prefrontal cortex, hippocampus, and cerebellum. The findings discussed here may explain how P2Y1 receptor activation during brain injury, hypoxia, inflammation, schizophrenia, or Alzheimer's disease leads to an impairment of cognitive processes. Hence, it is suggested that the blockade of P2Y1 receptors may have therapeutic potential against cognitive disturbances in these states. AU - Guzmán, José AU - Gerevich, Zoltan ID - 1435 JF - Neural Plasticity TI - P2Y receptors in synaptic transmission and plasticity: Therapeutic potential in cognitive dysfunction VL - 2016 ER - TY - CONF AB - Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. We introduce PSYNC, a domain specific language based on the Heard-Of model, which views asynchronous faulty systems as synchronous ones with an adversarial environment that simulates asynchrony and faults by dropping messages. We define a runtime system for PSYNC that efficiently executes on asynchronous networks. We formalize the relation between the runtime system and PSYNC in terms of observational refinement. The high-level lockstep abstraction introduced by PSYNC simplifies the design and implementation of fault-tolerant distributed algorithms and enables automated formal verification. We have implemented an embedding of PSYNC in the SCALA programming language with a runtime system for asynchronous networks. We show the applicability of PSYNC by implementing several important fault-tolerant distributed algorithms and we compare the implementation of consensus algorithms in PSYNC against implementations in other languages in terms of code size, runtime efficiency, and verification. AU - Dragoi, Cezara AU - Henzinger, Thomas A AU - Zufferey, Damien ID - 1439 TI - PSYNC: A partially synchronous language for fault-tolerant distributed algorithms VL - 20-22 ER - TY - JOUR AU - Janovjak, Harald L ID - 1440 IS - 2 JF - Structure TI - Light at the end of the protein: Crystal structure of a C-terminal light-sensing domain VL - 24 ER - TY - JOUR AB - The accuracy of interdisciplinarity measurements is directly related to the quality of the underlying bibliographic data. Existing indicators of interdisciplinarity are not capable of reflecting the inaccuracies introduced by incorrect and incomplete records because correct and complete bibliographic data can rarely be obtained. This is the case for the Rao–Stirling index, which cannot handle references that are not categorized into disciplinary fields. We introduce a method that addresses this problem. It extends the Rao–Stirling index to acknowledge missing data by calculating its interval of uncertainty using computational optimization. The evaluation of our method indicates that the uncertainty interval is not only useful for estimating the inaccuracy of interdisciplinarity measurements, but it also delivers slightly more accurate aggregated interdisciplinarity measurements than the Rao–Stirling index. AU - Calatrava Moreno, Maria AU - Auzinger, Thomas AU - Werthner, Hannes ID - 1446 IS - 1 JF - Scientometrics TI - On the uncertainty of interdisciplinarity measurements due to incomplete bibliographic data VL - 107 ER - TY - JOUR AB - We develop a new and systematic method for proving entropic Ricci curvature lower bounds for Markov chains on discrete sets. Using different methods, such bounds have recently been obtained in several examples (e.g., 1-dimensional birth and death chains, product chains, Bernoulli–Laplace models, and random transposition models). However, a general method to obtain discrete Ricci bounds had been lacking. Our method covers all of the examples above. In addition we obtain new Ricci curvature bounds for zero-range processes on the complete graph. The method is inspired by recent work of Caputo, Dai Pra and Posta on discrete functional inequalities. AU - Fathi, Max AU - Maas, Jan ID - 1448 IS - 3 JF - The Annals of Applied Probability TI - Entropic Ricci curvature bounds for discrete interacting systems VL - 26 ER - TY - JOUR AB - The dynamic assembly and disassembly of actin filaments is essential for the formation and transport of vesicles during endocytosis. In yeast, two types of actin structures, namely cortical patches and cytoplasmic cables, play a direct role in endocytosis, but how their interaction is regulated remains unclear. Here, we show that Srv2/CAP, an evolutionarily conserved actin regulator, is required for efficient endocytosis owing to its role in the formation of the actin patches that aid initial vesicle invagination and of the actin cables that these move along. Deletion of the SRV2 gene resulted in the appearance of aberrant fragmented actin cables that frequently moved past actin patches, the sites of endocytosis. We find that the C-terminal CARP domain of Srv2p is vitally important for the proper assembly of actin patches and cables; we also demonstrate that the N-terminal helical folded domain of Srv2 is required for its localization to actin patches, specifically to the ADP-actin rich region through an interaction with cofilin. These results demonstrate the in vivo roles of Srv2p in the regulation of the actin cytoskeleton during clathrin-mediated endocytosis AU - Toshima, Junko AU - Horikomi, Chika AU - Okada, Asuka AU - Hatori, Makiko AU - Nagano, Makoto AU - Masuda, Atsushi AU - Yamamoto, Wataru AU - Siekhaus, Daria E AU - Toshima, Jiro ID - 1476 IS - 2 JF - Journal of Cell Science TI - Srv2/CAP is required for polarized actin cable assembly and patch internalization during clathrin-mediated endocytosis VL - 129 ER - TY - JOUR AB - The actin cytoskeleton plays important roles in the formation and internalization of endocytic vesicles. In yeast, endocytic vesicles move towards early endosomes along actin cables, however, the molecular machinery regulating interaction between endocytic vesicles and actin cables is poorly understood. The Eps15-like protein Pan1p plays a key role in actin-mediated endocytosis and is negatively regulated by Ark1 and Prk1 kinases. Here we show that pan1 mutated to prevent phosphorylation at all 18 threonines, pan1-18TA, displayed almost the same endocytic defect as ark1Δ prk1Δ cells, and contained abnormal actin concentrations including several endocytic compartments. Early endosomes were highly localized in the actin concentrations and displayed movement along actin cables. The dephosphorylated form of Pan1p also caused stable associations between endocytic vesicles and actin cables, and between endocytic vesicles and endosomes. Thus Pan1 phosphorylation is part of a novel mechanism that regulates endocytic compartment interactions with each other and with actin cables. AU - Toshima, Junko AU - Furuya, Eri AU - Nagano, Makoto AU - Kanno, Chisa AU - Sakamoto, Yuta AU - Ebihara, Masashi AU - Siekhaus, Daria E AU - Toshima, Jiro ID - 1475 IS - February 2016 JF - eLife TI - Yeast Eps15-like endocytic protein Pan1p regulates the interaction between endocytic vesicles, endosomes and the actin cytoskeleton VL - 5 ER - TY - JOUR AB - We consider the Tonks-Girardeau gas subject to a random external potential. If the disorder is such that the underlying one-particle Hamiltonian displays localization (which is known to be generically the case), we show that there is exponential decay of correlations in the many-body eigenstates. Moreover, there is no Bose-Einstein condensation and no superfluidity, even at zero temperature. AU - Seiringer, Robert AU - Warzel, Simone ID - 1478 IS - 3 JF - New Journal of Physics TI - Decay of correlations and absence of superfluidity in the disordered Tonks-Girardeau gas VL - 18 ER - TY - JOUR AB - Exponential varieties arise from exponential families in statistics. These real algebraic varieties have strong positivity and convexity properties, familiar from toric varieties and their moment maps. Among them are varieties of inverses of symmetric matrices satisfying linear constraints. This class includes Gaussian graphical models. We develop a general theory of exponential varieties. These are derived from hyperbolic polynomials and their integral representations. We compare the multidegrees and ML degrees of the gradient map for hyperbolic polynomials. AU - Michałek, Mateusz AU - Sturmfels, Bernd AU - Uhler, Caroline AU - Zwiernik, Piotr ID - 1480 IS - 1 JF - Proceedings of the London Mathematical Society TI - Exponential varieties VL - 112 ER - TY - JOUR AB - Rhythms with time scales of multiple cycles per second permeate the mammalian brain, yet neuroscientists are not certain of their functional roles. One leading idea is that coherent oscillation between two brain regions facilitates the exchange of information between them. In rats, the hippocampus and the vibrissal sensorimotor system both are characterized by rhythmic oscillation in the theta range, 5–12 Hz. Previous work has been divided as to whether the two rhythms are independent or coherent. To resolve this question, we acquired three measures from rats—whisker motion, hippocampal local field potential (LFP), and barrel cortex unit firing—during a whisker-mediated texture discrimination task and during control conditions (not engaged in a whisker-mediated memory task). Compared to control conditions, the theta band of hippocampal LFP showed a marked increase in power as the rats approached and then palpated the texture. Phase synchronization between whisking and hippocampal LFP increased by almost 50% during approach and texture palpation. In addition, a greater proportion of barrel cortex neurons showed firing that was phase-locked to hippocampal theta while rats were engaged in the discrimination task. Consistent with a behavioral consequence of phase synchronization, the rats identified the texture more rapidly and with lower error likelihood on trials in which there was an increase in theta-whisking coherence at the moment of texture palpation. These results suggest that coherence between the whisking rhythm, barrel cortex firing, and hippocampal LFP is augmented selectively during epochs in which the rat collects sensory information and that such coherence enhances the efficiency of integration of stimulus information into memory and decision-making centers. AU - Grion, Natalia AU - Akrami, Athena AU - Zuo, Yangfang AU - Stella, Federico AU - Diamond, Mathew ID - 1487 IS - 2 JF - PLoS Biology TI - Coherence between rat sensorimotor system and hippocampus is enhanced during tactile discrimination VL - 14 ER - TY - JOUR AB - Plants have the ability to continously generate new organs by maintaining populations of stem cells throught their lives. The shoot apical meristem (SAM) provides a stable environment for the maintenance of stem cells. All cells inside the SAM divide, yet boundaries and patterns are maintained. Experimental evidence indicates that patterning is independent of cell lineage, thus a dynamic self-regulatory mechanism is required. A pivotal role in the organization of the SAM is played by the WUSCHEL gene (WUS). An important question in this regard is that how WUS expression is positioned in the SAM via a cell-lineage independent signaling mechanism. In this study we demonstrate via mathematical modeling that a combination of an inhibitor of the Cytokinin (CK) receptor, Arabidopsis histidine kinase 4 (AHK4) and two morphogens originating from the top cell layer, can plausibly account for the cell lineage-independent centering of WUS expression within SAM. Furthermore, our laser ablation and microsurgical experiments support the hypothesis that patterning in SAM occurs at the level of CK reception and signaling. The model suggests that the interplay between CK signaling, WUS/CLV feedback loop and boundary signals can account for positioning of the WUS expression, and provides directions for further experimental investigation. AU - Adibi, Milad AU - Yoshida, Saiko AU - Weijers, Dolf AU - Fleck, Christian ID - 1482 IS - 2 JF - PLoS One TI - Centering the organizing center in the Arabidopsis thaliana shoot apical meristem by a combination of cytokinin signaling and self-organization VL - 11 ER - TY - JOUR AU - Chen, Xu AU - Wu, Shuang AU - Liu, Zengyu AU - Friml, Jiřĺ ID - 1484 IS - 6 JF - Trends in Cell Biology TI - Environmental and endogenous control of cortical microtubule orientation VL - 26 ER - TY - JOUR AB - In this article the notion of metabolic turnover is revisited in the light of recent results of out-of-equilibrium thermodynamics. By means of Monte Carlo methods we perform an exact sampling of the enzymatic fluxes in a genome scale metabolic network of E. Coli in stationary growth conditions from which we infer the metabolites turnover times. However the latter are inferred from net fluxes, and we argue that this approximation is not valid for enzymes working nearby thermodynamic equilibrium. We recalculate turnover times from total fluxes by performing an energy balance analysis of the network and recurring to the fluctuation theorem. We find in many cases values one of order of magnitude lower, implying a faster picture of intermediate metabolism. AU - De Martino, Daniele ID - 1485 IS - 1 JF - Physical Biology TI - Genome-scale estimate of the metabolic turnover of E. Coli from the energy balance analysis VL - 13 ER - TY - JOUR AB - We review recent results concerning the mathematical properties of the Bardeen-Cooper-Schrieffer (BCS) functional of superconductivity, which were obtained in a series of papers, partly in collaboration with R. Frank, E. Hamza, S. Naboko, and J. P. Solovej. Our discussion includes, in particular, an investigation of the critical temperature for a general class of interaction potentials, as well as a study of its dependence on external fields. We shall explain how the Ginzburg-Landau model can be derived from the BCS theory in a suitable parameter regime. AU - Hainzl, Christian AU - Seiringer, Robert ID - 1486 IS - 2 JF - Journal of Mathematical Physics TI - The Bardeen–Cooper–Schrieffer functional of superconductivity and its mathematical properties VL - 57 ER - TY - JOUR AB - Branching morphogenesis of the epithelial ureteric bud forms the renal collecting duct system and is critical for normal nephron number, while low nephron number is implicated in hypertension and renal disease. Ureteric bud growth and branching requires GDNF signaling from the surrounding mesenchyme to cells at the ureteric bud tips, via the Ret receptor tyrosine kinase and coreceptor Gfrα1; Ret signaling up-regulates transcription factors Etv4 and Etv5, which are also critical for branching. Despite extensive knowledge of the genetic control of these events, it is not understood, at the cellular level, how renal branching morphogenesis is achieved or how Ret signaling influences epithelial cell behaviors to promote this process. Analysis of chimeric embryos previously suggested a role for Ret signaling in promoting cell rearrangements in the nephric duct, but this method was unsuited to study individual cell behaviors during ureteric bud branching. Here, we use Mosaic Analysis with Double Markers (MADM), combined with organ culture and time-lapse imaging, to trace the movements and divisions of individual ureteric bud tip cells. We first examine wild-type clones and then Ret or Etv4 mutant/wild-type clones in which the mutant and wild-type sister cells are differentially and heritably marked by green and red fluorescent proteins. We find that, in normal kidneys, most individual tip cells behave as self-renewing progenitors, some of whose progeny remain at the tips while others populate the growing UB trunks. In Ret or Etv4 MADM clones, the wild-type cells generated at a UB tip are much more likely to remain at, or move to, the new tips during branching and elongation, while their Ret−/− or Etv4−/− sister cells tend to lag behind and contribute only to the trunks. By tracking successive mitoses in a cell lineage, we find that Ret signaling has little effect on proliferation, in contrast to its effects on cell movement. Our results show that Ret/Etv4 signaling promotes directed cell movements in the ureteric bud tips, and suggest a model in which these cell movements mediate branching morphogenesis. AU - Riccio, Paul AU - Cebrián, Cristina AU - Zong, Hui AU - Hippenmeyer, Simon AU - Costantini, Frank ID - 1488 IS - 2 JF - PLoS Biology TI - Ret and Etv4 promote directed movements of progenitor cells during renal branching morphogenesis VL - 14 ER - TY - JOUR AB - We prove optimal local law, bulk universality and non-trivial decay for the off-diagonal elements of the resolvent for a class of translation invariant Gaussian random matrix ensembles with correlated entries. AU - Ajanki, Oskari H AU - Erdös, László AU - Krüger, Torben H ID - 1489 IS - 2 JF - Journal of Statistical Physics TI - Local spectral statistics of Gaussian matrices with correlated entries VL - 163 ER - TY - JOUR AB - To induce adaptive immunity, dendritic cells (DCs) migrate through afferent lymphatic vessels (LVs) to draining lymph nodes (dLNs). This process occurs in several consecutive steps. Upon entry into lymphatic capillaries, DCs first actively crawl into downstream collecting vessels. From there, they are next passively and rapidly transported to the dLN by lymph flow. Here, we describe a role for the chemokine CCL21 in intralymphatic DC crawling. Performing time-lapse imaging in murine skin, we found that blockade of CCL21-but not the absence of lymph flow-completely abolished DC migration from capillaries toward collecting vessels and reduced the ability of intralymphatic DCs to emigrate from skin. Moreover, we found that in vitro low laminar flow established a CCL21 gradient along lymphatic endothelial monolayers, thereby inducing downstream-directed DC migration. These findings reveal a role for intralymphatic CCL21 in promoting DC trafficking to dLNs, through the formation of a flow-induced gradient. AU - Russo, Erica AU - Teijeira, Alvaro AU - Vaahtomeri, Kari AU - Willrodt, Ann AU - Bloch, Joël AU - Nitschké, Maximilian AU - Santambrogio, Laura AU - Kerjaschki, Dontscho AU - Sixt, Michael K AU - Halin, Cornelia ID - 1490 IS - 7 JF - Cell Reports TI - Intralymphatic CCL21 promotes tissue egress of dendritic cells through afferent lymphatic vessels VL - 14 ER - TY - JOUR AB - We introduce a new method for deriving the time-dependent Hartree or Hartree-Fock equations as an effective mean-field dynamics from the microscopic Schrödinger equation for fermionic many-particle systems in quantum mechanics. The method is an adaption of the method used in Pickl (Lett. Math. Phys. 97 (2) 151–164 2011) for bosonic systems to fermionic systems. It is based on a Gronwall type estimate for a suitable measure of distance between the microscopic solution and an antisymmetrized product state. We use this method to treat a new mean-field limit for fermions with long-range interactions in a large volume. Some of our results hold for singular attractive or repulsive interactions. We can also treat Coulomb interaction assuming either a mild singularity cutoff or certain regularity conditions on the solutions to the Hartree(-Fock) equations. In the considered limit, the kinetic and interaction energy are of the same order, while the average force is subleading. For some interactions, we prove that the Hartree(-Fock) dynamics is a more accurate approximation than a simpler dynamics that one would expect from the subleading force. With our method we also treat the mean-field limit coupled to a semiclassical limit, which was discussed in the literature before, and we recover some of the previous results. All results hold for initial data close (but not necessarily equal) to antisymmetrized product states and we always provide explicit rates of convergence. AU - Petrat, Sören P AU - Pickl, Peter ID - 1493 IS - 1 JF - Mathematical Physics, Analysis and Geometry TI - A new method and a new scaling for deriving fermionic mean-field dynamics VL - 19 ER - TY - JOUR AB - To sustain a lifelong ability to initiate organs, plants retain pools of undifferentiated cells with a preserved prolif eration capacity. The root pericycle represents a unique tissue with conditional meristematic activity, and its tight control determines initiation of lateral organs. Here we show that the meristematic activity of the pericycle is constrained by the interaction with the adjacent endodermis. Release of these restraints by elimination of endo dermal cells by single-cell ablation triggers the pericycle to re-enter the cell cycle. We found that endodermis removal substitutes for the phytohormone auxin-dependent initiation of the pericycle meristematic activity. However, auxin is indispensable to steer the cell division plane orientation of new organ-defining divisions. We propose a dual, spatiotemporally distinct role for auxin during lateral root initiation. In the endodermis, auxin releases constraints arising from cell-to-cell interactions that compromise the pericycle meristematic activity, whereas, in the pericycle, auxin defines the orientation of the cell division plane to initiate lateral roots. AU - Marhavy, Peter AU - Montesinos López, Juan C AU - Abuzeineh, Anas AU - Van Damme, Daniël AU - Vermeer, Joop AU - Duclercq, Jérôme AU - Rakusova, Hana AU - Marhavá, Petra AU - Friml, Jirí AU - Geldner, Niko AU - Benková, Eva ID - 1492 IS - 4 JF - Genes and Development TI - Targeted cell elimination reveals an auxin-guided biphasic mode of lateral root initiation VL - 30 ER - TY - JOUR AB - The two-photon 1s2 2s 2p 3P0 1s22s2 1S0 transition in berylliumlike ions is theoretically investigated within a fully relativistic framework and a second-order perturbation theory. We focus our analysis on how electron correlation, as well as the negative-energy spectrum, can affect the forbidden E1M1 decay rate. For this purpose, we include the electronic correlation via an effective local potential and within a single configuration-state model. Due to its experimental interest, evaluations of decay rates are performed for berylliumlike xenon and uranium. We find that the negative-energy contribution can be neglected at the present level of accuracy in the evaluation of the decay rate. On the other hand, if contributions of electronic correlation are not carefully taken into account, it may change the lifetime of the metastable state by up to 20%. By performing a full-relativistic jj-coupling calculation, we found a decrease of the decay rate by two orders of magnitude compared to non-relativistic LS-coupling calculations, for the selected heavy ions. AU - Amaro, Pedro AU - Fratini, Filippo AU - Safari, Laleh AU - Machado, Jorge AU - Guerra, Mauro AU - Indelicato, Paul AU - Santos, José ID - 1496 IS - 3 JF - Physical Review A - Atomic, Molecular, and Optical Physics TI - Relativistic evaluation of the two-photon decay of the metastable 1s22s2p3P0 state in berylliumlike ions with an effective-potential model VL - 93 ER - TY - JOUR AB - Turbulence is one of the most frequently encountered non-equilibrium phenomena in nature, yet characterizing the transition that gives rise to turbulence in basic shear flows has remained an elusive task. Although, in recent studies, critical points marking the onset of sustained turbulence have been determined for several such flows, the physical nature of the transition could not be fully explained. In extensive experimental and computational studies we show for the example of Couette flow that the onset of turbulence is a second-order phase transition and falls into the directed percolation universality class. Consequently, the complex laminar–turbulent patterns distinctive for the onset of turbulence in shear flows result from short-range interactions of turbulent domains and are characterized by universal critical exponents. More generally, our study demonstrates that even high-dimensional systems far from equilibrium such as turbulence exhibit universality at onset and that here the collective dynamics obeys simple rules. AU - Lemoult, Grégoire M AU - Shi, Liang AU - Avila, Kerstin AU - Jalikop, Shreyas V AU - Avila, Marc AU - Hof, Björn ID - 1494 IS - 3 JF - Nature Physics TI - Directed percolation phase transition to sustained turbulence in Couette flow VL - 12 ER - TY - JOUR AB - We study the ground state of a trapped Bose gas, starting from the full many-body Schrödinger Hamiltonian, and derive the non-linear Schrödinger energy functional in the limit of a large particle number, when the interaction potential converges slowly to a Dirac delta function. Our method is based on quantitative estimates on the discrepancy between the full many-body energy and its mean-field approximation using Hartree states. These are proved using finite dimensional localization and a quantitative version of the quantum de Finetti theorem. Our approach covers the case of attractive interactions in the regime of stability. In particular, our main new result is a derivation of the 2D attractive non-linear Schrödinger ground state. AU - Lewin, Mathieu AU - Nam, Phan AU - Rougerie, Nicolas ID - 1491 IS - 9 JF - Transactions of the American Mathematical Society TI - The mean-field approximation and the non-linear Schrödinger functional for trapped Bose gases VL - 368 ER - TY - JOUR AB - The concept of well group in a special but important case captures homological properties of the zero set of a continuous map (Formula presented.) on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within (Formula presented.) distance r from f for a given (Formula presented.). The main drawback of the approach is that the computability of well groups was shown only when (Formula presented.) or (Formula presented.). Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of (Formula presented.) by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and (Formula presented.), our approximation of the (Formula presented.)th well group is exact. For the second part, we find examples of maps (Formula presented.) with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status. AU - Franek, Peter AU - Krcál, Marek ID - 1408 IS - 1 JF - Discrete & Computational Geometry TI - On computability and triviality of well groups VL - 56 ER - TY - JOUR AB - The inference of demographic history from genome data is hindered by a lack of efficient computational approaches. In particular, it has proved difficult to exploit the information contained in the distribution of genealogies across the genome. We have previously shown that the generating function (GF) of genealogies can be used to analytically compute likelihoods of demographic models from configurations of mutations in short sequence blocks (Lohse et al. 2011). Although the GF has a simple, recursive form, the size of such likelihood calculations explodes quickly with the number of individuals and applications of this framework have so far been mainly limited to small samples (pairs and triplets) for which the GF can be written by hand. Here we investigate several strategies for exploiting the inherent symmetries of the coalescent. In particular, we show that the GF of genealogies can be decomposed into a set of equivalence classes that allows likelihood calculations from nontrivial samples. Using this strategy, we automated blockwise likelihood calculations for a general set of demographic scenarios in Mathematica. These histories may involve population size changes, continuous migration, discrete divergence, and admixture between multiple populations. To give a concrete example, we calculate the likelihood for a model of isolation with migration (IM), assuming two diploid samples without phase and outgroup information. We demonstrate the new inference scheme with an analysis of two individual butterfly genomes from the sister species Heliconius melpomene rosina and H. cydno. AU - Lohse, Konrad AU - Chmelik, Martin AU - Martin, Simon AU - Barton, Nicholas H ID - 1518 IS - 2 JF - Genetics TI - Efficient strategies for calculating blockwise likelihoods under the coalescent VL - 202 ER - TY - CONF AB - When designing genetic circuits, the typical primitives used in major existing modelling formalisms are gene interaction graphs, where edges between genes denote either an activation or inhibition relation. However, when designing experiments, it is important to be precise about the low-level mechanistic details as to how each such relation is implemented. The rule-based modelling language Kappa allows to unambiguously specify mechanistic details such as DNA binding sites, dimerisation of transcription factors, or co-operative interactions. Such a detailed description comes with complexity and computationally costly executions. We propose a general method for automatically transforming a rule-based program, by eliminating intermediate species and adjusting the rate constants accordingly. To the best of our knowledge, we show the first automated reduction of rule-based models based on equilibrium approximations. Our algorithm is an adaptation of an existing algorithm, which was designed for reducing reaction-based programs; our version of the algorithm scans the rule-based Kappa model in search for those interaction patterns known to be amenable to equilibrium approximations (e.g. Michaelis-Menten scheme). Additional checks are then performed in order to verify if the reduction is meaningful in the context of the full model. The reduced model is efficiently obtained by static inspection over the rule-set. The tool is tested on a detailed rule-based model of a λ-phage switch, which lists 92 rules and 13 agents. The reduced model has 11 rules and 5 agents, and provides a dramatic reduction in simulation time of several orders of magnitude. AU - Beica, Andreea AU - Guet, Calin C AU - Petrov, Tatjana ID - 1524 TI - Efficient reduction of kappa models by static inspection of the rule-set VL - 9271 ER - TY - JOUR AB - Complex I (NADH:ubiquinone oxidoreductase) plays a central role in cellular energy production, coupling electron transfer between NADH and quinone to proton translocation. It is the largest protein assembly of respiratory chains and one of the most elaborate redox membrane proteins known. Bacterial enzyme is about half the size of mitochondrial and thus provides its important "minimal" model. Dysfunction of mitochondrial complex I is implicated in many human neurodegenerative diseases. The L-shaped complex consists of a hydrophilic arm, where electron transfer occurs, and a membrane arm, where proton translocation takes place. We have solved the crystal structures of the hydrophilic domain of complex I from Thermus thermophilus, the membrane domain from Escherichia coli and recently of the intact, entire complex I from T. thermophilus (536. kDa, 16 subunits, 9 iron-sulphur clusters, 64 transmembrane helices). The 95. Å long electron transfer pathway through the enzyme proceeds from the primary electron acceptor flavin mononucleotide through seven conserved Fe-S clusters to the unusual elongated quinone-binding site at the interface with the membrane domain. Four putative proton translocation channels are found in the membrane domain, all linked by the central flexible axis containing charged residues. The redox energy of electron transfer is coupled to proton translocation by the as yet undefined mechanism proposed to involve long-range conformational changes. This article is part of a Special Issue entitled Respiratory complex I, edited by Volker Zickermann and Ulrich Brandt. AU - Berrisford, John AU - Baradaran, Rozbeh AU - Sazanov, Leonid A ID - 1521 IS - 7 JF - Biochimica et Biophysica Acta - Bioenergetics TI - Structure of bacterial respiratory complex I VL - 1857 ER - TY - JOUR AB - We classify smooth Brunnian (i.e., unknotted on both components) embeddings (S2 × S1) ⊔ S3 → ℝ6. Any Brunnian embedding (S2 × S1) ⊔ S3 → ℝ6 is isotopic to an explicitly constructed embedding fk,m,n for some integers k, m, n such that m ≡ n (mod 2). Two embeddings fk,m,n and fk′ ,m′,n′ are isotopic if and only if k = k′, m ≡ m′ (mod 2k) and n ≡ n′ (mod 2k). We use Haefliger’s classification of embeddings S3 ⊔ S3 → ℝ6 in our proof. The relation between the embeddings (S2 × S1) ⊔ S3 → ℝ6 and S3 ⊔ S3 → ℝ6 is not trivial, however. For example, we show that there exist embeddings f: (S2 ×S1) ⊔ S3 → ℝ6 and g, g′ : S3 ⊔ S3 → ℝ6 such that the componentwise embedded connected sum f # g is isotopic to f # g′ but g is not isotopic to g′. AU - Avvakumov, Serhii ID - 1522 IS - 1 JF - Moscow Mathematical Journal TI - The classification of certain linked 3-manifolds in 6-space VL - 16 ER - TY - JOUR AB - For random graphs, the containment problem considers the probability that a binomial random graph G(n, p) contains a given graph as a substructure. When asking for the graph as a topological minor, i.e., for a copy of a subdivision of the given graph, it is well known that the (sharp) threshold is at p = 1/n. We consider a natural analogue of this question for higher-dimensional random complexes Xk(n, p), first studied by Cohen, Costa, Farber and Kappeler for k = 2. Improving previous results, we show that p = Θ(1/ √n) is the (coarse) threshold for containing a subdivision of any fixed complete 2-complex. For higher dimensions k > 2, we get that p = O(n−1/k) is an upper bound for the threshold probability of containing a subdivision of a fixed k-dimensional complex. AU - Gundert, Anna AU - Wagner, Uli ID - 1523 IS - 4 JF - Proceedings of the American Mathematical Society TI - On topological minors in random simplicial complexes VL - 144 ER - TY - CONF AB - We present the first study of robustness of systems that are both timed as well as reactive (I/O). We study the behavior of such timed I/O systems in the presence of uncertain inputs and formalize their robustness using the analytic notion of Lipschitz continuity: a timed I/O system is K-(Lipschitz) robust if the perturbation in its output is at most K times the perturbation in its input. We quantify input and output perturbation using similarity functions over timed words such as the timed version of the Manhattan distance and the Skorokhod distance. We consider two models of timed I/O systems — timed transducers and asynchronous sequential circuits. We show that K-robustness of timed transducers can be decided in polynomial space under certain conditions. For asynchronous sequential circuits, we reduce K-robustness w.r.t. timed Manhattan distances to K-robustness of discrete letter-to-letter transducers and show PSpace-completeness of the problem. AU - Henzinger, Thomas A AU - Otop, Jan AU - Samanta, Roopsha ID - 1526 TI - Lipschitz robustness of timed I/O systems VL - 9583 ER - TY - JOUR AB - We provide general conditions for which bosonic quadratic Hamiltonians on Fock spaces can be diagonalized by Bogoliubov transformations. Our results cover the case when quantum systems have infinite degrees of freedom and the associated one-body kinetic and paring operators are unbounded. Our sufficient conditions are optimal in the sense that they become necessary when the relevant one-body operators commute. AU - Nam, Phan AU - Napiórkowski, Marcin M AU - Solovej, Jan ID - 1545 IS - 11 JF - Journal of Functional Analysis TI - Diagonalization of bosonic quadratic Hamiltonians by Bogoliubov transformations VL - 270 ER - TY - JOUR AB - Antibiotic resistance carries a fitness cost that must be overcome in order for resistance to persist over the long term. Compensatory mutations that recover the functional defects associated with resistance mutations have been argued to play a key role in overcoming the cost of resistance, but compensatory mutations are expected to be rare relative to generally beneficial mutations that increase fitness, irrespective of antibiotic resistance. Given this asymmetry, population genetics theory predicts that populations should adapt by compensatory mutations when the cost of resistance is large, whereas generally beneficial mutations should drive adaptation when the cost of resistance is small. We tested this prediction by determining the genomic mechanisms underpinning adaptation to antibiotic-free conditions in populations of the pathogenic bacterium Pseudomonas aeruginosa that carry costly antibiotic resistance mutations. Whole-genome sequencing revealed that populations founded by high-cost rifampicin-resistant mutants adapted via compensatory mutations in three genes of the RNA polymerase core enzyme, whereas populations founded by low-cost mutants adapted by generally beneficial mutations, predominantly in the quorum-sensing transcriptional regulator gene lasR. Even though the importance of compensatory evolution in maintaining resistance has been widely recognized, our study shows that the roles of general adaptation in maintaining resistance should not be underestimated and highlights the need to understand how selection at other sites in the genome influences the dynamics of resistance alleles in clinical settings. AU - Qi, Qin AU - Toll Riera, Macarena AU - Heilbron, Karl AU - Preston, Gail AU - Maclean, R Craig ID - 1552 IS - 1822 JF - Proceedings of the Royal Society of London Series B Biological Sciences TI - The genomic basis of adaptation to the fitness cost of rifampicin resistance in Pseudomonas aeruginosa VL - 283 ER - TY - JOUR AB - Aiming at the automatic diagnosis of tumors using narrow band imaging (NBI) magnifying endoscopic (ME) images of the stomach, we combine methods from image processing, topology, geometry, and machine learning to classify patterns into three classes: oval, tubular and irregular. Training the algorithm on a small number of images of each type, we achieve a high rate of correct classifications. The analysis of the learning algorithm reveals that a handful of geometric and topological features are responsible for the overwhelming majority of decisions. AU - Dunaeva, Olga AU - Edelsbrunner, Herbert AU - Lukyanov, Anton AU - Machin, Michael AU - Malkova, Daria AU - Kuvaev, Roman AU - Kashin, Sergey ID - 1289 IS - 1 JF - Pattern Recognition Letters TI - The classification of endoscopy images with persistent homology VL - 83 ER - TY - CONF AB - A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, … , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. A pair of edges e and f in a graph is independent if e and f do not share a vertex. We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing. AU - Fulek, Radoslav AU - Pelsmajer, Michael AU - Schaefer, Marcus ID - 1164 TI - Hanani-Tutte for radial planarity II VL - 9801 ER - TY - JOUR AB - A modular approach to constructing cryptographic protocols leads to simple designs but often inefficient instantiations. On the other hand, ad hoc constructions may yield efficient protocols at the cost of losing conceptual simplicity. We suggest a new design paradigm, structure-preserving cryptography, that provides a way to construct modular protocols with reasonable efficiency while retaining conceptual simplicity. A cryptographic scheme over a bilinear group is called structure-preserving if its public inputs and outputs consist of elements from the bilinear groups and their consistency can be verified by evaluating pairing-product equations. As structure-preserving schemes smoothly interoperate with each other, they are useful as building blocks in modular design of cryptographic applications. This paper introduces structure-preserving commitment and signature schemes over bilinear groups with several desirable properties. The commitment schemes include homomorphic, trapdoor and length-reducing commitments to group elements, and the structure-preserving signature schemes are the first ones that yield constant-size signatures on multiple group elements. A structure-preserving signature scheme is called automorphic if the public keys lie in the message space, which cannot be achieved by compressing inputs via a cryptographic hash function, as this would destroy the mathematical structure we are trying to preserve. Automorphic signatures can be used for building certification chains underlying privacy-preserving protocols. Among a vast number of applications of structure-preserving protocols, we present an efficient round-optimal blind-signature scheme and a group signature scheme with an efficient and concurrently secure protocol for enrolling new members. AU - Abe, Masayuki AU - Fuchsbauer, Georg AU - Groth, Jens AU - Haralambiev, Kristiyan AU - Ohkubo, Miyako ID - 1592 IS - 2 JF - Journal of Cryptology TI - Structure preserving signatures and commitments to group elements VL - 29 ER - TY - JOUR AB - The addition of polysialic acid to N- and/or O-linked glycans, referred to as polysialylation, is a rare posttranslational modification that is mainly known to control the developmental plasticity of the nervous system. Here we show that CCR7, the central chemokine receptor controlling immune cell trafficking to secondary lymphatic organs, carries polysialic acid. This modification is essential for the recognition of the CCR7 ligand CCL21. As a consequence, dendritic cell trafficking is abrogated in polysialyltransferase-deficient mice, manifesting as disturbed lymph node homeostasis and unresponsiveness to inflammatory stimuli. Structure-function analysis of chemokine-receptor interactions reveals that CCL21 adopts an autoinhibited conformation, which is released upon interaction with polysialic acid. Thus, we describe a glycosylation-mediated immune cell trafficking disorder and its mechanistic basis. AU - Kiermaier, Eva AU - Moussion, Christine AU - Veldkamp, Christopher AU - Gerardy Schahn, Rita AU - De Vries, Ingrid AU - Williams, Larry AU - Chaffee, Gary AU - Phillips, Andrew AU - Freiberger, Friedrich AU - Imre, Richard AU - Taleski, Deni AU - Payne, Richard AU - Braun, Asolina AU - Förster, Reinhold AU - Mechtler, Karl AU - Mühlenhoff, Martina AU - Volkman, Brian AU - Sixt, Michael K ID - 1599 IS - 6269 JF - Science TI - Polysialylation controls dendritic cell trafficking by regulating chemokine recognition VL - 351 ER - TY - JOUR AB - Chemokines are the main guidance cues directing leukocyte migration. Opposed to early assumptions, chemokines do not necessarily act as soluble cues but are often immobilized within tissues, e.g., dendritic cell migration toward lymphatic vessels is guided by a haptotactic gradient of the chemokine CCL21. Controlled assay systems to quantitatively study haptotaxis in vitro are still missing. In this chapter, we describe an in vitro haptotaxis assay optimized for the unique properties of dendritic cells. The chemokine CCL21 is immobilized in a bioactive state, using laser-assisted protein adsorption by photobleaching. The cells follow this immobilized CCL21 gradient in a haptotaxis chamber, which provides three dimensionally confined migration conditions. AU - Schwarz, Jan AU - Sixt, Michael K ID - 1597 JF - Methods in Enzymology TI - Quantitative analysis of dendritic cell haptotaxis VL - 570 ER - TY - JOUR AB - We show that the Anderson model has a transition from localization to delocalization at exactly 2 dimensional growth rate on antitrees with normalized edge weights which are certain discrete graphs. The kinetic part has a one-dimensional structure allowing a description through transfer matrices which involve some Schur complement. For such operators we introduce the notion of having one propagating channel and extend theorems from the theory of one-dimensional Jacobi operators that relate the behavior of transfer matrices with the spectrum. These theorems are then applied to the considered model. In essence, in a certain energy region the kinetic part averages the random potentials along shells and the transfer matrices behave similar as for a one-dimensional operator with random potential of decaying variance. At d dimensional growth for d>2 this effective decay is strong enough to obtain absolutely continuous spectrum, whereas for some uniform d dimensional growth with d<2 one has pure point spectrum in this energy region. At exactly uniform 2 dimensional growth also some singular continuous spectrum appears, at least at small disorder. As a corollary we also obtain a change from singular spectrum (d≤2) to absolutely continuous spectrum (d≥3) for random operators of the type rΔdr+λ on ℤd, where r is an orthogonal radial projection, Δd the discrete adjacency operator (Laplacian) on ℤd and λ a random potential. AU - Sadel, Christian ID - 1608 IS - 7 JF - Annales Henri Poincare TI - Anderson transition at 2 dimensional growth rate on antitrees and spectral theory for operators with one propagating channel VL - 17 ER - TY - JOUR AB - We prove that whenever A is a 3-conservative relational structure with only binary and unary relations,then the algebra of polymorphisms of A either has no Taylor operation (i.e.,CSP(A)is NP-complete),or it generates an SD(∧) variety (i.e.,CSP(A)has bounded width). AU - Kazda, Alexandr ID - 1612 IS - 1 JF - Algebra Universalis TI - CSP for binary conservative relational structures VL - 75 ER - TY - JOUR AB - We study the discrepancy of jittered sampling sets: such a set P⊂ [0,1]d is generated for fixed m∈ℕ by partitioning [0,1]d into md axis aligned cubes of equal measure and placing a random point inside each of the N=md cubes. We prove that, for N sufficiently large, 1/10 d/N1/2+1/2d ≤EDN∗(P)≤ √d(log N) 1/2/N1/2+1/2d, where the upper bound with an unspecified constant Cd was proven earlier by Beck. Our proof makes crucial use of the sharp Dvoretzky-Kiefer-Wolfowitz inequality and a suitably taylored Bernstein inequality; we have reasons to believe that the upper bound has the sharp scaling in N. Additional heuristics suggest that jittered sampling should be able to improve known bounds on the inverse of the star-discrepancy in the regime N≳dd. We also prove a partition principle showing that every partition of [0,1]d combined with a jittered sampling construction gives rise to a set whose expected squared L2-discrepancy is smaller than that of purely random points. AU - Pausinger, Florian AU - Steinerberger, Stefan ID - 1617 JF - Journal of Complexity TI - On the discrepancy of jittered sampling VL - 33 ER - TY - JOUR AB - We consider the Bardeen–Cooper–Schrieffer free energy functional for particles interacting via a two-body potential on a microscopic scale and in the presence of weak external fields varying on a macroscopic scale. We study the influence of the external fields on the critical temperature. We show that in the limit where the ratio between the microscopic and macroscopic scale tends to zero, the next to leading order of the critical temperature is determined by the lowest eigenvalue of the linearization of the Ginzburg–Landau equation. AU - Frank, Rupert AU - Hainzl, Christian AU - Seiringer, Robert AU - Solovej, Jan ID - 1620 IS - 1 JF - Communications in Mathematical Physics TI - The external field dependence of the BCS critical temperature VL - 342 ER - TY - JOUR AB - We prove analogues of the Lieb–Thirring and Hardy–Lieb–Thirring inequalities for many-body quantum systems with fractional kinetic operators and homogeneous interaction potentials, where no anti-symmetry on the wave functions is assumed. These many-body inequalities imply interesting one-body interpolation inequalities, and we show that the corresponding one- and many-body inequalities are actually equivalent in certain cases. AU - Lundholm, Douglas AU - Nam, Phan AU - Portmann, Fabian ID - 1622 IS - 3 JF - Archive for Rational Mechanics and Analysis TI - Fractional Hardy–Lieb–Thirring and related Inequalities for interacting systems VL - 219 ER - TY - JOUR AB - Ancestral processes are fundamental to modern population genetics and spatial structure has been the subject of intense interest for many years. Despite this interest, almost nothing is known about the distribution of the locations of pedigree or genetic ancestors. Using both spatially continuous and stepping-stone models, we show that the distribution of pedigree ancestors approaches a travelling wave, for which we develop two alternative approximations. The speed and width of the wave are sensitive to the local details of the model. After a short time, genetic ancestors spread far more slowly than pedigree ancestors, ultimately diffusing out with radius ## rather than spreading at constant speed. In contrast to the wave of pedigree ancestors, the spread of genetic ancestry is insensitive to the local details of the models. AU - Kelleher, Jerome AU - Etheridge, Alison AU - Véber, Amandine AU - Barton, Nicholas H ID - 1631 JF - Theoretical Population Biology TI - Spread of pedigree versus genetic ancestry in spatially distributed populations VL - 108 ER - TY - JOUR AB - The plant hormone auxin (indole-3-acetic acid) is a major regulator of plant growth and development including embryo and root patterning, lateral organ formation and growth responses to environmental stimuli. Auxin is directionally transported from cell to cell by the action of specific auxin influx [AUXIN-RESISTANT1 (AUX1)] and efflux [PIN-FORMED (PIN)] transport regulators, whose polar, subcellular localizations are aligned with the direction of the auxin flow. Auxin itself regulates its own transport by modulation of the expression and subcellular localization of the auxin transporters. Increased auxin levels promote the transcription of PIN2 and AUX1 genes as well as stabilize PIN proteins at the plasma membrane, whereas prolonged auxin exposure increases the turnover of PIN proteins and their degradation in the vacuole. In this study, we applied a forward genetic approach, to identify molecular components playing a role in the auxin-mediated degradation. We generated EMS-mutagenized Arabidopsis PIN2::PIN2:GFP, AUX1::AUX1:YFP eir1aux1 populations and designed a screen for mutants with persistently strong fluorescent signals of the tagged PIN2 and AUX1 after prolonged treatment with the synthetic auxin 2,4-dichlorophenoxyacetic acid (2,4-D). This approach yielded novel auxin degradation mutants defective in trafficking and degradation of PIN2 and AUX1 proteins and established a role for auxin-mediated degradation in plant development. AU - Zemová, Radka AU - Zwiewka, Marta AU - Bielach, Agnieszka AU - Robert, Hélène AU - Friml, Jirí ID - 1641 IS - 2 JF - Journal of Plant Growth Regulation TI - A forward genetic screen for new regulators of auxin mediated degradation of auxin transport proteins in Arabidopsis thaliana VL - 35 ER - TY - CONF AB - At Crypto 2015 Fuchsbauer, Hanser and Slamanig (FHS) presented the first standard-model construction of efficient roundoptimal blind signatures that does not require complexity leveraging. It is conceptually simple and builds on the primitive of structure-preserving signatures on equivalence classes (SPS-EQ). FHS prove the unforgeability of their scheme assuming EUF-CMA security of the SPS-EQ scheme and hardness of a version of the DH inversion problem. Blindness under adversarially chosen keys is proven under an interactive variant of the DDH assumption. We propose a variant of their scheme whose blindness can be proven under a non-interactive assumption, namely a variant of the bilinear DDH assumption. We moreover prove its unforgeability assuming only unforgeability of the underlying SPS-EQ but no additional assumptions as needed for the FHS scheme. AU - Fuchsbauer, Georg AU - Hanser, Christian AU - Kamath Hosdurg, Chethan AU - Slamanig, Daniel ID - 1225 TI - Practical round-optimal blind signatures in the standard model from weaker assumptions VL - 9841 ER - TY - CONF AB - A somewhere statistically binding (SSB) hash, introduced by Hubáček and Wichs (ITCS ’15), can be used to hash a long string x to a short digest y = H hk (x) using a public hashing-key hk. Furthermore, there is a way to set up the hash key hk to make it statistically binding on some arbitrary hidden position i, meaning that: (1) the digest y completely determines the i’th bit (or symbol) of x so that all pre-images of y have the same value in the i’th position, (2) it is computationally infeasible to distinguish the position i on which hk is statistically binding from any other position i’. Lastly, the hash should have a local opening property analogous to Merkle-Tree hashing, meaning that given x and y = H hk (x) it should be possible to create a short proof π that certifies the value of the i’th bit (or symbol) of x without having to provide the entire input x. A similar primitive called a positional accumulator, introduced by Koppula, Lewko and Waters (STOC ’15) further supports dynamic updates of the hashed value. These tools, which are interesting in their own right, also serve as one of the main technical components in several recent works building advanced applications from indistinguishability obfuscation (iO). The prior constructions of SSB hashing and positional accumulators required fully homomorphic encryption (FHE) and iO respectively. In this work, we give new constructions of these tools based on well studied number-theoretic assumptions such as DDH, Phi-Hiding and DCR, as well as a general construction from lossy/injective functions. AU - Okamoto, Tatsuaki AU - Pietrzak, Krzysztof Z AU - Waters, Brent AU - Wichs, Daniel ID - 1653 TI - New realizations of somewhere statistically binding hashing and positional accumulators VL - 9452 ER - TY - JOUR AB - Continuous-time Markov chain (CTMC) models have become a central tool for understanding the dynamics of complex reaction networks and the importance of stochasticity in the underlying biochemical processes. When such models are employed to answer questions in applications, in order to ensure that the model provides a sufficiently accurate representation of the real system, it is of vital importance that the model parameters are inferred from real measured data. This, however, is often a formidable task and all of the existing methods fail in one case or the other, usually because the underlying CTMC model is high-dimensional and computationally difficult to analyze. The parameter inference methods that tend to scale best in the dimension of the CTMC are based on so-called moment closure approximations. However, there exists a large number of different moment closure approximations and it is typically hard to say a priori which of the approximations is the most suitable for the inference procedure. Here, we propose a moment-based parameter inference method that automatically chooses the most appropriate moment closure method. Accordingly, contrary to existing methods, the user is not required to be experienced in moment closure techniques. In addition to that, our method adaptively changes the approximation during the parameter inference to ensure that always the best approximation is used, even in cases where different approximations are best in different regions of the parameter space. © 2016 Elsevier Ireland Ltd AU - Schilling, Christian AU - Bogomolov, Sergiy AU - Henzinger, Thomas A AU - Podelski, Andreas AU - Ruess, Jakob ID - 1148 JF - Biosystems TI - Adaptive moment closure for parameter inference of biochemical reaction networks VL - 149 ER - TY - JOUR AB - Hybrid systems represent an important and powerful formalism for modeling real-world applications such as embedded systems. A verification tool like SpaceEx is based on the exploration of a symbolic search space (the region space). As a verification tool, it is typically optimized towards proving the absence of errors. In some settings, e.g., when the verification tool is employed in a feedback-directed design cycle, one would like to have the option to call a version that is optimized towards finding an error trajectory in the region space. A recent approach in this direction is based on guided search. Guided search relies on a cost function that indicates which states are promising to be explored, and preferably explores more promising states first. In this paper, we propose an abstraction-based cost function based on coarse-grained space abstractions for guiding the reachability analysis. For this purpose, a suitable abstraction technique that exploits the flexible granularity of modern reachability analysis algorithms is introduced. The new cost function is an effective extension of pattern database approaches that have been successfully applied in other areas. The approach has been implemented in the SpaceEx model checker. The evaluation shows its practical potential. AU - Bogomolov, Sergiy AU - Donzé, Alexandre AU - Frehse, Goran AU - Grosu, Radu AU - Johnson, Taylor AU - Ladan, Hamed AU - Podelski, Andreas AU - Wehrle, Martin ID - 1705 IS - 4 JF - International Journal on Software Tools for Technology Transfer TI - Guided search for hybrid systems based on coarse-grained space abstractions VL - 18 ER - TY - CONF AB - Volunteer supporters play an important role in modern crisis and disaster management. In the times of mobile Internet devices, help from thousands of volunteers can be requested within a short time span, thus relieving professional helpers from minor chores or geographically spread-out tasks. However, the simultaneous availability of many volunteers also poses new problems. In particular, the volunteer efforts must be well coordinated, or otherwise situations might emerge in which too many idle volunteers at one location become more of a burden than a relief to the professionals. In this work, we study the task of optimally assigning volunteers to selected locations, e.g. in order to perform regular measurements, to report on damage, or to distribute information or resources to the population in a crisis situation. We formulate the assignment tasks as an optimization problem and propose an effective and efficient solution procedure. Experiments on real data of the Team Österreich, consisting of over 36,000 Austrian volunteers, show the effectiveness and efficiency of our approach. AU - Pielorz, Jasmin AU - Lampert, Christoph ID - 1707 TI - Optimal geospatial allocation of volunteers for crisis management ER - TY - JOUR AB - Relational models for contingency tables are generalizations of log-linear models, allowing effects associated with arbitrary subsets of cells in the table, and not necessarily containing the overall effect, that is, a common parameter in every cell. Similarly to log-linear models, relational models can be extended to non-negative distributions, but the extension requires more complex methods. An extended relational model is defined as an algebraic variety, and it turns out to be the closure of the original model with respect to the Bregman divergence. In the extended relational model, the MLE of the cell parameters always exists and is unique, but some of its properties may be different from those of the MLE under log-linear models. The MLE can be computed using a generalized iterative scaling procedure based on Bregman projections. AU - Klimova, Anna AU - Rudas, Tamás ID - 1833 JF - Journal of Multivariate Analysis TI - On the closure of relational models VL - 143 ER - TY - JOUR AB - We consider random matrices of the form H=W+λV, λ∈ℝ+, where W is a real symmetric or complex Hermitian Wigner matrix of size N and V is a real bounded diagonal random matrix of size N with i.i.d.\ entries that are independent of W. We assume subexponential decay for the matrix entries of W and we choose λ∼1, so that the eigenvalues of W and λV are typically of the same order. Further, we assume that the density of the entries of V is supported on a single interval and is convex near the edges of its support. In this paper we prove that there is λ+∈ℝ+ such that the largest eigenvalues of H are in the limit of large N determined by the order statistics of V for λ>λ+. In particular, the largest eigenvalue of H has a Weibull distribution in the limit N→∞ if λ>λ+. Moreover, for N sufficiently large, we show that the eigenvectors associated to the largest eigenvalues are partially localized for λ>λ+, while they are completely delocalized for λ<λ+. Similar results hold for the lowest eigenvalues. AU - Lee, Jioon AU - Schnelli, Kevin ID - 1881 IS - 1-2 JF - Probability Theory and Related Fields TI - Extremal eigenvalues and eigenvectors of deformed Wigner matrices VL - 164 ER - TY - JOUR AB - We consider two systems (α1, …, αm) and (β1, …,βn) of simple curves drawn on a compact two-dimensional surface M with boundary. Each αi and each βj is either an arc meeting the boundary of M at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to “untangle” the βj from the ai by a self-homeomorphism of M; more precisely, we seek a homeomorphism φ:M→M fixing the boundary of M pointwise such that the total number of crossings of the ai with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if M is planar, i.e., a sphere with h ≥ 0 boundary components (“holes”), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface M with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. The proofs rely, among other things, on a result concerning simultaneous planar drawings of graphs by Erten and Kobourov. AU - Matoušek, Jiří AU - Sedgwick, Eric AU - Tancer, Martin AU - Wagner, Uli ID - 1411 IS - 1 JF - Israel Journal of Mathematics TI - Untangling two systems of noncrossing curves VL - 212 ER - TY - JOUR AB - Most entropy notions H(.) like Shannon or min-entropy satisfy a chain rule stating that for random variables X,Z, and A we have H(X|Z,A)≥H(X|Z)−|A|. That is, by conditioning on A the entropy of X can decrease by at most the bitlength |A| of A. Such chain rules are known to hold for some computational entropy notions like Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue of min-entropy, the chain rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption, and memory delegation. These applications rely on restricted special cases of the chain rule. Whether the chain rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: we construct joint distributions (X,Z,A), where A is a distribution over a single bit, such that the HILL entropy H HILL (X|Z) is large but H HILL (X|Z,A) is basically zero. Our counterexample just makes the minimal assumption that NP⊈P/poly. Under the stronger assumption that injective one-way function exist, we can make all the distributions efficiently samplable. Finally, we show that some more sophisticated cryptographic objects like lossy functions can be used to sample a distribution constituting a counterexample to the chain rule making only a single invocation to the underlying object. AU - Krenn, Stephan AU - Pietrzak, Krzysztof Z AU - Wadia, Akshay AU - Wichs, Daniel ID - 1479 IS - 3 JF - Computational Complexity TI - A counterexample to the chain rule for conditional HILL entropy VL - 25 ER - TY - CONF AB - Magic: the Gathering is a game about magical combat for any number of players. Formally it is a zero-sum, imperfect information stochastic game that consists of a potentially unbounded number of steps. We consider the problem of deciding if a move is legal in a given single step of Magic. We show that the problem is (a) coNP-complete in general; and (b) in P if either of two small sets of cards are not used. Our lower bound holds even for single-player Magic games. The significant aspects of our results are as follows: First, in most real-life game problems, the task of deciding whether a given move is legal in a single step is trivial, and the computationally hard task is to find the best sequence of legal moves in the presence of multiple players. In contrast, quite uniquely our hardness result holds for single step and with only one-player. Second, we establish efficient algorithms for important special cases of Magic. AU - Chatterjee, Krishnendu AU - Ibsen-Jensen, Rasmus ID - 478 TI - The complexity of deciding legality of a single step of magic: The gathering VL - 285 ER - TY - CONF AB - Clinical guidelines and decision support systems (DSS) play an important role in daily practices of medicine. Many text-based guidelines have been encoded for work-flow simulation of DSS to automate health care. During the collaboration with Carle hospital to develop a DSS, we identify that, for some complex and life-critical diseases, it is highly desirable to automatically rigorously verify some complex temporal properties in guidelines, which brings new challenges to current simulation based DSS with limited support of automatical formal verification and real-time data analysis. In this paper, we conduct the first study on applying runtime verification to cooperate with current DSS based on real-time data. Within the proposed technique, a user-friendly domain specific language, named DRTV, is designed to specify vital real-time data sampled by medical devices and temporal properties originated from clinical guidelines. Some interfaces are developed for data acquisition and communication. Then, for medical practice scenarios described in DRTV model, we will automatically generate event sequences and runtime property verifier automata. If a temporal property violates, real-time warnings will be produced by the formal verifier and passed to medical DSS. We have used DRTV to specify different kinds of medical care scenarios, and applied the proposed technique to assist existing DSS. As presented in experiment results, in terms of warning detection, it outperforms the only use of DSS or human inspection, and improves the quality of clinical health care of hospital AU - Jiang, Yu AU - Liu, Han AU - Kong, Hui AU - Wang, Rui AU - Hosseini, Mohamad AU - Sun, Jiaguang AU - Sha, Lui ID - 479 T2 - Proceedings of the 38th International Conference on Software Engineering Companion TI - Use runtime verification to improve the quality of medical care practice ER - TY - CONF AB - Graph games provide the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic reactive processes, the traditional model is perfect-information stochastic games, where some transitions of the game graph are controlled by two adversarial players, and the other transitions are executed probabilistically. We consider such games where the objective is the conjunction of several quantitative objectives (specified as mean-payoff conditions), which we refer to as generalized mean-payoff objectives. The basic decision problem asks for the existence of a finite-memory strategy for a player that ensures the generalized mean-payoff objective be satisfied with a desired probability against all strategies of the opponent. A special case of the decision problem is the almost-sure problem where the desired probability is 1. Previous results presented a semi-decision procedure for -approximations of the almost-sure problem. In this work, we show that both the almost-sure problem as well as the general basic decision problem are coNP-complete, significantly improving the previous results. Moreover, we show that in the case of 1-player stochastic games, randomized memoryless strategies are sufficient and the problem can be solved in polynomial time. In contrast, in two-player stochastic games, we show that even with randomized strategies exponential memory is required in general, and present a matching exponential upper bound. We also study the basic decision problem with infinite-memory strategies and present computational complexity results for the problem. Our results are relevant in the synthesis of stochastic reactive systems with multiple quantitative requirements. AU - Chatterjee, Krishnendu AU - Doyen, Laurent ID - 480 TI - Perfect-information stochastic games with generalized mean-payoff objectives VL - 05-08-July-2016 ER - TY - CONF AB - We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case. AU - Burton, Benjamin AU - De Mesmay, Arnaud N AU - Wagner, Uli ID - 1379 TI - Finding non-orientable surfaces in 3-manifolds VL - 51 ER - TY - JOUR AB - We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages provides a robust specification language to express properties in verification, and parity objectives are canonical forms to express them. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are undecidable even for special cases of parity objectives, we establish decidability (with optimal complexity) for POMDPs with all parity objectives under finite-memory strategies. We establish optimal (exponential) memory bounds and EXPTIME-completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives. We also present a practical approach, where we design heuristics to deal with the exponential complexity, and have applied our implementation on a number of POMDP examples. AU - Chatterjee, Krishnendu AU - Chmelik, Martin AU - Tracol, Mathieu ID - 1477 IS - 5 JF - Journal of Computer and System Sciences TI - What is decidable about partially observable Markov decision processes with ω-regular objectives VL - 82 ER - TY - JOUR AB - We consider partially observable Markov decision processes (POMDPs) with a set of target states and an integer cost associated with every transition. The optimization objective we study asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we also present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest. AU - Chatterjee, Krishnendu AU - Chmelik, Martin AU - Gupta, Raghav AU - Kanodia, Ayush ID - 1529 JF - Artificial Intelligence TI - Optimal cost almost-sure reachability in POMDPs VL - 234 ER - TY - GEN AB - We consider the quantitative analysis problem for interprocedural control-flow graphs (ICFGs). The input consists of an ICFG, a positive weight function that assigns every transition a positive integer-valued number, and a labelling of the transitions (events) as good, bad, and neutral events. The weight function assigns to each transition a numerical value that represents ameasure of how good or bad an event is. The quantitative analysis problem asks whether there is a run of the ICFG where the ratio of the sum of the numerical weights of good events versus the sum of weights of bad events in the long-run is at least a given threshold (or equivalently, to compute the maximal ratio among all valid paths in the ICFG). The quantitative analysis problem for ICFGs can be solved in polynomial time, and we present an efficient and practical algorithm for the problem. We show that several problems relevant for static program analysis, such as estimating the worst-case execution time of a program or the average energy consumption of a mobile application, can be modeled in our framework. We have implemented our algorithm as a tool in the Java Soot framework. We demonstrate the effectiveness of our approach with two case studies. First, we show that our framework provides a sound approach (no false positives) for the analysis of inefficiently-used containers. Second, we show that our approach can also be used for static profiling of programs which reasons about methods that are frequently invoked. Our experimental results show that our tool scales to relatively large benchmarks, and discovers relevant and useful information that can be used to optimize performance of the programs. AU - Chatterjee, Krishnendu AU - Pavlogiannis, Andreas AU - Velner, Yaron ID - 5445 SN - 2664-1690 TI - Quantitative interprocedural analysis ER - TY - CONF AB - POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIMEcomplete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach. © 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. AU - Chatterjee, Krishnendu AU - Chmelik, Martin AU - Davies, Jessica ID - 1166 T2 - Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence TI - A symbolic SAT based algorithm for almost sure reachability with small strategies in pomdps VL - 2016 ER - TY - GEN AB - The fixation probability is the probability that a new mutant introduced in a homogeneous population eventually takes over the entire population. The fixation probability is a fundamental quantity of natural selection, and known to depend on the population structure. Amplifiers of natural selection are population structures which increase the fixation probability of advantageous mutants, as compared to the baseline case of well-mixed populations. In this work we focus on symmetric population structures represented as undirected graphs. In the regime of undirected graphs, the strongest amplifier known has been the Star graph, and the existence of undirected graphs with stronger amplification properties has remained open for over a decade. In this work we present the Comet and Comet-swarm families of undirected graphs. We show that for a range of fitness values of the mutants, the Comet and Comet-swarm graphs have fixation probability strictly larger than the fixation probability of the Star graph, for fixed population size and at the limit of large populations, respectively. AU - Pavlogiannis, Andreas AU - Tkadlec, Josef AU - Chatterjee, Krishnendu AU - Nowak, Martin ID - 5449 SN - 2664-1690 TI - Amplification on undirected population structures: Comets beat stars ER -