TY - CHAP AU - Vicente, Sara AU - Vladimir Kolmogorov AU - Rother, Carsten ED - Blake, Andrew ED - Kohli, Pushmeet ED - Rother, Carsten ID - 2922 T2 - Markov Random Fields for Vision and Image Processing TI - Graph-cut Based Image Segmentation with Connectivity Priors ER - TY - CHAP AU - Kumar, M Pawan AU - Vladimir Kolmogorov AU - Torr, Philip H ED - Blake, Andrew ED - Kohli, Pushmeet ED - Rother, Carsten ID - 2923 T2 - Markov Random Fields for Vision and Image Processing TI - Analyzing Convex Relaxations for MAP Estimation ER - TY - CHAP AU - Criminisi, Antonio AU - Cross, Geoffrey AU - Blake, Andrew AU - Vladimir Kolmogorov ED - Blake, Andrew ED - Kohli, Pushmeet ED - Rother, Carsten ID - 2924 T2 - Markov Random Fields for Vision and Image Processing TI - Bilayer Segmentation of Video ER - TY - CHAP AU - Rother, Carsten AU - Vladimir Kolmogorov AU - Boykov, Yuri AU - Blake, Andrew ED - Blake, Andrew ED - Kohli, Pushmeet ED - Rother, Carsten ID - 2925 T2 - Markov Random Fields for Vision and Image Processing TI - Interactive Foreground Extraction using graph cut ER - TY - CHAP AU - Boykov, Yuri AU - Vladimir Kolmogorov ED - Blake, Andrew ED - Kohli, Pushmeet ED - Rother, Carsten ID - 2935 T2 - Markov Random Fields for Vision and Image Processing TI - Basic graph cut algorithms ER - TY - JOUR AB - Rapid research progress in genotyping techniques have allowed large genome-wide association studies. Existing methods often focus on determining associations between single loci and a specic phenotype. However, a particular phenotype is usually the result of complex relationships between multiple loci and the environment. In this paper, we describe a two-stage method for detecting epistasis by combining the traditionally used single-locus search with a search for multiway interactions. Our method is based on an extended version of Fisher's exact test. To perform this test, a Markov chain is constructed on the space of multidimensional contingency tables using the elements of a Markov basis as moves. We test our method on simulated data and compare it to a two-stage logistic regression method and to a fully Bayesian method, showing that we are able to detect the interacting loci when other methods fail to do so. Finally, we apply our method to a genome-wide data set consisting of 685 dogs and identify epistasis associated with canine hair length for four pairs of single nucleotide polymorphisms (SNPs). AU - Malaspinas, Anna-Sapfo AU - Caroline Uhler ID - 2961 IS - 1 JF - Journal of Algebraic Statistics TI - Detecting epistasis via Markov bases VL - 2 ER - TY - CONF AB - Traditional statistical methods for the confidentiality protection for statistical databases do not scale well to deal with GWAS (genome-wide association studies) databases and external information on them. The more recent concept of differential privacy, introduced by the cryptographic community, is an approach which provides a rigorous definition of privacy with meaningful privacy guarantees in the presence of arbitrary external information. Building on such notions, we propose new methods to release aggregate GWAS data without compromising an individual's privacy. We present methods for releasing differentially private minor allele frequencies, chi-square statistics and p-values. We compare these approaches on simulated data and on a GWAS study of canine hair length involving 685 dogs. We also propose a privacy-preserving method for finding genome-wide associations based on a differentially private approach to penalized logistic regression. AU - Fienberg, Stephen E AU - Slavkovic, Aleksandra AU - Caroline Uhler ID - 2960 TI - Privacy Preserving GWAS Data Sharing ER - TY - CONF AB - Zero-knowledge proofs of knowledge (ZK-PoK) for discrete logarithms and related problems are indispensable for practical cryptographic protocols. Recently, Camenisch, Kiayias, and Yung provided a specification language (the CKY-language) for such protocols which allows for a modular design and protocol analysis: for every zero-knowledge proof specified in this language, protocol designers are ensured that there exists an efficient protocol which indeed proves the specified statement. However, the protocols resulting from their compilation techniques only satisfy the classical notion of ZK-PoK, which is not retained are when they used as building blocks for higher-level applications or composed with other protocols. This problem can be tackled by moving to the Universal Composability (UC) framework, which guarantees retention of security when composing protocols in arbitrary ways. While there exist generic transformations from $\Sigma$-protocols to UC-secure protocols, these transformation are often too inefficient for practice. In this paper we introduce a specification language akin to the CKY-language and a compiler such that the resulting protocols are UC-secure and efficient. To this end, we propose an extension of the UC-framework addressing the issue that UC-secure zero-knowledge proofs are by definition proofs of knowledge, and state a special composition theorem which allows one to use the weaker -- but more efficient and often sufficient -- notion of proofs of membership in the UC-framework. We believe that our contributions enable the design of practically efficient protocols that are UC-secure and thus themselves can be used as building blocks. AU - Camenisch, Jan AU - Stephan Krenn AU - Shoup, Victor ED - Lee, Dong Hoon ED - Wang, Xiaoyun ID - 2975 TI - A Framework for Practical Universally Composable Zero-Knowledge Protocols VL - 7073 ER - TY - CONF AB - Cryptographic two-party protocols are used ubiquitously in everyday life. While some of these protocols are easy to understand and implement (e.g., key exchange or transmission of encrypted data), many of them are much more complex (e.g., e-banking and e-voting applications, or anonymous authentication and credential systems). For a software engineer without appropriate cryptographic skills the implementation of such protocols is often difficult, time consuming and error-prone. For this reason, a number of compilers supporting programmers have been published in recent years. However, they are either designed for very specific cryptographic primitives (e.g., zero-knowledge proofs of knowledge), or they only offer a very low level of abstraction and thus again demand substantial mathematical and cryptographic skills from the programmer. Finally, some of the existing compilers do not produce executable code, but only metacode which has to be instantiated with mathematical libraries, encryption routines, etc. before it can actually be used. In this paper we present a cryptographically aware compiler which is equally useful to cryptographers who want to benchmark protocols designed on paper, and to programmers who want to implement complex security sensitive protocols without having to understand all subtleties. Our tool offers a high level of abstraction and outputs well-structured and documented Java code. We believe that our compiler can contribute to shortening the development cycles of cryptographic applications and to reducing their error-proneness. AU - Bangerter, Endre AU - Stephan Krenn AU - Seifriz, Martial AU - Ultes-Nitsche, Ulrich ED - Venter, Hein S. ED - Coetzee, Marijke ED - Loock, Marianne ID - 2977 TI - cPLC - A Cryptographic Programming Language and Compiler ER - TY - CONF AB - Side channel attacks on cryptographic systems exploit information gained from physical implementations rather than theoretical weaknesses of a scheme. In recent years, major achievements were made for the class of so called access-driven cache attacks. Such attacks exploit the leakage of the memory locations accessed by a victim process. In this paper we consider the AES block cipher and present an attack which is capable of recovering the full secret key in almost realtime for AES-128, requiring only a very limited number of observed encryptions. Unlike previous attacks, we do not require any information about the plaintext (such as its distribution, etc.). Moreover, for the first time, we also show how the plaintext can be recovered without having access to the ciphertext at all. It is the first working attack on AES implementations using compressed tables. There, no efficient techniques to identify the beginning of AES rounds is known, which is the fundamental assumption underlying previous attacks. We have a fully working implementation of our attack which is able to recover AES keys after observing as little as 100 encryptions. It works against the OpenSSL 0.9.8n implementation of AES on Linux systems. Our spy process does not require any special privileges beyond those of a standard Linux user. A contribution of probably independent interest is a denial of service attack on the task scheduler of current Linux systems (CFS), which allows one to observe (on average) every single memory access of a victim process. AU - Gullasch, David AU - Bangerter, Endre AU - Stephan Krenn ID - 2976 TI - Cache Games - Bringing Access-Based Cache Attacks on AES to Practice ER - TY - JOUR AB - The phytohormone auxin is vital to plant growth and development. A unique property of auxin among all other plant hormones is its cell-to-cell polar transport that requires activity of polarly localized PIN-FORMED (PIN) auxin efflux transporters. Despite the substantial molecular insight into the cellular PIN polarization, the mechanistic understanding for developmentally and environmentally regulated PIN polarization is scarce. The long-standing belief that auxin modulates its own transport by means of a positive feedback mechanism has inspired both experimentalists and theoreticians for more than two decades. Recently, theoretical models for auxin-dependent patterning in plants include the feedback between auxin transport and the PIN protein localization. These computer models aid to assess the complexity of plant development by testing and predicting plausible scenarios for various developmental processes that occur in planta. Although the majority of these models rely on purely heuristic principles, the most recent mechanistic models tentatively integrate biologically testable components into known cellular processes that underlie the PIN polarity regulation. The existing and emerging computational approaches to describe PIN polarization are presented and discussed in the light of recent experimental data on the PIN polar targeting. AU - Wabnik, Krzysztof T AU - Govaerts, Willy AU - Friml, Jirí AU - Kleine Vehn, Jürgen ID - 3092 IS - 8 JF - Molecular BioSystems TI - Feedback models for polarized auxin transport: An emerging trend VL - 7 ER - TY - JOUR AB - The phytohormone auxin is an important determinant of plant development. Directional auxin flow within tissues depends on polar localization of PIN auxin transporters. To explore regulation of PIN-mediated auxin transport, we screened for suppressors of PIN1 overexpression (supo) and identified an inositol polyphosphate 1-phosphatase mutant (supo1), with elevated inositol trisphosphate (InsP 3) and cytosolic Ca 2+ levels. Pharmacological and genetic increases in InsP 3 or Ca 2+ levels also suppressed the PIN1 gain-of-function phenotypes and caused defects in basal PIN localization, auxin transport and auxin-mediated development. In contrast, the reductions in InsP 3 levels and Ca 2+ signaling antagonized the effects of the supo1 mutation and disrupted preferentially apical PIN localization. InsP 3 and Ca 2+ are evolutionarily conserved second messengers involved in various cellular functions, particularly stress responses. Our findings implicate them as modifiers of cell polarity and polar auxin transport, and highlight a potential integration point through which Ca 2+ signaling-related stimuli could influence auxin-mediated development. AU - Zhang, Jing AU - Vanneste, Steffen AU - Brewer, Philip B AU - Michniewicz, Marta AU - Peter Grones AU - Kleine-Vehn, Jürgen AU - Löfke, Christian AU - Teichmann, Thomas AU - Bielach, Agnieszka AU - Cannoot, Bernard AU - Hoyerová, Klára AU - Xu Chen AU - Xue, Hong-Wei AU - Eva Benková AU - Zažímalová, Eva AU - Jirí Friml ID - 3089 IS - 6 JF - Developmental Cell TI - Inositol trisphosphate-induced ca^2+ signaling modulates auxin transport and pin polarity VL - 20 ER - TY - JOUR AB - The polarized transport of the phytohormone auxin [1], which is crucial for the regulation of different stages of plant development [2, 3], depends on the asymmetric plasma membrane distribution of the PIN-FORMED (PIN) auxin efflux carriers [4, 5]. The PIN polar localization results from clathrin-mediated endocytosis (CME) from the plasma membrane and subsequent polar recycling [6]. The Arabidopsis genome encodes two groups of dynamin-related proteins (DRPs) that show homology to mammalian dynamin - a protein required for fission of endocytic vesicles during CME [7, 8]. Here we show by coimmunoprecipitation (coIP), bimolecular fluorescence complementation (BiFC), and Förster resonance energy transfer (FRET) that members of the DRP1 group closely associate with PIN proteins at the cell plate. Localization and phenotypic analysis of novel drp1 mutants revealed a requirement for DRP1 function in correct PIN distribution and in auxin-mediated development. We propose that rapid and specific internalization of PIN proteins mediated by the DRP1 proteins and the associated CME machinery from the cell plate membranes during cytokinesis is an important mechanism for proper polar PIN positioning in interphase cells. AU - Mravec, Jozef AU - Petrášek, Jan AU - Li, Na AU - Boeren, Sjef AU - Karlova, Rumyana AU - Kitakura, Saeko AU - Pařezová, Markéta AU - Naramoto, Satoshi AU - Nodzyński, Thomasz AU - Dhonukshe, Pankaj AU - Bednarek, Sebastian Y AU - Zažímalová, Eva AU - De Vries, Sacco AU - Jirí Friml ID - 3090 IS - 12 JF - Current Biology TI - Cell plate restricted association of DRP1A and PIN proteins is required for cell polarity establishment in arabidopsis VL - 21 ER - TY - JOUR AB - Background: Whereas the majority of animals develop toward a predetermined body plan, plants show iterative growth and continually produce new organs and structures from actively dividing meristems. This raises an intriguing question: How are these newly developed organs patterned? In Arabidopsis embryos, radial symmetry is broken by the bisymmetric specification of the cotyledons in the apical domain. Subsequently, this bisymmetry is propagated to the root promeristem. Results: Here we present a mutually inhibitory feedback loop between auxin and cytokinin that sets distinct boundaries of hormonal output. Cytokinins promote the bisymmetric distribution of the PIN-FORMED (PIN) auxin efflux proteins, which channel auxin toward a central domain. High auxin promotes transcription of the cytokinin signaling inhibitor AHP6, which closes the interaction loop. This bisymmetric auxin response domain specifies the differentiation of protoxylem in a bisymmetric pattern. In embryonic roots, cytokinin is required to translate a bisymmetric auxin response in the cotyledons to a bisymmetric vascular pattern in the root promeristem. Conclusions: Our results present an interactive feedback loop between hormonal signaling and transport by which small biases in hormonal input are propagated into distinct signaling domains to specify the vascular pattern in the root meristem. It is an intriguing possibility that such a mechanism could transform radial patterns and allow continuous vascular connections between other newly emerging organs. AU - Bishopp, Anthony AU - Help, Hanna AU - El-Showk, Sedeer AU - Weijers, Dolf AU - Scheres, Ben AU - Jirí Friml AU - Eva Benková AU - Mähönen, Ari Pekka AU - Helariutta, Ykä ID - 3088 IS - 11 JF - Current Biology TI - A mutually inhibitory interaction between auxin and cytokinin specifies vascular pattern in roots VL - 21 ER - TY - JOUR AB - Plants take up iron from the soil using the IRON-REGULATED TRANSPORTER 1 (IRT1) high-affinity iron transporter at the root surface. Sophisticated regulatory mechanisms allow plants to tightly control the levels of IRT1, ensuring optimal absorption of essential but toxic iron. Here, we demonstrate that overexpression of Arabidopsis thaliana IRT1 leads to constitutive IRT1 protein accumulation, metal overload, and oxidative stress. IRT1 is unexpectedly found in trans-Golgi network/early endosomes of root hair cells, and its levels and localization are unaffected by iron nutrition. Using pharmacological approaches, we show that IRT1 cycles to the plasma membrane to perform iron and metal uptake at the cell surface and is sent to the vacuole for proper turnover. We also prove that IRT1 is monoubiquitinated on several cytosol-exposed residues in vivo and that mutation of two putative monoubiquitination target residues in IRT1 triggers stabilization at the plasma membrane and leads to extreme lethality. Together, these data suggest a model in which monoubiquitin-dependent internalization/sorting and turnover keep the plasma membrane pool of IRT1 low to ensure proper iron uptake and to prevent metal toxicity. More generally, our work demonstrates the existence of monoubiquitin-dependent trafficking to lytic vacuoles in plants and points to proteasome-independent turnover of plasma membrane proteins. AU - Barberon, Marie AU - Zelazny, Enric AU - Robert, Stéphanie AU - Conéjéro, Geneviève AU - Curie, Cathy AU - Jirí Friml AU - Vert, Grégory ID - 3093 IS - 32 JF - PNAS TI - Monoubiquitin dependent endocytosis of the Iron Regulated Transporter 1 IRT1 transporter controls iron uptake in plants VL - 108 ER - TY - JOUR AB - Summary Gravitropism aligns plant growth with gravity. It involves gravity perception and the asymmetric distribution of the phytohormone auxin. Here we provide insights into the mechanism for hypocotyl gravitropic growth. We show that the Arabidopsis thaliana PIN3 auxin transporter is required for the asymmetric auxin distribution for the gravitropic response. Gravistimulation polarizes PIN3 to the bottom side of hypocotyl endodermal cells, which correlates with an increased auxin response at the lower hypocotyl side. Both PIN3 polarization and hypocotyl bending require the activity of the trafficking regulator GNOM and the protein kinase PINOID. Our data suggest that gravity-induced PIN3 polarization diverts the auxin flow to mediate the asymmetric distribution of auxin for gravitropic shoot bending. AU - Rakusová, Hana AU - Gallego-Bartolomé, Javier AU - Vanstraelen, Marleen AU - Robert, Hélène S AU - Alabadí, David AU - Blázquez, Miguel A AU - Eva Benková AU - Jirí Friml ID - 3094 IS - 5 JF - Plant Journal TI - Polarization of PIN3 dependent auxin transport for hypocotyl gravitropic response in Arabidopsis thaliana VL - 67 ER - TY - JOUR AU - Sauer, Michael AU - Friml, Jirí ID - 3091 JF - Molecular Systems Biology TI - Fleeting hormone cues get stabilized for plant organogenesis VL - 7 ER - TY - JOUR AB - Multicellular organisms depend on cell production, cell fate specification, and correct patterning to shape their adult body. In plants, auxin plays a prominent role in the timely coordination of these different cellular processes. A well-studied example is lateral root initiation, in which auxin triggers founder cell specification and cell cycle activation of xylem pole–positioned pericycle cells. Here, we report that the E2Fa transcription factor of Arabidopsis thaliana is an essential component that regulates the asymmetric cell division marking lateral root initiation. Moreover, we demonstrate that E2Fa expression is regulated by the LATERAL ORGAN BOUNDARY DOMAIN18/LATERAL ORGAN BOUNDARY DOMAIN33 (LBD18/LBD33) dimer that is, in turn, regulated by the auxin signaling pathway. LBD18/LBD33 mediates lateral root organogenesis through E2Fa transcriptional activation, whereas E2Fa expression under control of the LBD18 promoter eliminates the need for LBD18. Besides lateral root initiation, vascular patterning is disrupted in E2Fa knockout plants, similarly as it is affected in auxin signaling and lbd mutants, indicating that the transcriptional induction of E2Fa through LBDs represents a general mechanism for auxin-dependent cell cycle activation. Our data illustrate how a conserved mechanism driving cell cycle entry has been adapted evolutionarily to connect auxin signaling with control of processes determining plant architecture. AU - Berckmans, Barbara AU - Vassileva, Valya AU - Schmid, Stephan P AU - Maes, Sara AU - Parizot, Boris AU - Naramoto, Satoshi AU - Magyar, Zoltan AU - Lessa Alvim Kamei, Claire AU - Koncz, Csaba AU - Bögre, Laszlo AU - Persiau, Geert AU - De Jaeger, Geert AU - Jirí Friml AU - Simon, Rüdiger AU - Beeckman, Tom AU - de Veyldera, Lieven ID - 3102 IS - 10 JF - Plant Cell TI - Auxin Dependent cell cycle reactivation through transcriptional regulation of arabidopsis E2Fa by lateral organ boundary proteins VL - 23 ER - TY - JOUR AB - Endocytosis in plants has an essential role not only for basic cellular functions but also for growth and development, hormonal signaling and communication with the environment including nutrient delivery, toxin avoidance, and pathogen defense. The major endocytic mechanism in plants depends on the coat protein clathrin. It starts by clathrin-coated vesicle formation at the plasma membrane, where specific cargoes are recognized and packaged for internalization. Recently, genetic, biochemical and advanced microscopy studies provided initial insights into mechanisms and roles of clathrin-mediated endocytosis in plants. Here we summarize the present state of knowledge and compare mechanisms of clathrin-mediated endocytosis in plants with animal and yeast paradigms as well as review plant-specific regulations and roles of this process. AU - Chen, Xu AU - Irani, Niloufer AU - Friml, Jirí ID - 3103 IS - 6 JF - Current Opinion in Plant Biology TI - Clathrin-mediated endocytosis: The gateway into plant cells VL - 14 ER - TY - JOUR AB - Cancer cell of origin is difficult to identify by analyzing cells within terminal stage tumors, whose identity could be concealed by the acquired plasticity. Thus, an ideal approach to identify the cell of origin is to analyze proliferative abnormalities in distinct lineages prior to malignancy. Here, we use mosaic analysis with double markers (MADM) in mice to model gliomagenesis by initiating concurrent p53/Nf1 mutations sporadically in neural stem cells (NSCs). Surprisingly, MADM-based lineage tracing revealed significant aberrant growth prior to malignancy only in oligodendrocyte precursor cells (OPCs), but not in any other NSC-derived lineages or NSCs themselves. Upon tumor formation, phenotypic and transcriptome analyses of tumor cells revealed salient OPC features. Finally, introducing the same p53/Nf1 mutations directly into OPCs consistently led to gliomagenesis. Our findings suggest OPCs as the cell of origin in this model, even when initial mutations occur in NSCs, and highlight the importance of analyzing premalignant stages to identify the cancer cell of origin. AU - Liu, Chong AU - Sage, Jonathan C AU - Miller, Michael R AU - Verhaak, Roel G AU - Simon Hippenmeyer AU - Vogel, Hannes AU - Foreman, Oded AU - Bronson, Roderick T AU - Nishiyama, Akiko AU - Luo, Liqun AU - Zong, Hui ID - 3147 IS - 2 JF - Cell TI - Mosaic analysis with double markers reveals tumor cell of origin in glioma VL - 146 ER - TY - CONF AB - We introduce a new class of functions that can be minimized in polynomial time in the value oracle model. These are functions f satisfying f(x) + f(y) ≥ f(x ∏ y) + f(x ∐ y) where the domain of each variable x i corresponds to nodes of a rooted binary tree, and operations ∏,∐ are defined with respect to this tree. Special cases include previously studied L-convex and bisubmodular functions, which can be obtained with particular choices of trees. We present a polynomial-time algorithm for minimizing functions in the new class. It combines Murota's steepest descent algorithm for L-convex functions with bisubmodular minimization algorithms. AU - Vladimir Kolmogorov ID - 3204 TI - Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions VL - 6907 ER - TY - CONF AB - In this paper we address the problem of finding the most probable state of discrete Markov random field (MRF) with associative pairwise terms. Although of practical importance, this problem is known to be NP-hard in general. We propose a new type of MRF decomposition, submod-ular decomposition (SMD). Unlike existing decomposition approaches SMD decomposes the initial problem into sub-problems corresponding to a specific class label while preserving the graph structure of each subproblem. Such decomposition enables us to take into account several types of global constraints in an efficient manner. We study theoretical properties of the proposed approach and demonstrate its applicability on a number of problems. AU - Osokin, Anton AU - Vetrov, Dmitry AU - Vladimir Kolmogorov ID - 3206 TI - Submodular decomposition framework for inference in associative Markov networks with global constraints ER - TY - CONF AB - This paper proposes a novel Linear Programming (LP) based algorithm, called Dynamic Tree-Block Coordinate Ascent (DT-BCA), for performing maximum a posteriori (MAP) inference in probabilistic graphical models. Unlike traditional message passing algorithms, which operate uniformly on the whole factor graph, our method dynamically chooses regions of the factor graph on which to focus message-passing efforts. We propose two criteria for selecting regions, including an efficiently computable upper-bound on the increase in the objective possible by passing messages in any particular region. This bound is derived from the theory of primal-dual methods from combinatorial optimization, and the forest that maximizes the bounds can be chosen efficiently using a maximum-spanning-tree-like algorithm. Experimental results show that our dynamic schedules significantly speed up state-of-the-art LP-based message-passing algorithms on a wide variety of real-world problems. AU - Tarlow, Daniel AU - Batra, Druv AU - Kohli, Pushmeet AU - Vladimir Kolmogorov ID - 3205 TI - Dynamic tree block coordinate ascent ER - TY - CONF AB - Cosegmentation is typically defined as the task of jointly segmenting something similar in a given set of images. Existing methods are too generic and so far have not demonstrated competitive results for any specific task. In this paper we overcome this limitation by adding two new aspects to cosegmentation: (1) the "something" has to be an object, and (2) the "similarity" measure is learned. In this way, we are able to achieve excellent results on the recently introduced iCoseg dataset, which contains small sets of images of either the same object instance or similar objects of the same class. The challenge of this dataset lies in the extreme changes in viewpoint, lighting, and object deformations within each set. We are able to considerably outperform several competitors. To achieve this performance, we borrow recent ideas from object recognition: the use of powerful features extracted from a pool of candidate object-like segmentations. We believe that our work will be beneficial to several application areas, such as image retrieval. AU - Vicente, Sara AU - Rother, Carsten AU - Vladimir Kolmogorov ID - 3207 TI - Object cosegmentation ER - TY - CONF AB - The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two limitations: - Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are ε-close to uniform, one must set v ≤ m - 2log(1/ε), meaning that the entropy loss L = def m - v ≥ 2 log(1/ε). For many applications, such entropy loss is too large. - Large Seed Length: the seed length n of (almost) universal hash function required by the LHL must be at least n ≥ min (u - v, v + 2log(1/ε)) - O(1), where u is the length of the source, and must grow with the number of extracted bits. Quite surprisingly, we show that both limitations of the LHL - large entropy loss and large seed - can be overcome (or, at least, mitigated) in various important scenarios. First, we show that entropy loss could be reduced to L = log(1/ε) for the setting of deriving secret keys for a wide range of cryptographic applications. Specifically, the security of these schemes with an LHL-derived key gracefully degrades from ε to at most ε + √ε2-L. (Notice that, unlike standard LHL, this bound is meaningful even when one extracts more bits than the min-entropy we have!) Based on these results we build a general computational extractor that enjoys low entropy loss and can be used to instantiate a generic key derivation function for any cryptographic application. Second, we study the soundness of the natural expand-then-extract approach, where one uses a pseudorandom generator (PRG) to expand a short "input seed" S into a longer "output seed" S′, and then use the resulting S′ as the seed required by the LHL (or, more generally, by any randomness extractor). We show that, in general, the expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true. Despite that, we show that it is sound either: (1) when extracting a "small" (logarithmic in the security of the PRG) number of bits; or (2) in minicrypt. Implication (2) suggests that the expand-then-extract approach is likely secure when used with "practical" PRGs, despite lacking a reductionist proof of security! © 2011 International Association for Cryptologic Research. AU - Barak, Boaz AU - Dodis, Yevgeniy AU - Krawczyk, Hugo AU - Pereira, Olivier AU - Krzysztof Pietrzak AU - Standaert, François-Xavier AU - Yu, Yu ID - 3240 TI - Leftover hash lemma revisited VL - 6841 ER - TY - CONF AB - Verification of programs with procedures, multi-threaded programs, and higher-order functional programs can be effectively au- tomated using abstraction and refinement schemes that rely on spurious counterexamples for abstraction discovery. The analysis of counterexam- ples can be automated by a series of interpolation queries, or, alterna- tively, as a constraint solving query expressed by a set of recursion free Horn clauses. (A set of interpolation queries can be formulated as a single constraint over Horn clauses with linear dependency structure between the unknown relations.) In this paper we present an algorithm for solving recursion free Horn clauses over a combined theory of linear real/rational arithmetic and uninterpreted functions. Our algorithm performs resolu- tion to deal with the clausal structure and relies on partial solutions to deal with (non-local) instances of functionality axioms. AU - Gupta, Ashutosh AU - Popeea, Corneliu AU - Rybalchenko, Andrey ED - Yang, Hongseok ID - 3264 TI - Solving recursion-free Horn clauses over LI+UIF VL - 7078 ER - TY - CONF AB - We present a joint image segmentation and labeling model (JSL) which, given a bag of figure-ground segment hypotheses extracted at multiple image locations and scales, constructs a joint probability distribution over both the compatible image interpretations (tilings or image segmentations) composed from those segments, and over their labeling into categories. The process of drawing samples from the joint distribution can be interpreted as first sampling tilings, modeled as maximal cliques, from a graph connecting spatially non-overlapping segments in the bag [1], followed by sampling labels for those segments, conditioned on the choice of a particular tiling. We learn the segmentation and labeling parameters jointly, based on Maximum Likelihood with a novel Incremental Saddle Point estimation procedure. The partition function over tilings and labelings is increasingly more accurately approximated by including incorrect configurations that a not-yet-competent model rates probable during learning. We show that the proposed methodologymatches the current state of the art in the Stanford dataset [2], as well as in VOC2010, where 41.7% accuracy on the test set is achieved. AU - Ion, Adrian AU - Carreira, Joao AU - Sminchisescu, Cristian ID - 3266 T2 - NIPS Proceedings TI - Probabilistic joint image segmentation and labeling VL - 24 ER - TY - JOUR AB - The unintentional scattering of light between neighboring surfaces in complex projection environments increases the brightness and decreases the contrast, disrupting the appearance of the desired imagery. To achieve satisfactory projection results, the inverse problem of global illumination must be solved to cancel this secondary scattering. In this paper, we propose a global illumination cancellation method that minimizes the perceptual difference between the desired imagery and the actual total illumination in the resulting physical environment. Using Gauss-Newton and active set methods, we design a fast solver for the bound constrained nonlinear least squares problem raised by the perceptual error metrics. Our solver is further accelerated with a CUDA implementation and multi-resolution method to achieve 1–2 fps for problems with approximately 3000 variables. We demonstrate the global illumination cancellation algorithm with our multi-projector system. Results show that our method preserves the color fidelity of the desired imagery significantly better than previous methods. AU - Sheng, Yu AU - Cutler, Barbara AU - Chen, Chao AU - Nasman, Joshua ID - 3269 IS - 4 JF - Computer Graphics Forum TI - Perceptual global illumination cancellation in complex projection environments VL - 30 ER - TY - JOUR AB - We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We study the problem with different measures: volume, diameter and radius. For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). The latter result leads to the inapproximability of the problem of computing the nonbounding cycle with the smallest volume and computing cycles representing a homology basis with the minimal total volume. As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius. Our work is restricted to homology over the ℤ2 field. AU - Chen, Chao AU - Freedman, Daniel ID - 3267 IS - 3 JF - Discrete & Computational Geometry TI - Hardness results for homology localization VL - 45 ER - TY - CHAP AB - Algebraic topology is generally considered one of the purest subfield of mathematics. However, over the last decade two interesting new lines of research have emerged, one focusing on algorithms for algebraic topology, and the other on applications of algebraic topology in engineering and science. Amongst the new areas in which the techniques have been applied are computer vision and image processing. In this paper, we survey the results of these endeavours. Because algebraic topology is an area of mathematics with which most computer vision practitioners have no experience, we review the machinery behind the theories of homology and persistent homology; our review emphasizes intuitive explanations. In terms of applications to computer vision, we focus on four illustrative problems: shape signatures, natural image statistics, image denoising, and segmentation. Our hope is that this review will stimulate interest on the part of computer vision researchers to both use and extend the tools of this new field. AU - Freedman, Daniel AU - Chen, Chao ID - 3268 T2 - Computer Vision TI - Algebraic topology for computer vision ER - TY - JOUR AB - The zonula adherens (ZA) of epithelial cells is a site of cell-cell adhesion where cellular forces are exerted and resisted. Increasing evidence indicates that E-cadherin adhesion molecules at the ZA serve to sense force applied on the junctions and coordinate cytoskeletal responses to those forces. Efforts to understand the role that cadherins play in mechanotransduction have been limited by the lack of assays to measure the impact of forces on the ZA. In this study we used 4D imaging of GFP-tagged E-cadherin to analyse the movement of the ZA. Junctions in confluent epithelial monolayers displayed prominent movements oriented orthogonal (perpendicular) to the ZA itself. Two components were identified in these movements: a relatively slow unidirectional (translational) component that could be readily fitted by least-squares regression analysis, upon which were superimposed more rapid oscillatory movements. Myosin IIB was a dominant factor responsible for driving the unilateral translational movements. In contrast, frequency spectrum analysis revealed that depletion of Myosin IIA increased the power of the oscillatory movements. This implies that Myosin IIA may serve to dampen oscillatory movements of the ZA. This extends our recent analysis of Myosin II at the ZA to demonstrate that Myosin IIA and Myosin IIB make distinct contributions to junctional movement at the ZA. AU - Smutny, Michael AU - Wu, Selwin AU - Gomez, Guillermo AU - Mangold, Sabine AU - Yap, Alpha AU - Hamilton, Nicholas ID - 3288 IS - 7 JF - PLoS One TI - Multicomponent analysis of junctional movements regulated by Myosin II isoforms at the epithelial zonula adherens VL - 6 ER - TY - JOUR AB - Cationic antimicrobial peptides (CAMPs) selectively target bacterial membranes by electrostatic interactions with negatively charged lipids. It turned out that for inhibition of microbial growth a high CAMP membrane concentration is required, which can be realized by the incorporation of hydrophobic groups within the peptide. Increasing hydrophobicity, however, reduces the CAMP selectivity for bacterial over eukaryotic host membranes, thereby causing the risk of detrimental side-effects. In this study we addressed how cationic amphipathic peptides—in particular a CAMP with Lysine–Leucine–Lysine repeats (termed KLK)—affect the localization and dynamics of molecules in eukaryotic membranes. We found KLK to selectively inhibit the endocytosis of a subgroup of membrane proteins and lipids by electrostatically interacting with negatively charged sialic acid moieties. Ultrastructural characterization revealed the formation of membrane invaginations representing fission or fusion intermediates, in which the sialylated proteins and lipids were immobilized. Experiments on structurally different cationic amphipathic peptides (KLK, 6-MO-LF11-322 and NK14-2) indicated a cooperation of electrostatic and hydrophobic forces that selectively arrest sialylated membrane constituents. AU - Weghuber, Julian AU - Aichinger, Michael C. AU - Brameshuber, Mario AU - Stefan Wieser AU - Verena Ruprecht AU - Plochberger, Birgit AU - Madl, Josef AU - Horner, Andreas AU - Reipert, Siegfried AU - Lohner, Karl AU - Henics, Tamas AU - Schuetz, Gerhard J ID - 3286 IS - 10 JF - Biochimica et Biophysica Acta (BBA) - Biomembranes TI - Cationic amphipathic peptides accumulate sialylated proteins and lipids in the plasma membrane of eukaryotic host cells VL - 1808 ER - TY - JOUR AB - Diffusing membrane constituents are constantly exposed to a variety of forces that influence their stochastic path. Single molecule experiments allow for resolving trajectories at extremely high spatial and temporal accuracy, thereby offering insights into en route interactions of the tracer. In this review we discuss approaches to derive information about the underlying processes, based on single molecule tracking experiments. In particular, we focus on a new versatile way to analyze single molecule diffusion in the absence of a full analytical treatment. The method is based on comprehensive comparison of an experimental data set against the hypothetical outcome of multiple experiments performed on the computer. Since Monte Carlo simulations can be easily and rapidly performed even on state-of-the-art PCs, our method provides a simple way for testing various - even complicated - diffusion models. We describe the new method in detail, and show the applicability on two specific examples: firstly, kinetic rate constants can be derived for the transient interaction of mobile membrane proteins; secondly, residence time and corral size can be extracted for confined diffusion. AU - Ruprecht, Verena AU - Axmann, Markus AU - Wieser, Stefan AU - Schuetz, Gerhard ID - 3287 IS - 8 JF - Current Protein & Peptide Science TI - What can we learn from single molecule trajectories? VL - 12 ER - TY - JOUR AB - Resolving the dynamical interplay of proteins and lipids in the live-cell plasma membrane represents a central goal in current cell biology. Superresolution concepts have introduced a means of capturing spatial heterogeneity at a nanoscopic length scale. Similar concepts for detecting dynamical transitions (superresolution chronoscopy) are still lacking. Here, we show that recently introduced spot-variation fluorescence correlation spectroscopy allows for sensing transient confinement times of membrane constituents at dramatically improved resolution. Using standard diffraction-limited optics, spot-variation fluorescence correlation spectroscopy captures signatures of single retardation events far below the transit time of the tracer through the focal spot. We provide an analytical description of special cases of transient binding of a tracer to pointlike traps, or association of a tracer with nanodomains. The influence of trap mobility and the underlying binding kinetics are quantified. Experimental approaches are suggested that allow for gaining quantitative mechanistic insights into the interaction processes of membrane constituents. AU - Ruprecht, Verena AU - Wieser, Stefan AU - Marguet, Didier AU - Schuetz, Gerhard ID - 3285 IS - 11 JF - Biophysical Journal TI - Spot variation fluorescence correlation spectroscopy allows for superresolution chronoscopy of confinement times in membranes VL - 100 ER - TY - CONF AB - Cloud computing aims to give users virtually unlimited pay-per-use computing resources without the burden of managing the underlying infrastructure. We present a new job execution environment Flextic that exploits scal- able static scheduling techniques to provide the user with a flexible pricing model, such as a tradeoff between dif- ferent degrees of execution speed and execution price, and at the same time, reduce scheduling overhead for the cloud provider. We have evaluated a prototype of Flextic on Amazon EC2 and compared it against Hadoop. For various data parallel jobs from machine learning, im- age processing, and gene sequencing that we considered, Flextic has low scheduling overhead and reduces job du- ration by up to 15% compared to Hadoop, a dynamic cloud scheduler. AU - Henzinger, Thomas A AU - Singh, Anmol AU - Singh, Vasu AU - Wies, Thomas AU - Zufferey, Damien ID - 3302 TI - Static scheduling in clouds ER - TY - CONF AB - The chemical master equation is a differential equation describing the time evolution of the probability distribution over the possible “states” of a biochemical system. The solution of this equation is of interest within the systems biology field ever since the importance of the molec- ular noise has been acknowledged. Unfortunately, most of the systems do not have analytical solutions, and numerical solutions suffer from the course of dimensionality and therefore need to be approximated. Here, we introduce the concept of tail approximation, which retrieves an approximation of the probabilities in the tail of a distribution from the total probability of the tail and its conditional expectation. This approximation method can then be used to numerically compute the solution of the chemical master equation on a subset of the state space, thus fighting the explosion of the state space, for which this problem is renowned. AU - Henzinger, Thomas A AU - Mateescu, Maria ID - 3301 TI - Tail approximation for the chemical master equation ER - TY - CONF AB - We introduce propagation models, a formalism designed to support general and efficient data structures for the transient analysis of biochemical reaction networks. We give two use cases for propagation abstract data types: the uniformization method and numerical integration. We also sketch an implementation of a propagation abstract data type, which uses abstraction to approximate states. AU - Henzinger, Thomas A AU - Mateescu, Maria ID - 3299 TI - Propagation models for computing biochemical reaction networks ER - TY - CONF AB - In addition to being correct, a system should be robust, that is, it should behave reasonably even after receiving unexpected inputs. In this paper, we summarize two formal notions of robustness that we have introduced previously for reactive systems. One of the notions is based on assigning costs for failures on a user-provided notion of incorrect transitions in a specification. Here, we define a system to be robust if a finite number of incorrect inputs does not lead to an infinite number of incorrect outputs. We also give a more refined notion of robustness that aims to minimize the ratio of output failures to input failures. The second notion is aimed at liveness. In contrast to the previous notion, it has no concept of recovery from an error. Instead, it compares the ratio of the number of liveness constraints that the system violates to the number of liveness constraints that the environment violates. AU - Bloem, Roderick AU - Chatterjee, Krishnendu AU - Greimel, Karin AU - Henzinger, Thomas A AU - Jobstmann, Barbara ID - 3316 T2 - 6th IEEE International Symposium on Industrial and Embedded Systems TI - Specification-centered robustness ER - TY - JOUR AB - Parvalbumin is thought to act in a manner similar to EGTA, but how a slow Ca2+ buffer affects nanodomain-coupling regimes at GABAergic synapses is unclear. Direct measurements of parvalbumin concentration and paired recordings in rodent hippocampus and cerebellum revealed that parvalbumin affects synaptic dynamics only when expressed at high levels. Modeling suggests that, in high concentrations, parvalbumin may exert BAPTA-like effects, modulating nanodomain coupling via competition with local saturation of endogenous fixed buffers. AU - Eggermann, Emmanuel AU - Jonas, Peter M ID - 3318 JF - Nature Neuroscience TI - How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses VL - 15 ER - TY - CHAP AB - We study the topology of the Megaparsec Cosmic Web in terms of the scale-dependent Betti numbers, which formalize the topological information content of the cosmic mass distribution. While the Betti numbers do not fully quantify topology, they extend the information beyond conventional cosmological studies of topology in terms of genus and Euler characteristic. The richer information content of Betti numbers goes along the availability of fast algorithms to compute them. For continuous density fields, we determine the scale-dependence of Betti numbers by invoking the cosmologically familiar filtration of sublevel or superlevel sets defined by density thresholds. For the discrete galaxy distribution, however, the analysis is based on the alpha shapes of the particles. These simplicial complexes constitute an ordered sequence of nested subsets of the Delaunay tessellation, a filtration defined by the scale parameter, α. As they are homotopy equivalent to the sublevel sets of the distance field, they are an excellent tool for assessing the topological structure of a discrete point distribution. In order to develop an intuitive understanding for the behavior of Betti numbers as a function of α, and their relation to the morphological patterns in the Cosmic Web, we first study them within the context of simple heuristic Voronoi clustering models. These can be tuned to consist of specific morphological elements of the Cosmic Web, i.e. clusters, filaments, or sheets. To elucidate the relative prominence of the various Betti numbers in different stages of morphological evolution, we introduce the concept of alpha tracks. Subsequently, we address the topology of structures emerging in the standard LCDM scenario and in cosmological scenarios with alternative dark energy content. The evolution of the Betti numbers is shown to reflect the hierarchical evolution of the Cosmic Web. We also demonstrate that the scale-dependence of the Betti numbers yields a promising measure of cosmological parameters, with a potential to help in determining the nature of dark energy and to probe primordial non-Gaussianities. We also discuss the expected Betti numbers as a function of the density threshold for superlevel sets of a Gaussian random field. Finally, we introduce the concept of persistent homology. It measures scale levels of the mass distribution and allows us to separate small from large scale features. Within the context of the hierarchical cosmic structure formation, persistence provides a natural formalism for a multiscale topology study of the Cosmic Web. AU - Van De Weygaert, Rien AU - Vegter, Gert AU - Edelsbrunner, Herbert AU - Jones, Bernard AU - Pranav, Pratyush AU - Park, Changbom AU - Hellwing, Wojciech AU - Eldering, Bob AU - Kruithof, Nico AU - Bos, Patrick AU - Hidding, Johan AU - Feldbrugge, Job AU - Ten Have, Eline AU - Van Engelen, Matti AU - Caroli, Manuel AU - Teillaud, Monique ED - Gavrilova, Marina ED - Tan, Kenneth ED - Mostafavi, Mir ID - 3335 T2 - Transactions on Computational Science XIV TI - Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web VL - 6970 ER - TY - CONF AB - We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance µ in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution shape P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. An alternative algorithm, based purely on rational arithmetic, answers the same deconstruction problem, up to an uncertainty parameter, and its running time depends on the parameter δ (in addition to the other input parameters: n, δ and the radius of the disk). If the input shape is found to be approximable, the rational-arithmetic algorithm also computes an approximate solution shape for the problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution shape P with at most one more vertex than a vertex-minimal one. Our study is motivated by applications from two different domains. However, since the offset operation has numerous uses, we anticipate that the reverse question that we study here will be still more broadly applicable. We present results obtained with our implementation of the rational-arithmetic algorithm. AU - Berberich, Eric AU - Halperin, Dan AU - Kerber, Michael AU - Pogalnikova, Roza ID - 3329 T2 - Proceedings of the twenty-seventh annual symposium on Computational geometry TI - Deconstructing approximate offsets ER - TY - JOUR AB - Given an algebraic hypersurface O in ℝd, how many simplices are necessary for a simplicial complex isotopic to O? We address this problem and the variant where all vertices of the complex must lie on O. We give asymptotically tight worst-case bounds for algebraic plane curves. Our results gradually improve known bounds in higher dimensions; however, the question for tight bounds remains unsolved for d ≥ 3. AU - Kerber, Michael AU - Sagraloff, Michael ID - 3332 IS - 3 JF - Graphs and Combinatorics TI - A note on the complexity of real algebraic hypersurfaces VL - 27 ER - TY - CONF AB - We consider the problem of approximating all real roots of a square-free polynomial f. Given isolating intervals, our algorithm refines each of them to a width at most 2-L, that is, each of the roots is approximated to L bits after the binary point. Our method provides a certified answer for arbitrary real polynomials, only requiring finite approximations of the polynomial coefficient and choosing a suitable working precision adaptively. In this way, we get a correct algorithm that is simple to implement and practically efficient. Our algorithm uses the quadratic interval refinement method; we adapt that method to be able to cope with inaccuracies when evaluating f, without sacrificing its quadratic convergence behavior. We prove a bound on the bit complexity of our algorithm in terms of degree, coefficient size and discriminant. Our bound improves previous work on integer polynomials by a factor of deg f and essentially matches best known theoretical bounds on root approximation which are obtained by very sophisticated algorithms. AU - Kerber, Michael AU - Sagraloff, Michael ID - 3330 TI - Root refinement for real polynomials ER - TY - CONF AB - We report on a generic uni- and bivariate algebraic kernel that is publicly available with CGAL 3.7. It comprises complete, correct, though efficient state-of-the-art implementations on polynomials, roots of polynomial systems, and the support to analyze algebraic curves defined by bivariate polynomials. The kernel design is generic, that is, various number types and substeps can be exchanged. It is accompanied with a ready-to-use interface to enable arrangements induced by algebraic curves, that have already been used as basis for various geometric applications, as arrangements on Dupin cyclides or the triangulation of algebraic surfaces. We present two novel applications: arrangements of rotated algebraic curves and Boolean set operations on polygons bounded by segments of algebraic curves. We also provide experiments showing that our general implementation is competitive and even often clearly outperforms existing implementations that are explicitly tailored for specific types of non-linear curves that are available in CGAL. AU - Berberich, Eric AU - Hemmer, Michael AU - Kerber, Michael ID - 3328 TI - A generic algebraic kernel for non linear geometric applications ER - TY - JOUR AU - Edelsbrunner, Herbert AU - Pach, János AU - Ziegler, Günter ID - 3334 IS - 1 JF - Discrete & Computational Geometry TI - Letter from the new editors-in-chief VL - 45 ER - TY - JOUR AB - Compositional theories are crucial when designing large and complex systems from smaller components. In this work we propose such a theory for synchronous concurrent systems. Our approach follows so-called interface theories, which use game-theoretic interpretations of composition and refinement. These are appropriate for systems with distinct inputs and outputs, and explicit conditions on inputs that must be enforced during composition. Our interfaces model systems that execute in an infinite sequence of synchronous rounds. At each round, a contract must be satisfied. The contract is simply a relation specifying the set of valid input/output pairs. Interfaces can be composed by parallel, serial or feedback composition. A refinement relation between interfaces is defined, and shown to have two main properties: (1) it is preserved by composition, and (2) it is equivalent to substitutability, namely, the ability to replace an interface by another one in any context. Shared refinement and abstraction operators, corresponding to greatest lower and least upper bounds with respect to refinement, are also defined. Input-complete interfaces, that impose no restrictions on inputs, and deterministic interfaces, that produce a unique output for any legal input, are discussed as special cases, and an interesting duality between the two classes is exposed. A number of illustrative examples are provided, as well as algorithms to compute compositions, check refinement, and so on, for finite-state interfaces. AU - Tripakis, Stavros AU - Lickly, Ben AU - Henzinger, Thomas A AU - Lee, Edward ID - 3353 IS - 4 JF - ACM Transactions on Programming Languages and Systems (TOPLAS) TI - A theory of synchronous relational interfaces VL - 33 ER - TY - CONF AB - Byzantine Fault Tolerant (BFT) protocols aim to improve the reliability of distributed systems. They enable systems to tolerate arbitrary failures in a bounded number of nodes. BFT protocols are usually proven correct for certain safety and liveness properties. However, recent studies have shown that the performance of state-of-the-art BFT protocols decreases drastically in the presence of even a single malicious node. This motivates a formal quantitative analysis of BFT protocols to investigate their performance characteristics under different scenarios. We present HyPerf, a new hybrid methodology based on model checking and simulation techniques for evaluating the performance of BFT protocols. We build a transition system corresponding to a BFT protocol and systematically explore the set of behaviors allowed by the protocol. We associate certain timing information with different operations in the protocol, like cryptographic operations and message transmission. After an elaborate state exploration, we use the time information to evaluate the performance characteristics of the protocol using simulation techniques. We integrate our framework in Mace, a tool for building and verifying distributed systems. We evaluate the performance of PBFT using our framework. We describe two different use-cases of our methodology. For the benign operation of the protocol, we use the time information as random variables to compute the probability distribution of the execution times. In the presence of faults, we estimate the worst-case performance of the protocol for various attacks that can be employed by malicious nodes. Our results show the importance of hybrid techniques in systematically analyzing the performance of large-scale systems. AU - Halalai, Raluca AU - Henzinger, Thomas A AU - Singh, Vasu ID - 3355 TI - Quantitative evaluation of BFT protocols ER - TY - CONF AB - A controller for a discrete game with ω-regular objectives requires attention if, intuitively, it requires measuring the state and switching from the current control action. Minimum attention controllers are preferable in modern shared implementations of cyber-physical systems because they produce the least burden on system resources such as processor time or communication bandwidth. We give algorithms to compute minimum attention controllers for ω-regular objectives in imperfect information discrete two-player games. We show a polynomial-time reduction from minimum attention controller synthesis to synthesis of controllers for mean-payoff parity objectives in games of incomplete information. This gives an optimal EXPTIME-complete synthesis algorithm. We show that the minimum attention controller problem is decidable for infinite state systems with finite bisimulation quotients. In particular, the problem is decidable for timed and rectangular automata. AU - Chatterjee, Krishnendu AU - Majumdar, Ritankar ED - Fahrenberg, Uli ED - Tripakis, Stavros ID - 3350 TI - Minimum attention controller synthesis for omega regular objectives VL - 6919 ER - TY - CONF AB - In two-player games on graph, the players construct an infinite path through the game graph and get a reward computed by a payoff function over infinite paths. Over weighted graphs, the typical and most studied payoff functions compute the limit-average or the discounted sum of the rewards along the path. Besides their simple definition, these two payoff functions enjoy the property that memoryless optimal strategies always exist. In an attempt to construct other simple payoff functions, we define a class of payoff functions which compute an (infinite) weighted average of the rewards. This new class contains both the limit-average and the discounted sum functions, and we show that they are the only members of this class which induce memoryless optimal strategies, showing that there is essentially no other simple payoff functions. AU - Chatterjee, Krishnendu AU - Doyen, Laurent AU - Singh, Rohit ED - Owe, Olaf ED - Steffen, Martin ED - Telle, Jan Arne ID - 3351 TI - On memoryless quantitative objectives VL - 6914 ER - TY - JOUR AB - We consider two-player games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine the successor state. We consider ω-regular winning conditions specified as parity objectives. Both players are allowed to use randomization when choosing their moves. We study the computation of the limit-winning set of states, consisting of the states where the sup-inf value of the game for player 1 is 1: in other words, a state is limit-winning if player 1 can ensure a probability of winning arbitrarily close to 1. We show that the limit-winning set can be computed in O(n2d+2) time, where n is the size of the game structure and 2d is the number of priorities (or colors). The membership problem of whether a state belongs to the limit-winning set can be decided in NP ∩ coNP. While this complexity is the same as for the simpler class of turn-based parity games, where in each state only one of the two players has a choice of moves, our algorithms are considerably more involved than those for turn-based games. This is because concurrent games do not satisfy two of the most fundamental properties of turn-based parity games. First, in concurrent games limit-winning strategies require randomization; and second, they require infinite memory. AU - Chatterjee, Krishnendu AU - De Alfaro, Luca AU - Henzinger, Thomas A ID - 3354 IS - 4 JF - ACM Transactions on Computational Logic (TOCL) TI - Qualitative concurrent parity games VL - 12 ER -