TY - JOUR AB - We have selected problems that may not yet be well known, but have the potential to push the research in interesting directions. In particular, we state problems that do not require specific knowledge outside the standard circle of ideas in discrete geometry. Despite the relatively simple statements, these problems are related to current research and their solutions are likely to require new ideas and approaches. We have chosen problems from different fields to make this short paper attractive to a wide range of specialists. AU - Herbert Edelsbrunner AU - Ivanov, Alexander AU - Karasev, Roman ID - 2911 JF - Automatic Control and Computer Sciences TI - Open problems in discrete and computational geometry VL - in print ER - TY - CONF AB - In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k = 1 and k = 2 respectively. In particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron. AU - Huber, Anna AU - Kolmogorov, Vladimir ID - 2930 TI - Towards minimizing k-submodular functions VL - 7422 ER - TY - GEN AB - This paper addresses the problem of approximate MAP-MRF inference in general graphical models. Following [36], we consider a family of linear programming relaxations of the problem where each relaxation is specified by a set of nested pairs of factors for which the marginalization constraint needs to be enforced. We develop a generalization of the TRW-S algorithm [9] for this problem, where we use a decomposition into junction chains, monotonic w.r.t. some ordering on the nodes. This generalizes the monotonic chains in [9] in a natural way. We also show how to deal with nested factors in an efficient way. Experiments show an improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on a number of computer vision and natural language processing problems. AU - Kolmogorov, Vladimir AU - Schoenemann, Thomas ID - 2928 T2 - arXiv TI - Generalized sequential tree-reweighted message passing ER - TY - GEN AU - Vladimir Kolmogorov ID - 2929 TI - The power of linear programming for valued CSPs: a constructive characterization ER - TY - CONF AB - Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from this task by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is hard as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage, ZKCrypt provides assurance that the output implementation securely realizes the abstract proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system. AU - Almeida, José AU - Barbosa, Manuel AU - Bangerter, Endre AU - Barthe, Gilles AU - Krenn, Stephan AU - Béguelin, Santiago ID - 2937 T2 - Proceedings of the 2012 ACM conference on Computer and communications security TI - Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols ER - TY - CONF AB - The notion of delays arises naturally in many computational models, such as, in the design of circuits, control systems, and dataflow languages. In this work, we introduce automata with delay blocks (ADBs), extending finite state automata with variable time delay blocks, for deferring individual transition output symbols, in a discrete-time setting. We show that the ADB languages strictly subsume the regular languages, and are incomparable in expressive power to the context-free languages. We show that ADBs are closed under union, concatenation and Kleene star, and under intersection with regular languages, but not closed under complementation and intersection with other ADB languages. We show that the emptiness and the membership problems are decidable in polynomial time for ADBs, whereas the universality problem is undecidable. Finally we consider the linear-time model checking problem, i.e., whether the language of an ADB is contained in a regular language, and show that the model checking problem is PSPACE-complete. Copyright 2012 ACM. AU - Chatterjee, Krishnendu AU - Henzinger, Thomas A AU - Prabhu, Vinayak ID - 2936 T2 - roceedings of the tenth ACM international conference on Embedded software TI - Finite automata with time delay blocks ER - TY - JOUR AB - Social insects have a very high potential to become invasive pest species. Here, we explore how their social lifestyle and their interaction with parasites may contribute to this invasive success. Similar to solitary species, parasite release followed by the evolution of increased competitive ability can promote establishment of introduced social insect hosts in their introduced range. Genetic bottlenecks during introduction of low numbers of founder individuals decrease the genetic diversity at three levels: the population, the colony and the individual, with the colony level being specific to social insects. Reduced genetic diversity can affect both the individual immune system and the collective colony-level disease defences (social immunity). Still, the dual immune system is likely to make social insects more robust to parasite attack. Changes in social structure from small, family-based, territorially aggressive societies in native populations towards huge networks of cooperating nests (unicoloniality) occur in some invasive social insects, for example, most invasive ants and some termites. Unicoloniality is likely to affect disease dynamics in multiple ways. The free exchange of individuals within the population leads to an increased genetic heterogeneity among individuals of a single nest, thereby decreasing disease transmission. However, the multitude of reproductively active queens per colony buffers the effect of individual diseased queens and their offspring, which may result in a higher level of vertical disease transmission in unicolonial societies. Lastly, unicoloniality provides a competitive advantage over native species, allowing them to quickly become the dominant species in the habitat, which in turn selects for parasite adaptation to this common host genotype and thus eventually a high parasite pressure. Overall, invasions by insect societies are characterized by general features applying to all introduced species, as well as idiosyncrasies that emerge from their social lifestyle. It is important to study these effects in concert to be able to develop efficient management and biocontrol strategies. © 2012 British Ecological Society. AU - Ugelvig, Line V AU - Cremer, Sylvia ID - 2938 IS - 6 JF - Functional Ecology TI - Effects of social immunity and unicoloniality on host parasite interactions in invasive insect societies VL - 26 ER - TY - JOUR AB - In this paper, we present a new approach for establishing correspondences between sparse image features related by an unknown nonrigid mapping and corrupted by clutter and occlusion, such as points extracted from images of different instances of the same object category. We formulate this matching task as an energy minimization problem by defining an elaborate objective function of the appearance and the spatial arrangement of the features. Optimization of this energy is an instance of graph matching, which is in general an NP-hard problem. We describe a novel graph matching optimization technique, which we refer to as dual decomposition (DD), and demonstrate on a variety of examples that this method outperforms existing graph matching algorithms. In the majority of our examples, DD is able to find the global minimum within a minute. The ability to globally optimize the objective allows us to accurately learn the parameters of our matching model from training examples. We show on several matching tasks that our learned model yields results superior to those of state-of-the-art methods. AU - Torresani, Lorenzo AU - Kolmogorov, Vladimir AU - Rother, Carsten ID - 2931 IS - 2 JF - IEEE Transactions on Pattern Analysis and Machine Intelligence TI - A dual decomposition approach to feature correspondence VL - 35 ER - TY - CONF AB - Interface theories provide a formal framework for component-based development of software and hardware which supports the incremental design of systems and the independent implementability of components. These capabilities are ensured through mathematical properties of the parallel composition operator and the refinement relation for components. More recently, a conjunction operation was added to interface theories in order to provide support for handling multiple viewpoints, requirements engineering, and component reuse. Unfortunately, the conjunction operator does not allow independent implementability in general. In this paper, we study conditions that need to be imposed on interface models in order to enforce independent implementability with respect to conjunction. We focus on multiple viewpoint specifications and propose a new compatibility criterion between two interfaces, which we call orthogonality. We show that orthogonal interfaces can be refined separately, while preserving both orthogonality and composability with other interfaces. We illustrate the independent implementability of different viewpoints with a FIFO buffer example. AU - Henzinger, Thomas A AU - Nickovic, Dejan ID - 2942 T2 - Conference proceedings Monterey Workshop 2012 TI - Independent implementability of viewpoints VL - 7539 ER - TY - JOUR AB - We examine whether the Escherichia coli chromosome is folded into a self-adherent nucleoprotein complex, or alternately is a confined but otherwise unconstrained self-avoiding polymer. We address this through in vivo visualization, using an inducible GFP fusion to the nucleoid-associated protein Fis to non-specifically decorate the entire chromosome. For a range of different growth conditions, the chromosome is a compact structure that does not fill the volume of the cell, and which moves from the new pole to the cell centre. During rapid growth, chromosome segregation occurs well before cell division, with daughter chromosomes coupled by a thin inter-daughter filament before complete segregation, whereas during slow growth chromosomes stay adjacent until cell division occurs. Image correlation analysis indicates that sub-nucleoid structure is stable on a 1min timescale, comparable to the timescale for redistribution time measured for GFP-Fis after photobleaching. Optical deconvolution and writhe calculation analysis indicate that the nucleoid has a large-scale coiled organization rather than being an amorphous mass. Our observations are consistent with the chromosome having a self-adherent filament organization. AU - Hadizadeh Yazdi, Nastaran AU - Guet, Calin C AU - Johnson, Reid AU - Marko, John ID - 2943 IS - 6 JF - Molecular Microbiology TI - Variation of the folding and dynamics of the Escherichia coli chromosome with growth conditions VL - 86 ER - TY - JOUR AU - Dolbilin, Nikolai AU - Edelsbrunner, Herbert AU - Musin, Oleg ID - 2941 IS - 4 JF - Russian Mathematical Surveys TI - On the optimality of functionals over triangulations of Delaunay sets VL - 67 ER - TY - JOUR AB - MicroRNAs (miRNAs) are small noncoding RNAs that function in literally all cellular processes. miRNAs interact with Argonaute (Ago) proteins and guide them to specific target sites located in the 3′-untranslated region (3′-UTR) of target mRNAs leading to translational repression and deadenylation-induced mRNA degradation. Most miRNAs are processed from hairpin-structured precursors by the consecutive action of the RNase III enzymes Drosha and Dicer. However, processing of miR-451 is Dicer independent and cleavage is mediated by the endonuclease Ago2. Here we have characterized miR-451 sequence and structure requirements for processing as well as sorting of miRNAs into different Ago proteins. Pre-miR-451 appears to be optimized for Ago2 cleavage and changes result in reduced processing. In addition, we show that the mature miR-451 only associates with Ago2 suggesting that mature miRNAs are not exchanged between different members of the Ago protein family. Based on cloning and deep sequencing of endogenous miRNAs associated with Ago1-3, we do not find evidence for miRNA sorting in human cells. However, Ago identity appears to influence the length of some miRNAs, while others remain unaffected. AU - Dueck, Anne AU - Ziegler, Christian AU - Eichner, Alexander AU - Berezikov, Eugène AU - Meister, Gunter ID - 2946 IS - 19 JF - Nucleic Acids Research TI - MicroRNAs associated with the different human Argonaute proteins VL - 40 ER - TY - CONF AB - We introduce games with probabilistic uncertainty, a model for controller synthesis in which the controller observes the state through imprecise sensors that provide correct information about the current state with a fixed probability. That is, in each step, the sensors return an observed state, and given the observed state, there is a probability distribution (due to the estimation error) over the actual current state. The controller must base its decision on the observed state (rather than the actual current state, which it does not know). On the other hand, we assume that the environment can perfectly observe the current state. We show that controller synthesis for qualitative ω-regular objectives in our model can be reduced in polynomial time to standard partial-observation stochastic games, and vice-versa. As a consequence we establish the precise decidability frontier for the new class of games, and establish optimal complexity results for all the decidable problems. AU - Chatterjee, Krishnendu AU - Chmelik, Martin AU - Majumdar, Ritankar ID - 2947 TI - Equivalence of games with probabilistic uncertainty and partial observation games VL - 7561 ER - TY - JOUR AB - In search of foreign antigens, lymphocytes recirculate from the blood, through lymph nodes, into lymphatics and back to the blood. Dendritic cells also migrate to lymph nodes for optimal interaction with lymphocytes. This continuous trafficking of immune cells into and out of lymph nodes is essential for immune surveillance of foreign invaders. In this article, we review our current understanding of the functions of high endothelial venules (HEVs), stroma and lymphatics in the entry, positioning and exit of immune cells in lymph nodes during homeostasis, and we highlight the unexpected role of dendritic cells in the control of lymphocyte homing through HEVs. AU - Girard, Jean AU - Moussion, Christine AU - Förster, Reinhold ID - 2945 IS - 11 JF - Nature Reviews Immunology TI - HEVs, lymphatics and homeostatic immune cell trafficking in lymph nodes VL - 12 ER - TY - JOUR AU - Dupret, David AU - Csicsvari, Jozsef L ID - 2949 IS - 11 JF - Nature Neuroscience TI - The medial entorhinal cortex keeps Up VL - 15 ER - TY - JOUR AB - Spontaneous postsynaptic currents (PSCs) provide key information about the mechanisms of synaptic transmission and the activity modes of neuronal networks. However, detecting spontaneous PSCs in vitro and in vivo has been challenging, because of the small amplitude, the variable kinetics, and the undefined time of generation of these events. Here, we describe a, to our knowledge, new method for detecting spontaneous synaptic events by deconvolution, using a template that approximates the average time course of spontaneous PSCs. A recorded PSC trace is deconvolved from the template, resulting in a series of delta-like functions. The maxima of these delta-like events are reliably detected, revealing the precise onset times of the spontaneous PSCs. Among all detection methods, the deconvolution-based method has a unique temporal resolution, allowing the detection of individual events in high-frequency bursts. Furthermore, the deconvolution-based method has a high amplitude resolution, because deconvolution can substantially increase the signal/noise ratio. When tested against previously published methods using experimental data, the deconvolution-based method was superior for spontaneous PSCs recorded in vivo. Using the high-resolution deconvolution-based detection algorithm, we show that the frequency of spontaneous excitatory postsynaptic currents in dentate gyrus granule cells is 4.5 times higher in vivo than in vitro. AU - Pernia-Andrade, Alejandro AU - Goswami, Sarit AU - Stickler, Yvonne AU - Fröbe, Ulrich AU - Schlögl, Alois AU - Jonas, Peter M ID - 2954 IS - 7 JF - Biophysical Journal TI - A deconvolution based method with high sensitivity and temporal resolution for detection of spontaneous synaptic currents in vitro and in vivo VL - 103 ER - TY - JOUR AB - Contractile actomyosin rings drive various fundamental morphogenetic processes ranging from cytokinesis to wound healing. Actomyosin rings are generally thought to function by circumferential contraction. Here, we show that the spreading of the enveloping cell layer (EVL) over the yolk cell during zebrafish gastrulation is driven by a contractile actomyosin ring. In contrast to previous suggestions, we find that this ring functions not only by circumferential contraction but also by a flow-friction mechanism. This generates a pulling force through resistance against retrograde actomyosin flow. EVL spreading proceeds normally in situations where circumferential contraction is unproductive, indicating that the flow-friction mechanism is sufficient. Thus, actomyosin rings can function in epithelial morphogenesis through a combination of cable-constriction and flow-friction mechanisms. AU - Behrndt, Martin AU - Salbreux, Guillaume AU - Campinho, Pedro AU - Hauschild, Robert AU - Oswald, Felix AU - Roensch, Julia AU - Grill, Stephan AU - Heisenberg, Carl-Philipp J ID - 2950 IS - 6104 JF - Science TI - Forces driving epithelial spreading in zebrafish gastrulation VL - 338 ER - TY - JOUR AB - Differential cell adhesion and cortex tension are thought to drive cell sorting by controlling cell-cell contact formation. Here, we show that cell adhesion and cortex tension have different mechanical functions in controlling progenitor cell-cell contact formation and sorting during zebrafish gastrulation. Cortex tension controls cell-cell contact expansion by modulating interfacial tension at the contact. By contrast, adhesion has little direct function in contact expansion, but instead is needed to mechanically couple the cortices of adhering cells at their contacts, allowing cortex tension to control contact expansion. The coupling function of adhesion is mediated by E-cadherin and limited by the mechanical anchoring of E-cadherin to the cortex. Thus, cell adhesion provides the mechanical scaffold for cell cortex tension to drive cell sorting during gastrulation. AU - Maître, Jean-Léon AU - Berthoumieux, Hélène AU - Krens, Gabriel AU - Salbreux, Guillaume AU - Julicher, Frank AU - Paluch, Ewa AU - Heisenberg, Carl-Philipp J ID - 2951 IS - 6104 JF - Science TI - Adhesion functions in cell sorting by mechanically coupling the cortices of adhering cells VL - 338 ER - TY - JOUR AB - Body axis elongation represents a common and fundamental morphogenetic process in development. A key mechanism triggering body axis elongation without additional growth is convergent extension (CE), whereby a tissue undergoes simultaneous narrowing and extension. Both collective cell migration and cell intercalation are thought to drive CE and are used to different degrees in various species as they elongate their body axis. Here, we provide an overview of CE as a general strategy for body axis elongation and discuss conserved and divergent mechanisms underlying CE among different species. AU - Tada, Masazumi AU - Heisenberg, Carl-Philipp J ID - 2952 IS - 21 JF - Development TI - Convergent extension Using collective cell migration and cell intercalation to shape embryos VL - 139 ER - TY - JOUR AU - Heisenberg, Carl-Philipp J AU - Fässler, Reinhard ID - 2953 IS - 5 JF - Current Opinion in Cell Biology TI - Cell-cell adhesion and extracellular matrix diversity counts VL - 24 ER -