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 - In the last decade, induced pluripotent stem (iPS) cells have revolutionized the utility of human in vitro models of neurological disease. The iPS-derived and differentiated cells allow researchers to study the impact of a distinct cell type in health and disease as well as performing therapeutic drug screens on a human genetic background. In particular, clinical trials for Alzheimer's disease (AD) have been often failing. Two of the potential reasons are first, the species gap involved in proceeding from initial discoveries in rodent models to human studies, and second, an unsatisfying patient stratification, meaning subgrouping patients based on the disease severity due to the lack of phenotypic and genetic markers. iPS cells overcome this obstacles and will improve our understanding of disease subtypes in AD. They allow researchers conducting in depth characterization of neural cells from both familial and sporadic AD patients as well as preclinical screens on human cells.
In this review, we briefly outline the status quo of iPS cell research in neurological diseases along with the general advantages and pitfalls of these models. We summarize how genome-editing techniques such as CRISPR/Cas will allow researchers to reduce the problem of genomic variability inherent to human studies, followed by recent iPS cell studies relevant to AD. We then focus on current techniques for the differentiation of iPS cells into neural cell types that are relevant to AD research. Finally, we discuss how the generation of three-dimensional cell culture systems will be important for understanding AD phenotypes in a complex cellular milieu, and how both two- and three-dimensional iPS cell models can provide platforms for drug discovery and translational studies into the treatment of AD.
AU - Mungenast, Alison
AU - Siegert, Sandra
AU - Tsai, Li
ID - 1613
JF - Molecular and Cellular Neuroscience
TI - Modeling Alzheimer's disease with human induced pluripotent stem (iPS) cells
VL - 73
ER -
TY - JOUR
AB - The hippocampus plays a key role in learning and memory. Previous studies suggested that the main types of principal neurons, dentate gyrus granule cells (GCs), CA3 pyramidal neurons, and CA1 pyramidal neurons, differ in their activity pattern, with sparse firing in GCs and more frequent firing in CA3 and CA1 pyramidal neurons. It has been assumed but never shown that such different activity may be caused by differential synaptic excitation. To test this hypothesis, we performed high-resolution whole-cell patch-clamp recordings in anesthetized rats in vivo. In contrast to previous in vitro data, both CA3 and CA1 pyramidal neurons fired action potentials spontaneously, with a frequency of ∼3–6 Hz, whereas GCs were silent. Furthermore, both CA3 and CA1 cells primarily fired in bursts. To determine the underlying mechanisms, we quantitatively assessed the frequency of spontaneous excitatory synaptic input, the passive membrane properties, and the active membrane characteristics. Surprisingly, GCs showed comparable synaptic excitation to CA3 and CA1 cells and the highest ratio of excitation versus hyperpolarizing inhibition. Thus, differential synaptic excitation is not responsible for differences in firing. Moreover, the three types of hippocampal neurons markedly differed in their passive properties. While GCs showed the most negative membrane potential, CA3 pyramidal neurons had the highest input resistance and the slowest membrane time constant. The three types of neurons also differed in the active membrane characteristics. GCs showed the highest action potential threshold, but displayed the largest gain of the input-output curves. In conclusion, our results reveal that differential firing of the three main types of hippocampal principal neurons in vivo is not primarily caused by differences in the characteristics of the synaptic input, but by the distinct properties of synaptic integration and input-output transformation.
AU - Kowalski, Janina
AU - Gan, Jian
AU - Jonas, Peter M
AU - Pernia-Andrade, Alejandro
ID - 1616
IS - 5
JF - Hippocampus
TI - Intrinsic membrane properties determine hippocampal differential firing pattern in vivo in anesthetized rats
VL - 26
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 - 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 - We introduce a modification of the classic notion of intrinsic volume using persistence moments of height functions. Evaluating the modified first intrinsic volume on digital approximations of a compact body with smoothly embedded boundary in Rn, we prove convergence to the first intrinsic volume of the body as the resolution of the approximation improves. We have weaker results for the other modified intrinsic volumes, proving they converge to the corresponding intrinsic volumes of the n-dimensional unit ball.
AU - Edelsbrunner, Herbert
AU - Pausinger, Florian
ID - 1662
JF - Advances in Mathematics
TI - Approximation and convergence of the intrinsic volume
VL - 287
ER -
TY - JOUR
AB - We introduce a scheme for preparation, manipulation, and read out of Majorana zero modes in semiconducting wires with mesoscopic superconducting islands. Our approach synthesizes recent advances in materials growth with tools commonly used in quantum-dot experiments, including gate control of tunnel barriers and Coulomb effects, charge sensing, and charge pumping. We outline a sequence of milestones interpolating between zero-mode detection and quantum computing that includes (1) detection of fusion rules for non-Abelian anyons using either proximal charge sensors or pumped current, (2) validation of a prototype topological qubit, and (3) demonstration of non-Abelian statistics by braiding in a branched geometry. The first two milestones require only a single wire with two islands, and additionally enable sensitive measurements of the system\'s excitation gap, quasiparticle poisoning rates, residual Majorana zero-mode splittings, and topological-qubit coherence times. These pre-braiding experiments can be adapted to other manipulation and read out schemes as well.
AU - Aasen, David
AU - Hell, Michael
AU - Mishmash, Ryan
AU - Higginbotham, Andrew P
AU - Danon, Jeroen
AU - Leijnse, Martin
AU - Jespersen, Thomas
AU - Folk, Joshua
AU - Marcs, Charles
AU - Flensberg, Karsten
AU - Alicea, Jason
ID - 100
IS - 3
JF - Physical Review X
TI - Milestones toward Majorana-based quantum computing
VL - 6
ER -
TY - JOUR
AB - Majorana zero modes are quasiparticle excitations in condensed matter systems that have been proposed as building blocks of fault-tolerant quantum computers. They are expected to exhibit non-Abelian particle statistics, in contrast to the usual statistics of fermions and bosons, enabling quantum operations to be performed by braiding isolated modes around one another. Quantum braiding operations are topologically protected insofar as these modes are pinned near zero energy, with the departure from zero expected to be exponentially small as the modes become spatially separated. Following theoretical proposals, several experiments have identified signatures of Majorana modes in nanowires with proximity-induced superconductivity and atomic chains, with small amounts of mode splitting potentially explained by hybridization of Majorana modes. Here, we use Coulomb-blockade spectroscopy in an InAs nanowire segment with epitaxial aluminium, which forms a proximity-induced superconducting Coulomb island (a â ∼ Majorana islandâ (tm)) that is isolated from normal-metal leads by tunnel barriers, to measure the splitting of near-zero-energy Majorana modes. We observe exponential suppression of energy splitting with increasing wire length. For short devices of a few hundred nanometres, sub-gap state energies oscillate as the magnetic field is varied, as is expected for hybridized Majorana modes. Splitting decreases by a factor of about ten for each half a micrometre of increased wire length. For devices longer than about one micrometre, transport in strong magnetic fields occurs through a zero-energy state that is energetically isolated from a continuum, yielding uniformly spaced Coulomb-blockade conductance peaks, consistent with teleportation via Majorana modes. Our results help to explain the trivial-to-topological transition in finite systems and to quantify the scaling of topological protection with end-mode separation.
AU - Albrecht, S M
AU - Higginbotham, Andrew P
AU - Jespersen, Thomas
AU - Madsen, Morten
AU - Kuemmeth, Ferdinand
AU - Nygård, Jesper
AU - Krogstrup, Peter
AU - Marcus, Charles
ID - 101
IS - 7593
JF - Nature
TI - Exponential protection of zero modes in Majorana islands
VL - 531
ER -
TY - JOUR
AB - Recent experiments have produced mounting evidence of Majorana zero modes in nanowire-superconductor hybrids. Signatures of an expected topological phase transition accompanying the onset of these modes nevertheless remain elusive. We investigate a fundamental question concerning this issue: Do well-formed Majorana modes necessarily entail a sharp phase transition in these setups? Assuming reasonable parameters, we argue that finite-size effects can dramatically smooth this putative transition into a crossover, even in systems large enough to support well-localized Majorana modes. We propose overcoming such finite-size effects by examining the behavior of low-lying excited states through tunneling spectroscopy. In particular, the excited-state energies exhibit characteristic field and density dependence, and scaling with system size, that expose an approaching topological phase transition. We suggest several experiments for extracting the predicted behavior. As a useful byproduct, the protocols also allow one to measure the wire's spin-orbit coupling directly in its superconducting environment.
AU - Mishmash, Ryan
AU - Aasen, David
AU - Higginbotham, Andrew P
AU - Alicea, Jason
ID - 102
IS - 24
JF - Physical Review B
TI - Approaching a topological phase transition in Majorana nanowires
VL - 93
ER -
TY - CONF
AB - Games on graphs provide the appropriate framework to study several central problems in computer science, such as verification and synthesis of reactive systems. One of the most basic objectives for games on graphs is the liveness (or Büchi) objective that given a target set of vertices requires that some vertex in the target set is visited infinitely often. We study generalized Büchi objectives (i.e., conjunction of liveness objectives), and implications between two generalized Büchi objectives (known as GR(1) objectives), that arise in numerous applications in computer-aided verification. We present improved algorithms and conditional super-linear lower bounds based on widely believed assumptions about the complexity of (A1) combinatorial Boolean matrix multiplication and (A2) CNF-SAT. We consider graph games with n vertices, m edges, and generalized Büchi objectives with k conjunctions. First, we present an algorithm with running time O(k*n^2), improving the previously known O(k*n*m) and O(k^2*n^2) worst-case bounds. Our algorithm is optimal for dense graphs under (A1). Second, we show that the basic algorithm for the problem is optimal for sparse graphs when the target sets have constant size under (A2). Finally, we consider GR(1) objectives, with k_1 conjunctions in the antecedent and k_2 conjunctions in the consequent, and present an O(k_1 k_2 n^{2.5})-time algorithm, improving the previously known O(k_1*k_2*n*m)-time algorithm for m > n^{1.5}.
AU - Chatterjee, Krishnendu
AU - Dvorák, Wolfgang
AU - Henzinger, Monika
AU - Loitzenbauer, Veronika
ID - 1068
TI - Conditionally optimal algorithms for generalized Büchi Games
VL - 58
ER -
TY - CONF
AB - The Continuous Skolem Problem asks whether a real-valued function satisfying a linear differen-
tial equation has a zero in a given interval of real numbers. This is a fundamental reachability
problem for continuous linear dynamical systems, such as linear hybrid automata and continuous-
time Markov chains. Decidability of the problem is currently open – indeed decidability is open
even for the sub-problem in which a zero is sought in a bounded interval. In this paper we show
decidability of the bounded problem subject to Schanuel’s Conjecture, a unifying conjecture in
transcendental number theory. We furthermore analyse the unbounded problem in terms of the
frequencies of the differential equation, that is, the imaginary parts of the characteristic roots.
We show that the unbounded problem can be reduced to the bounded problem if there is at most
one rationally linearly independent frequency, or if there are two rationally linearly independent
frequencies and all characteristic roots are simple. We complete the picture by showing that de-
cidability of the unbounded problem in the case of two (or more) rationally linearly independent
frequencies would entail a major new effectiveness result in Diophantine approximation, namely
computability of the Diophantine-approximation types of all real algebraic numbers.
AU - Chonev, Ventsislav K
AU - Ouaknine, Joël
AU - Worrell, James
ID - 1069
TI - On the skolem problem for continuous linear dynamical systems
VL - 55
ER -
TY - CONF
AB - We present a logic that extends CTL (Computation Tree Logic) with operators that express synchronization properties. A property is synchronized in a system if it holds in all paths of a certain length. The new logic is obtained by using the same path quantifiers and temporal operators as in CTL, but allowing a different order of the quantifiers. This small syntactic variation induces a logic that can express non-regular properties for which known extensions of MSO with equality of path length are undecidable. We show that our variant of CTL is decidable and that the model-checking problem is in Delta_3^P = P^{NP^NP}, and is DP-hard. We analogously consider quantifier exchange in extensions of CTL, and we present operators defined using basic operators of CTL* that express the occurrence of infinitely many synchronization points. We show that the model-checking problem remains in Delta_3^P. The distinguishing power of CTL and of our new logic coincide if the Next operator is allowed in the logics, thus the classical bisimulation quotient can be used for state-space reduction before model checking.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
ID - 1070
TI - Computation tree logic for synchronization properties
VL - 55
ER -
TY - CONF
AB - We consider data-structures for answering reachability and distance queries on constant-treewidth graphs with n nodes, on the standard RAM computational model with wordsize W=Theta(log n). Our first contribution is a data-structure that after O(n) preprocessing time, allows (1) pair reachability queries in O(1) time; and (2) single-source reachability queries in O(n/log n) time. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries. The data-structure uses at all times O(n) space. Our second contribution is a space-time tradeoff data-structure for distance queries. For any epsilon in [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n^{1-\epsilon} alpha(n)) time, where alpha is the inverse of the Ackermann function, and at all times uses O(n^epsilon) space. The input graph G is not considered in the space complexity.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Pavlogiannis, Andreas
ID - 1071
TI - Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs
VL - 57
ER -
TY - JOUR
AB - The asymmetric localization of proteins in the plasma membrane domains of eukaryotic cells is a fundamental manifestation of cell polarity that is central to multicellular organization and developmental patterning. In plants, the mechanisms underlying the polar localization of cargo proteins are still largely unknown and appear to be fundamentally distinct from those operating in mammals. Here, we present a systematic, quantitative comparative analysis of the polar delivery and subcellular localization of proteins that characterize distinct polar plasma membrane domains in plant cells. The combination of microscopic analyses and computational modeling revealed a mechanistic framework common to diverse polar cargos and underlying the establishment and maintenance of apical, basal, and lateral polar domains in plant cells. This mechanism depends on the polar secretion, constitutive endocytic recycling, and restricted lateral diffusion of cargos within the plasma membrane. Moreover, our observations suggest that polar cargo distribution involves the individual protein potential to form clusters within the plasma membrane and interact with the extracellular matrix. Our observations provide insights into the shared cellular mechanisms of polar cargo delivery and polarity maintenance in plant cells.
AU - Łangowski, Łukasz
AU - Wabnik, Krzysztof T
AU - Li, Hongjiang
AU - Vanneste, Steffen
AU - Naramoto, Satoshi
AU - Tanaka, Hirokazu
AU - Friml, Jirí
ID - 1081
JF - Cell Discovery
TI - Cellular mechanisms for cargo delivery and polarity maintenance at different polar domains in plant cells
VL - 2
ER -
TY - CONF
AB - In many applications, it is desirable to extract only the relevant aspects of data. A principled way to do this is the information bottleneck (IB) method, where one seeks a code that maximises information about a relevance variable, Y, while constraining the information encoded about the original data, X. Unfortunately however, the IB method is computationally demanding when data are high-dimensional and/or non-gaussian. Here we propose an approximate variational scheme for maximising a lower bound on the IB objective, analogous to variational EM. Using this method, we derive an IB algorithm to recover features that are both relevant and sparse. Finally, we demonstrate how kernelised versions of the algorithm can be used to address a broad range of problems with non-linear relation between X and Y.
AU - Chalk, Matthew J
AU - Marre, Olivier
AU - Tkacik, Gasper
ID - 1082
TI - Relevant sparse codes with variational information bottleneck
VL - 29
ER -
TY - CONF
AB - While weighted automata provide a natural framework to express quantitative properties, many basic properties like average response time cannot be expressed with weighted automata. Nested weighted automata extend weighted automata and consist of a master automaton and a set of slave automata that are invoked by the master automaton. Nested weighted automata are strictly more expressive than weighted automata (e.g., average response time can be expressed with nested weighted automata), but the basic decision questions have higher complexity (e.g., for deterministic automata, the emptiness question for nested weighted automata is PSPACE-hard, whereas the corresponding complexity for weighted automata is PTIME). We consider a natural subclass of nested weighted automata where at any point at most a bounded number k of slave automata can be active. We focus on automata whose master value function is the limit average. We show that these nested weighted automata with bounded width are strictly more expressive than weighted automata (e.g., average response time with no overlapping requests can be expressed with bound k=1, but not with non-nested weighted automata). We show that the complexity of the basic decision problems (i.e., emptiness and universality) for the subclass with k constant matches the complexity for weighted automata. Moreover, when k is part of the input given in unary we establish PSPACE-completeness.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 1090
TI - Nested weighted limit-average automata of bounded width
VL - 58
ER -
TY - CONF
AB - We introduce a general class of distances (metrics) between Markov chains, which are based on linear behaviour. This class encompasses distances given topologically (such as the total variation distance or trace distance) as well as by temporal logics or automata. We investigate which of the distances can be approximated by observing the systems, i.e. by black-box testing or simulation, and we provide both negative and positive results.
AU - Daca, Przemyslaw
AU - Henzinger, Thomas A
AU - Kretinsky, Jan
AU - Petrov, Tatjana
ID - 1093
TI - Linear distances between Markov chains
VL - 59
ER -
TY - CONF
AB - The semantics of concurrent data structures is usually given by a sequential specification and a consistency condition. Linearizability is the most popular consistency condition due to its simplicity and general applicability. Nevertheless, for applications that do not require all guarantees offered by linearizability, recent research has focused on improving performance and scalability of concurrent data structures by relaxing their semantics. In this paper, we present local linearizability, a relaxed consistency condition that is applicable to container-type concurrent data structures like pools, queues, and stacks. While linearizability requires that the effect of each operation is observed by all threads at the same time, local linearizability only requires that for each thread T, the effects of its local insertion operations and the effects of those removal operations that remove values inserted by T are observed by all threads at the same time. We investigate theoretical and practical properties of local linearizability and its relationship to many existing consistency conditions. We present a generic implementation method for locally linearizable data structures that uses existing linearizable data structures as building blocks. Our implementations show performance and scalability improvements over the original building blocks and outperform the fastest existing container-type implementations.
AU - Haas, Andreas
AU - Henzinger, Thomas A
AU - Holzer, Andreas
AU - Kirsch, Christoph
AU - Lippautz, Michael
AU - Payer, Hannes
AU - Sezgin, Ali
AU - Sokolova, Ana
AU - Veith, Helmut
ID - 1095
T2 - Leibniz International Proceedings in Informatics
TI - Local linearizability for concurrent container-type data structures
VL - 59
ER -
TY - CONF
AB - We present an interactive system for computational design, optimization, and fabrication of multicopters. Our computational approach allows non-experts to design, explore, and evaluate a wide range of different multicopters. We provide users with an intuitive interface for assembling a multicopter from a collection of components (e.g., propellers, motors, and carbon fiber rods). Our algorithm interactively optimizes shape and controller parameters of the current design to ensure its proper operation. In addition, we allow incorporating a variety of other metrics (such as payload, battery usage, size, and cost) into the design process and exploring tradeoffs between them. We show the efficacy of our method and system by designing, optimizing, fabricating, and operating multicopters with complex geometries and propeller configurations. We also demonstrate the ability of our optimization algorithm to improve the multicopter performance under different metrics.
AU - Du, Tao
AU - Schulz, Adriana
AU - Zhu, Bo
AU - Bickel, Bernd
AU - Matusik, Wojciech
ID - 1097
IS - 6
TI - Computational multicopter design
VL - 35
ER -
TY - CONF
AB - Better understanding of the potential benefits of information transfer and representation learning is an important step towards the goal of building intelligent systems that are able to persist in the world and learn over time. In this work, we consider a setting where the learner encounters a stream of tasks but is able to retain only limited information from each encountered task, such as a learned predictor. In contrast to most previous works analyzing this scenario, we do not make any distributional assumptions on the task generating process. Instead, we formulate a complexity measure that captures the diversity of the observed tasks. We provide a lifelong learning algorithm with error guarantees for every observed task (rather than on average). We show sample complexity reductions in comparison to solving every task in isolation in terms of our task complexity measure. Further, our algorithmic framework can naturally be viewed as learning a representation from encountered tasks with a neural network.
AU - Pentina, Anastasia
AU - Urner, Ruth
ID - 1098
TI - Lifelong learning with weighted majority votes
VL - 29
ER -
TY - CONF
AB - We present FlexMolds, a novel computational approach to automatically design flexible, reusable molds that, once 3D printed, allow us to physically fabricate, by means of liquid casting, multiple copies of complex shapes with rich surface details and complex topology. The approach to design such flexible molds is based on a greedy bottom-up search of possible cuts over an object, evaluating for each possible cut the feasibility of the resulting mold. We use a dynamic simulation approach to evaluate candidate molds, providing a heuristic to generate forces that are able to open, detach, and remove a complex mold from the object it surrounds. We have tested the approach with a number of objects with nontrivial shapes and topologies.
AU - Malomo, Luigi
AU - Pietroni, Nico
AU - Bickel, Bernd
AU - Cignoni, Paolo
ID - 1099
IS - 6
TI - FlexMolds: Automatic design of flexible shells for molding
VL - 35
ER -
TY - CONF
AB - Weakly-supervised object localization methods tend to fail for object classes that consistently co-occur with the same background elements, e.g. trains on tracks. We propose a method to overcome these failures by adding a very small amount of model-specific additional annotation. The main idea is to cluster a deep network\'s mid-level representations and assign object or distractor labels to each cluster. Experiments show substantially improved localization results on the challenging ILSVC2014 dataset for bounding box detection and the PASCAL VOC2012 dataset for semantic segmentation.
AU - Kolesnikov, Alexander
AU - Lampert, Christoph
ID - 1102
T2 - Proceedings of the British Machine Vision Conference 2016
TI - Improving weakly-supervised object localization by micro-annotation
VL - 2016-September
ER -
TY - CONF
AB - We propose two parallel state-space-exploration algorithms for hybrid automaton (HA), with the goal of enhancing performance on multi-core shared-memory systems. The first uses the parallel, breadth-first-search algorithm (PBFS) of the SPIN model checker, when traversing the discrete modes of the HA, and enhances it with a parallel exploration of the continuous states within each mode. We show that this simple-minded extension of PBFS does not provide the desired load balancing in many HA benchmarks. The second algorithm is a task-parallel BFS algorithm (TP-BFS), which uses a cheap precomputation of the cost associated with the post operations (both continuous and discrete) in order to improve load balancing. We illustrate the TP-BFS and the cost precomputation of the post operators on a support-function-based algorithm for state-space exploration. The performance comparison of the two algorithms shows that, in general, TP-BFS provides a better utilization/load-balancing of the CPU. Both algorithms are implemented in the model checker XSpeed. Our experiments show a maximum speed-up of more than 2000 χ on a navigation benchmark, with respect to SpaceEx LGG scenario. In order to make the comparison fair, we employed an equal number of post operations in both tools. To the best of our knowledge, this paper represents the first attempt to provide parallel, reachability-analysis algorithms for HA.
AU - Gurung, Amit
AU - Deka, Arup
AU - Bartocci, Ezio
AU - Bogomolov, Sergiy
AU - Grosu, Radu
AU - Ray, Rajarshi
ID - 1103
TI - Parallel reachability analysis for hybrid systems
ER -
TY - CONF
AB - We present a coherent microwave to telecom signal converter based on the electro-optical effect using a crystalline WGM-resonator coupled to a 3D microwave cavity, achieving high photon conversion efficiency of 0.1% with MHz bandwidth.
AU - Rueda, Alfredo
AU - Sedlmeir, Florian
AU - Collodo, Michele
AU - Vogl, Ulrich
AU - Stiller, Birgit
AU - Schunk, Georg
AU - Strekalov, Dimitry
AU - Marquardt, Christoph
AU - Fink, Johannes M
AU - Painter, Oskar
AU - Leuchs, Gerd
AU - Schwefel, Harald
ID - 1115
TI - Efficient single sideband microwave to optical conversion using a LiNbO inf 3 inf WGM-resonator
ER -
TY - THES
AB - Computer graphics is an extremely exciting field for two reasons. On the one hand,
there is a healthy injection of pragmatism coming from the visual effects industry
that want robust algorithms that work so they can produce results at an increasingly
frantic pace. On the other hand, they must always try to push the envelope and
achieve the impossible to wow their audiences in the next blockbuster, which means
that the industry has not succumb to conservatism, and there is plenty of room to
try out new and crazy ideas if there is a chance that it will pan into something
useful.
Water simulation has been in visual effects for decades, however it still remains
extremely challenging because of its high computational cost and difficult artdirectability.
The work in this thesis tries to address some of these difficulties.
Specifically, we make the following three novel contributions to the state-of-the-art
in water simulation for visual effects.
First, we develop the first algorithm that can convert any sequence of closed
surfaces in time into a moving triangle mesh. State-of-the-art methods at the time
could only handle surfaces with fixed connectivity, but we are the first to be able to
handle surfaces that merge and split apart. This is important for water simulation
practitioners, because it allows them to convert splashy water surfaces extracted
from particles or simulated using grid-based level sets into triangle meshes that can
be either textured and enhanced with extra surface dynamics as a post-process.
We also apply our algorithm to other phenomena that merge and split apart, such
as morphs and noisy reconstructions of human performances.
Second, we formulate a surface-based energy that measures the deviation of a
water surface froma physically valid state. Such discrepancies arise when there is a
mismatch in the degrees of freedom between the water surface and the underlying
physics solver. This commonly happens when practitioners use a moving triangle
mesh with a grid-based physics solver, or when high-resolution grid-based surfaces
are combined with low-resolution physics. Following the direction of steepest
descent on our surface-based energy, we can either smooth these artifacts or turn
them into high-resolution waves by interpreting the energy as a physical potential.
Third, we extend state-of-the-art techniques in non-reflecting boundaries to handle spatially and time-varying background flows. This allows a novel new
workflow where practitioners can re-simulate part of an existing simulation, such
as removing a solid obstacle, adding a new splash or locally changing the resolution.
Such changes can easily lead to new waves in the re-simulated region that would
reflect off of the new simulation boundary, effectively ruining the illusion of a
seamless simulation boundary between the existing and new simulations. Our
non-reflecting boundaries makes sure that such waves are absorbed.
AU - Bojsen-Hansen, Morten
ID - 1122
TI - Tracking, correcting and absorbing water surface waves
ER -
TY - THES
AB - Traditionally machine learning has been focusing on the problem of solving a single
task in isolation. While being quite well understood, this approach disregards an
important aspect of human learning: when facing a new problem, humans are able to
exploit knowledge acquired from previously learned tasks. Intuitively, access to several
problems simultaneously or sequentially could also be advantageous for a machine
learning system, especially if these tasks are closely related. Indeed, results of many
empirical studies have provided justification for this intuition. However, theoretical
justifications of this idea are rather limited.
The focus of this thesis is to expand the understanding of potential benefits of information
transfer between several related learning problems. We provide theoretical
analysis for three scenarios of multi-task learning - multiple kernel learning, sequential
learning and active task selection. We also provide a PAC-Bayesian perspective on
lifelong learning and investigate how the task generation process influences the generalization
guarantees in this scenario. In addition, we show how some of the obtained
theoretical results can be used to derive principled multi-task and lifelong learning
algorithms and illustrate their performance on various synthetic and real-world datasets.
AU - Pentina, Anastasia
ID - 1126
TI - Theoretical foundations of multi-task lifelong learning
ER -
TY - THES
AB - The process of gene expression is central to the modern understanding of how cellular systems
function. In this process, a special kind of regulatory proteins, called transcription factors,
are important to determine how much protein is produced from a given gene. As biological
information is transmitted from transcription factor concentration to mRNA levels to amounts of
protein, various sources of noise arise and pose limits to the fidelity of intracellular signaling.
This thesis concerns itself with several aspects of stochastic gene expression: (i) the mathematical
description of complex promoters responsible for the stochastic production of biomolecules,
(ii) fundamental limits to information processing the cell faces due to the interference from multiple
fluctuating signals, (iii) how the presence of gene expression noise influences the evolution
of regulatory sequences, (iv) and tools for the experimental study of origins and consequences
of cell-cell heterogeneity, including an application to bacterial stress response systems.
AU - Rieckh, Georg
ID - 1128
TI - Studying the complexities of transcriptional regulation
ER -
TY - CONF
AB - Time-triggered (TT) switched networks are a deterministic communication infrastructure used by real-time distributed embedded systems. These networks rely on the notion of globally discretized time (i.e. time slots) and a static TT schedule that prescribes which message is sent through which link at every time slot, such that all messages reach their destination before a global timeout. These schedules are generated offline, assuming a static network with fault-free links, and entrusting all error-handling functions to the end user. Assuming the network is static is an over-optimistic view, and indeed links tend to fail in practice. We study synthesis of TT schedules on a network in which links fail over time and we assume the switches run a very simple error-recovery protocol once they detect a crashed link. We address the problem of finding a pk; qresistant schedule; namely, one that, assuming the switches run a fixed error-recovery protocol, guarantees that the number of messages that arrive at their destination by the timeout is at least no matter what sequence of at most k links fail. Thus, we maintain the simplicity of the switches while giving a guarantee on the number of messages that meet the timeout. We show how a pk; q-resistant schedule can be obtained using a CEGAR-like approach: find a schedule, decide whether it is pk; q-resistant, and if it is not, use the witnessing fault sequence to generate a constraint that is added to the program. The newly added constraint disallows the schedule to be regenerated in a future iteration while also eliminating several other schedules that are not pk; q-resistant. We illustrate the applicability of our approach using an SMT-based implementation. © 2016 ACM.
AU - Avni, Guy
AU - Guha, Shibashis
AU - Rodríguez Navas, Guillermo
ID - 1135
T2 - Proceedings of the 13th International Conference on Embedded Software
TI - Synthesizing time triggered schedules for switched networks with faulty links
ER -
TY - CONF
AB - We propose an interactive sculpting system for seamlessly editing pre-computed animations of liquid, without the need for any resimulation. The input is a sequence of meshes without correspondences representing the liquid surface over time. Our method enables the efficient selection of consistent space-time parts of this animation, such as moving waves or droplets, which we call space-time features. Once selected, a feature can be copied, edited, or duplicated and then pasted back anywhere in space and time in the same or in another liquid animation sequence. Our method circumvents tedious user interactions by automatically computing the spatial and temporal ranges of the selected feature. We also provide space-time shape editing tools for non-uniform scaling, rotation, trajectory changes, and temporal editing to locally speed up or slow down motion. Using our tools, the user can edit and progressively refine any input simulation result, possibly using a library of precomputed space-time features extracted from other animations. In contrast to the trial-and-error loop usually required to edit animation results through the tuning of indirect simulation parameters, our method gives the user full control over the edited space-time behaviors. © 2016 Copyright held by the owner/author(s).
AU - Manteaux, Pierre
AU - Vimont, Ulysse
AU - Wojtan, Christopher J
AU - Rohmer, Damien
AU - Cani, Marie
ID - 1136
T2 - Proceedings of the 9th International Conference on Motion in Games
TI - Space-time sculpting of liquid animation
ER -
TY - JOUR
AB - RASGRP1 is an important guanine nucleotide exchange factor and activator of the RAS-MAPK pathway following T cell antigen receptor (TCR) signaling. The consequences of RASGRP1 mutations in humans are unknown. In a patient with recurrent bacterial and viral infections, born to healthy consanguineous parents, we used homozygosity mapping and exome sequencing to identify a biallelic stop-gain variant in RASGRP1. This variant segregated perfectly with the disease and has not been reported in genetic databases. RASGRP1 deficiency was associated in T cells and B cells with decreased phosphorylation of the extracellular-signal-regulated serine kinase ERK, which was restored following expression of wild-type RASGRP1. RASGRP1 deficiency also resulted in defective proliferation, activation and motility of T cells and B cells. RASGRP1-deficient natural killer (NK) cells exhibited impaired cytotoxicity with defective granule convergence and actin accumulation. Interaction proteomics identified the dynein light chain DYNLL1 as interacting with RASGRP1, which links RASGRP1 to cytoskeletal dynamics. RASGRP1-deficient cells showed decreased activation of the GTPase RhoA. Treatment with lenalidomide increased RhoA activity and reversed the migration and activation defects of RASGRP1-deficient lymphocytes.
AU - Salzer, Elisabeth
AU - Çaǧdaş, Deniz
AU - Hons, Miroslav
AU - Mace, Emily
AU - Garncarz, Wojciech
AU - Petronczki, Oezlem
AU - Platzer, René
AU - Pfajfer, Laurène
AU - Bilic, Ivan
AU - Ban, Sol
AU - Willmann, Katharina
AU - Mukherjee, Malini
AU - Supper, Verena
AU - Hsu, Hsiangting
AU - Banerjee, Pinaki
AU - Sinha, Papiya
AU - Mcclanahan, Fabienne
AU - Zlabinger, Gerhard
AU - Pickl, Winfried
AU - Gribben, John
AU - Stockinger, Hannes
AU - Bennett, Keiryn
AU - Huppa, Johannes
AU - Dupré, Loï̈C
AU - Sanal, Özden
AU - Jäger, Ulrich
AU - Sixt, Michael K
AU - Tezcan, Ilhan
AU - Orange, Jordan
AU - Boztug, Kaan
ID - 1137
IS - 12
JF - Nature Immunology
TI - RASGRP1 deficiency causes immunodeficiency with impaired cytoskeletal dynamics
VL - 17
ER -
TY - CONF
AB - Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions, we establish that automata with monitor counters and nested weighted automata are equivalent. We study for the first time such quantitative automata under probabilistic semantics. We show that several problems that are undecidable for the classical questions of emptiness and universality become decidable under the probabilistic semantics. We present a complete picture of decidability for such automata, and even an almost-complete picture of computational complexity, for the probabilistic questions we consider. © 2016 ACM.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Otop, Jan
ID - 1138
T2 - Proceedings of the 31st Annual ACM/IEEE Symposium
TI - Quantitative automata under probabilistic semantics
ER -
TY - CONF
AB - Given a model of a system and an objective, the model-checking question asks whether the model satisfies the objective. We study polynomial-time problems in two classical models, graphs and Markov Decision Processes (MDPs), with respect to several fundamental -regular objectives, e.g., Rabin and Streett objectives. For many of these problems the best-known upper bounds are quadratic or cubic, yet no super-linear lower bounds are known. In this work our contributions are two-fold: First, we present several improved algorithms, and second, we present the first conditional super-linear lower bounds based on widely believed assumptions about the complexity of CNF-SAT and combinatorial Boolean matrix multiplication. A separation result for two models with respect to an objective means a conditional lower bound for one model that is strictly higher than the existing upper bound for the other model, and similarly for two objectives with respect to a model. Our results establish the following separation results: (1) A separation of models (graphs and MDPs) for disjunctive queries of reachability and Büchi objectives. (2) Two kinds of separations of objectives, both for graphs and MDPs, namely, (2a) the separation of dual objectives such as Streett/Rabin objectives, and (2b) the separation of conjunction and disjunction of multiple objectives of the same type such as safety, Büchi, and coBüchi. In summary, our results establish the first model and objective separation results for graphs and MDPs for various classical -regular objectives. Quite strikingly, we establish conditional lower bounds for the disjunction of objectives that are strictly higher than the existing upper bounds for the conjunction of the same objectives. © 2016 ACM.
AU - Chatterjee, Krishnendu
AU - Dvoák, Wolfgang
AU - Henzinger, Monika
AU - Loitzenbauer, Veronika
ID - 1140
T2 - Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science
TI - Model and objective separation with conditional lower bounds disjunction is harder than conjunction
ER -
TY - JOUR
AB - Hemolysis drives susceptibility to bacterial infections and predicts poor outcome from sepsis. These detrimental effects are commonly considered to be a consequence of heme-iron serving as a nutrient for bacteria. We employed a Gram-negative sepsis model and found that elevated heme levels impaired the control of bacterial proliferation independently of heme-iron acquisition by pathogens. Heme strongly inhibited phagocytosis and the migration of human and mouse phagocytes by disrupting actin cytoskeletal dynamics via activation of the GTP-binding Rho family protein Cdc42 by the guanine nucleotide exchange factor DOCK8. A chemical screening approach revealed that quinine effectively prevented heme effects on the cytoskeleton, restored phagocytosis and improved survival in sepsis. These mechanistic insights provide potential therapeutic targets for patients with sepsis or hemolytic disorders.
AU - Martins, Rui
AU - Maier, Julia
AU - Gorki, Anna
AU - Huber, Kilian
AU - Sharif, Omar
AU - Starkl, Philipp
AU - Saluzzo, Simona
AU - Quattrone, Federica
AU - Gawish, Riem
AU - Lakovits, Karin
AU - Aichinger, Michael
AU - Radic Sarikas, Branka
AU - Lardeau, Charles
AU - Hladik, Anastasiya
AU - Korosec, Ana
AU - Brown, Markus
AU - Vaahtomeri, Kari
AU - Duggan, Michelle
AU - Kerjaschki, Dontscho
AU - Esterbauer, Harald
AU - Colinge, Jacques
AU - Eisenbarth, Stephanie
AU - Decker, Thomas
AU - Bennett, Keiryn
AU - Kubicek, Stefan
AU - Sixt, Michael K
AU - Superti Furga, Giulio
AU - Knapp, Sylvia
ID - 1142
IS - 12
JF - Nature Immunology
TI - Heme drives hemolysis-induced susceptibility to infection via disruption of phagocyte functions
VL - 17
ER -
TY - JOUR
AB - We study the ground state of a dilute Bose gas in a scaling limit where the Gross-Pitaevskii functional emerges. This is a repulsive nonlinear Schrödinger functional whose quartic term is proportional to the scattering length of the interparticle interaction potential. We propose a new derivation of this limit problem, with a method that bypasses some of the technical difficulties that previous derivations had to face. The new method is based on a combination of Dyson\'s lemma, the quantum de Finetti theorem and a second moment estimate for ground states of the effective Dyson Hamiltonian. It applies equally well to the case where magnetic fields or rotation are present.
AU - Nam, Phan
AU - Rougerie, Nicolas
AU - Seiringer, Robert
ID - 1143
IS - 2
JF - Analysis and PDE
TI - Ground states of large bosonic systems: The gross Pitaevskii limit revisited
VL - 9
ER -
TY - JOUR
AB - Auxin directs plant ontogenesis via differential accumulation within tissues depending largely on the activity of PIN proteins that mediate auxin efflux from cells and its directional cell-to-cell transport. Regardless of the developmental importance of PINs, the structure of these transporters is poorly characterized. Here, we present experimental data concerning protein topology of plasma membrane-localized PINs. Utilizing approaches based on pH-dependent quenching of fluorescent reporters combined with immunolocalization techniques, we mapped the membrane topology of PINs and further cross-validated our results using available topology modeling software. We delineated the topology of PIN1 with two transmembrane (TM) bundles of five α-helices linked by a large intracellular loop and a C-terminus positioned outside the cytoplasm. Using constraints derived from our experimental data, we also provide an updated position of helical regions generating a verisimilitude model of PIN1. Since the canonical long PINs show a high degree of conservation in TM domains and auxin transport capacity has been demonstrated for Arabidopsis representatives of this group, this empirically enhanced topological model of PIN1 will be an important starting point for further studies on PIN structure–function relationships. In addition, we have established protocols that can be used to probe the topology of other plasma membrane proteins in plants. © 2016 The Authors
AU - Nodzyński, Tomasz
AU - Vanneste, Steffen
AU - Zwiewka, Marta
AU - Pernisová, Markéta
AU - Hejátko, Jan
AU - Friml, Jirí
ID - 1145
IS - 11
JF - Molecular Plant
TI - Enquiry into the topology of plasma membrane localized PIN auxin transport components
VL - 9
ER -
TY - JOUR
AB - Apical dominance is one of the fundamental developmental phenomena in plant biology, which determines the overall architecture of aerial plant parts. Here we show apex decapitation activated competition for dominance in adjacent upper and lower axillary buds. A two-nodal-bud pea (Pisum sativum L.) was used as a model system to monitor and assess auxin flow, auxin transport channels, and dormancy and initiation status of axillary buds. Auxin flow was manipulated by lateral stem wounds or chemically by auxin efflux inhibitors 2,3,5-triiodobenzoic acid (TIBA), 1-N-naphtylphtalamic acid (NPA), or protein synthesis inhibitor cycloheximide (CHX) treatments, which served to interfere with axillary bud competition. Redirecting auxin flow to different points influenced which bud formed the outgrowing and dominant shoot. The obtained results proved that competition between upper and lower axillary buds as secondary auxin sources is based on the same auxin canalization principle that operates between the shoot apex and axillary bud. © The Author(s) 2016.
AU - Balla, Jozef
AU - Medved'Ová, Zuzana
AU - Kalousek, Petr
AU - Matiješčuková, Natálie
AU - Friml, Jirí
AU - Reinöhl, Vilém
AU - Procházka, Stanislav
ID - 1147
JF - Scientific Reports
TI - Auxin flow mediated competition between axillary buds to restore apical dominance
VL - 6
ER -
TY - JOUR
AB - Tissue patterning in multicellular organisms is the output of precise spatio–temporal regulation of gene expression coupled with changes in hormone dynamics. In plants, the hormone auxin regulates growth and development at every stage of a plant’s life cycle. Auxin signaling occurs through binding of the auxin molecule to a TIR1/AFB F-box ubiquitin ligase, allowing interaction with Aux/IAA transcriptional repressor proteins. These are subsequently ubiquitinated and degraded via the 26S proteasome, leading to derepression of auxin response factors (ARFs). How auxin is able to elicit such a diverse range of developmental responses through a single signaling module has not yet been resolved. Here we present an alternative auxin-sensing mechanism in which the ARF ARF3/ETTIN controls gene expression through interactions with process-specific transcription factors. This noncanonical hormonesensing mechanism exhibits strong preference for the naturally occurring auxin indole 3-acetic acid (IAA) and is important for coordinating growth and patterning in diverse developmental contexts such as gynoecium morphogenesis, lateral root emergence, ovule development, and primary branch formation. Disrupting this IAA-sensing ability induces morphological aberrations with consequences for plant fitness. Therefore, our findings introduce a novel transcription factor-based mechanism of hormone perception in plants. © 2016 Simonini et al.
AU - Simonini, Sara
AU - Deb, Joyita
AU - Moubayidin, Laila
AU - Stephenson, Pauline
AU - Valluru, Manoj
AU - Freire Rios, Alejandra
AU - Sorefan, Karim
AU - Weijers, Dolf
AU - Friml, Jirí
AU - Östergaard, Lars
ID - 1151
IS - 20
JF - Genes and Development
TI - A noncanonical auxin sensing mechanism is required for organ morphogenesis in arabidopsis
VL - 30
ER -
TY - JOUR
AB - Differential cell growth enables flexible organ bending in the presence of environmental signals such as light or gravity. A prominent example of the developmental processes based on differential cell growth is the formation of the apical hook that protects the fragile shoot apical meristem when it breaks through the soil during germination. Here, we combined in silico and in vivo approaches to identify a minimal mechanism producing auxin gradient-guided differential growth during the establishment of the apical hook in the model plant Arabidopsis thaliana. Computer simulation models based on experimental data demonstrate that asymmetric expression of the PIN-FORMED auxin efflux carrier at the concave (inner) versus convex (outer) side of the hook suffices to establish an auxin maximum in the epidermis at the concave side of the apical hook. Furthermore, we propose a mechanism that translates this maximum into differential growth, and thus curvature, of the apical hook. Through a combination of experimental and in silico computational approaches, we have identified the individual contributions of differential cell elongation and proliferation to defining the apical hook and reveal the role of auxin-ethylene crosstalk in balancing these two processes. © 2016 American Society of Plant Biologists. All rights reserved.
AU - Žádníková, Petra
AU - Wabnik, Krzysztof T
AU - Abuzeineh, Anas
AU - Gallemí, Marçal
AU - Van Der Straeten, Dominique
AU - Smith, Richard
AU - Inze, Dirk
AU - Friml, Jirí
AU - Prusinkiewicz, Przemysław
AU - Benková, Eva
ID - 1153
IS - 10
JF - Plant Cell
TI - A model of differential growth guided apical hook formation in plants
VL - 28
ER -
TY - JOUR
AB - Cellular locomotion is a central hallmark of eukaryotic life. It is governed by cell-extrinsic molecular factors, which can either emerge in the soluble phase or as immobilized, often adhesive ligands. To encode for direction, every cue must be present as a spatial or temporal gradient. Here, we developed a microfluidic chamber that allows measurement of cell migration in combined response to surface immobilized and soluble molecular gradients. As a proof of principle we study the response of dendritic cells to their major guidance cues, chemokines. The majority of data on chemokine gradient sensing is based on in vitro studies employing soluble gradients. Despite evidence suggesting that in vivo chemokines are often immobilized to sugar residues, limited information is available how cells respond to immobilized chemokines. We tracked migration of dendritic cells towards immobilized gradients of the chemokine CCL21 and varying superimposed soluble gradients of CCL19. Differential migratory patterns illustrate the potential of our setup to quantitatively study the competitive response to both types of gradients. Beyond chemokines our approach is broadly applicable to alternative systems of chemo- and haptotaxis such as cells migrating along gradients of adhesion receptor ligands vs. any soluble cue.
AU - Schwarz, Jan
AU - Bierbaum, Veronika
AU - Merrin, Jack
AU - Frank, Tino
AU - Hauschild, Robert
AU - Bollenbach, Mark Tobias
AU - Tay, Savaş
AU - Sixt, Michael K
AU - Mehling, Matthias
ID - 1154
JF - Scientific Reports
TI - A microfluidic device for measuring cell migration towards substrate bound and soluble chemokine gradients
VL - 6
ER -
TY - JOUR
AB - We consider sample covariance matrices of the form Q = ( σ1/2X)(σ1/2X)∗, where the sample X is an M ×N random matrix whose entries are real independent random variables with variance 1/N and whereσ is an M × M positive-definite deterministic matrix. We analyze the asymptotic fluctuations of the largest rescaled eigenvalue of Q when both M and N tend to infinity with N/M →d ϵ (0,∞). For a large class of populations σ in the sub-critical regime, we show that the distribution of the largest rescaled eigenvalue of Q is given by the type-1 Tracy-Widom distribution under the additional assumptions that (1) either the entries of X are i.i.d. Gaussians or (2) that σ is diagonal and that the entries of X have a sub-exponential decay.
AU - Lee, Ji
AU - Schnelli, Kevin
ID - 1157
IS - 6
JF - Annals of Applied Probability
TI - Tracy-widom distribution for the largest eigenvalue of real sample covariance matrices with general population
VL - 26
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 - CONF
AB - We show that c-planarity is solvable in quadratic time for flat clustered graphs with three clusters if the combinatorial embedding of the underlying graph is fixed. In simpler graph-theoretical terms our result can be viewed as follows. Given a graph G with the vertex set partitioned into three parts embedded on a 2-sphere, our algorithm decides if we can augment G by adding edges without creating an edge-crossing so that in the resulting spherical graph the vertices of each part induce a connected sub-graph. We proceed by a reduction to the problem of testing the existence of a perfect matching in planar bipartite graphs. We formulate our result in a slightly more general setting of cyclic clustered graphs, i.e., the simple graph obtained by contracting each cluster, where we disregard loops and multi-edges, is a cycle.
AU - Fulek, Radoslav
ID - 1165
TI - C-planarity of embedded cyclic c-graphs
VL - 9801
ER -
TY - JOUR
AB - A central issue in cell biology is the physico-chemical basis of organelle biogenesis in intracellular trafficking pathways, its most impressive manifestation being the biogenesis of Golgi cisternae. At a basic level, such morphologically and chemically distinct compartments should arise from an interplay between the molecular transport and chemical maturation. Here, we formulate analytically tractable, minimalist models, that incorporate this interplay between transport and chemical progression in physical space, and explore the conditions for de novo biogenesis of distinct cisternae. We propose new quantitative measures that can discriminate between the various models of transport in a qualitative manner-this includes measures of the dynamics in steady state and the dynamical response to perturbations of the kind amenable to live-cell imaging.
AU - Sachdeva, Himani
AU - Barma, Mustansir
AU - Rao, Madan
ID - 1172
JF - Scientific Reports
TI - Nonequilibrium description of de novo biogenesis and transport through Golgi-like cisternae
VL - 6
ER -
TY - JOUR
AB - Boldyreva, Palacio and Warinschi introduced a multiple forking game as an extension of general forking. The notion of (multiple) forking is a useful abstraction from the actual simulation of cryptographic scheme to the adversary in a security reduction, and is achieved through the intermediary of a so-called wrapper algorithm. Multiple forking has turned out to be a useful tool in the security argument of several cryptographic protocols. However, a reduction employing multiple forking incurs a significant degradation of (Formula presented.) , where (Formula presented.) denotes the upper bound on the underlying random oracle calls and (Formula presented.) , the number of forkings. In this work we take a closer look at the reasons for the degradation with a tighter security bound in mind. We nail down the exact set of conditions for success in the multiple forking game. A careful analysis of the cryptographic schemes and corresponding security reduction employing multiple forking leads to the formulation of ‘dependence’ and ‘independence’ conditions pertaining to the output of the wrapper in different rounds. Based on the (in)dependence conditions we propose a general framework of multiple forking and a General Multiple Forking Lemma. Leveraging (in)dependence to the full allows us to improve the degradation factor in the multiple forking game by a factor of (Formula presented.). By implication, the cost of a single forking involving two random oracles (augmented forking) matches that involving a single random oracle (elementary forking). Finally, we study the effect of these observations on the concrete security of existing schemes employing multiple forking. We conclude that by careful design of the protocol (and the wrapper in the security reduction) it is possible to harness our observations to the full extent.
AU - Kamath Hosdurg, Chethan
AU - Chatterjee, Sanjit
ID - 1177
IS - 4
JF - Algorithmica
TI - A closer look at multiple-forking: Leveraging (in)dependence for a tighter bound
VL - 74
ER -
TY - CONF
AB - Computational notions of entropy have recently found many applications, including leakage-resilient cryptography, deterministic encryption or memory delegation. The two main types of results which make computational notions so useful are (1) Chain rules, which quantify by how much the computational entropy of a variable decreases if conditioned on some other variable (2) Transformations, which quantify to which extend one type of entropy implies another.
Such chain rules and transformations typically lose a significant amount in quality of the entropy, and are the reason why applying these results one gets rather weak quantitative security bounds. In this paper we for the first time prove lower bounds in this context, showing that existing results for transformations are, unfortunately, basically optimal for non-adaptive black-box reductions (and it’s hard to imagine how non black-box reductions or adaptivity could be useful here.)
A variable X has k bits of HILL entropy of quality (ϵ,s)
if there exists a variable Y with k bits min-entropy which cannot be distinguished from X with advantage ϵ
by distinguishing circuits of size s. A weaker notion is Metric entropy, where we switch quantifiers, and only require that for every distinguisher of size s, such a Y exists.
We first describe our result concerning transformations. By definition, HILL implies Metric without any loss in quality. Metric entropy often comes up in applications, but must be transformed to HILL for meaningful security guarantees. The best known result states that if a variable X has k bits of Metric entropy of quality (ϵ,s)
, then it has k bits of HILL with quality (2ϵ,s⋅ϵ2). We show that this loss of a factor Ω(ϵ−2)
in circuit size is necessary. In fact, we show the stronger result that this loss is already necessary when transforming so called deterministic real valued Metric entropy to randomised boolean Metric (both these variants of Metric entropy are implied by HILL without loss in quality).
The chain rule for HILL entropy states that if X has k bits of HILL entropy of quality (ϵ,s)
, then for any variable Z of length m, X conditioned on Z has k−m bits of HILL entropy with quality (ϵ,s⋅ϵ2/2m). We show that a loss of Ω(2m/ϵ) in circuit size necessary here. Note that this still leaves a gap of ϵ between the known bound and our lower bound.
AU - Pietrzak, Krzysztof Z
AU - Maciej, Skorski
ID - 1179
TI - Pseudoentropy: Lower-bounds for chain rules and transformations
VL - 9985
ER -
TY - CONF
AB - Balanced knockout tournaments are ubiquitous in sports competitions and are also used in decisionmaking and elections. The traditional computational question, that asks to compute a draw (optimal draw) that maximizes the winning probability for a distinguished player, has received a lot of attention. Previous works consider the problem where the pairwise winning probabilities are known precisely, while we study how robust is the winning probability with respect to small errors in the pairwise winning probabilities. First, we present several illuminating examples to establish: (a) there exist deterministic tournaments (where the pairwise winning probabilities are 0 or 1) where one optimal draw is much more robust than the other; and (b) in general, there exist tournaments with slightly suboptimal draws that are more robust than all the optimal draws. The above examples motivate the study of the computational problem of robust draws that guarantee a specified winning probability. Second, we present a polynomial-time algorithm for approximating the robustness of a draw for sufficiently small errors in pairwise winning probabilities, and obtain that the stated computational problem is NP-complete. We also show that two natural cases of deterministic tournaments where the optimal draw could be computed in polynomial time also admit polynomial-time algorithms to compute robust optimal draws.
AU - Chatterjee, Krishnendu
AU - Ibsen-Jensen, Rasmus
AU - Tkadlec, Josef
ID - 1182
TI - Robust draws in balanced knockout tournaments
VL - 2016-January
ER -