TY - CONF
AB - When designing genetic circuits, the typical primitives used in major existing modelling formalisms are gene interaction graphs, where edges between genes denote either an activation or inhibition relation. However, when designing experiments, it is important to be precise about the low-level mechanistic details as to how each such relation is implemented. The rule-based modelling language Kappa allows to unambiguously specify mechanistic details such as DNA binding sites, dimerisation of transcription factors, or co-operative interactions. Such a detailed description comes with complexity and computationally costly executions. We propose a general method for automatically transforming a rule-based program, by eliminating intermediate species and adjusting the rate constants accordingly. To the best of our knowledge, we show the first automated reduction of rule-based models based on equilibrium approximations.
Our algorithm is an adaptation of an existing algorithm, which was designed for reducing reaction-based programs; our version of the algorithm scans the rule-based Kappa model in search for those interaction patterns known to be amenable to equilibrium approximations (e.g. Michaelis-Menten scheme). Additional checks are then performed in order to verify if the reduction is meaningful in the context of the full model. The reduced model is efficiently obtained by static inspection over the rule-set. The tool is tested on a detailed rule-based model of a λ-phage switch, which lists 92 rules and 13 agents. The reduced model has 11 rules and 5 agents, and provides a dramatic reduction in simulation time of several orders of magnitude.
AU - Beica, Andreea
AU - Guet, Calin C
AU - Petrov, Tatjana
ID - 1524
TI - Efficient reduction of kappa models by static inspection of the rule-set
VL - 9271
ER -
TY - CONF
AB - We present the first study of robustness of systems that are both timed as well as reactive (I/O). We study the behavior of such timed I/O systems in the presence of uncertain inputs and formalize their robustness using the analytic notion of Lipschitz continuity: a timed I/O system is K-(Lipschitz) robust if the perturbation in its output is at most K times the perturbation in its input. We quantify input and output perturbation using similarity functions over timed words such as the timed version of the Manhattan distance and the Skorokhod distance. We consider two models of timed I/O systems — timed transducers and asynchronous sequential circuits. We show that K-robustness of timed transducers can be decided in polynomial space under certain conditions. For asynchronous sequential circuits, we reduce K-robustness w.r.t. timed Manhattan distances to K-robustness of discrete letter-to-letter transducers and show PSpace-completeness of the problem.
AU - Henzinger, Thomas A
AU - Otop, Jan
AU - Samanta, Roopsha
ID - 1526
TI - Lipschitz robustness of timed I/O systems
VL - 9583
ER -
TY - JOUR
AB - We consider partially observable Markov decision processes (POMDPs) with a set of target states and an integer cost associated with every transition. The optimization objective we study asks to minimize the expected total cost of reaching a state in the target set, while ensuring that the target set is reached almost surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost, both double exponential in the POMDP state space size; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we also present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Gupta, Raghav
AU - Kanodia, Ayush
ID - 1529
JF - Artificial Intelligence
TI - Optimal cost almost-sure reachability in POMDPs
VL - 234
ER -
TY - JOUR
AB - We provide general conditions for which bosonic quadratic Hamiltonians on Fock spaces can be diagonalized by Bogoliubov transformations. Our results cover the case when quantum systems have infinite degrees of freedom and the associated one-body kinetic and paring operators are unbounded. Our sufficient conditions are optimal in the sense that they become necessary when the relevant one-body operators commute.
AU - Nam, Phan
AU - Napiórkowski, Marcin M
AU - Solovej, Jan
ID - 1545
IS - 11
JF - Journal of Functional Analysis
TI - Diagonalization of bosonic quadratic Hamiltonians by Bogoliubov transformations
VL - 270
ER -
TY - JOUR
AB - Antibiotic resistance carries a fitness cost that must be overcome in order for resistance to persist over the long term. Compensatory mutations that recover the functional defects associated with resistance mutations have been argued to play a key role in overcoming the cost of resistance, but compensatory mutations are expected to be rare relative to generally beneficial mutations that increase fitness, irrespective of antibiotic resistance. Given this asymmetry, population genetics theory predicts that populations should adapt by compensatory mutations when the cost of resistance is large, whereas generally beneficial mutations should drive adaptation when the cost of resistance is small. We tested this prediction by determining the genomic mechanisms underpinning adaptation to antibiotic-free conditions in populations of the pathogenic bacterium Pseudomonas aeruginosa that carry costly antibiotic resistance mutations. Whole-genome sequencing revealed that populations founded by high-cost rifampicin-resistant mutants adapted via compensatory mutations in three genes of the RNA polymerase core enzyme, whereas populations founded by low-cost mutants adapted by generally beneficial mutations, predominantly in the quorum-sensing transcriptional regulator gene lasR. Even though the importance of compensatory evolution in maintaining resistance has been widely recognized, our study shows that the roles of general adaptation in maintaining resistance should not be underestimated and highlights the need to understand how selection at other sites in the genome influences the dynamics of resistance alleles in clinical settings.
AU - Qi, Qin
AU - Toll Riera, Macarena
AU - Heilbron, Karl
AU - Preston, Gail
AU - Maclean, R Craig
ID - 1552
IS - 1822
JF - Proceedings of the Royal Society of London Series B Biological Sciences
TI - The genomic basis of adaptation to the fitness cost of rifampicin resistance in Pseudomonas aeruginosa
VL - 283
ER -
TY - JOUR
AB - The addition of polysialic acid to N- and/or O-linked glycans, referred to as polysialylation, is a rare posttranslational modification that is mainly known to control the developmental plasticity of the nervous system. Here we show that CCR7, the central chemokine receptor controlling immune cell trafficking to secondary lymphatic organs, carries polysialic acid. This modification is essential for the recognition of the CCR7 ligand CCL21. As a consequence, dendritic cell trafficking is abrogated in polysialyltransferase-deficient mice, manifesting as disturbed lymph node homeostasis and unresponsiveness to inflammatory stimuli. Structure-function analysis of chemokine-receptor interactions reveals that CCL21 adopts an autoinhibited conformation, which is released upon interaction with polysialic acid. Thus, we describe a glycosylation-mediated immune cell trafficking disorder and its mechanistic basis.
AU - Kiermaier, Eva
AU - Moussion, Christine
AU - Veldkamp, Christopher
AU - Gerardy Schahn, Rita
AU - De Vries, Ingrid
AU - Williams, Larry
AU - Chaffee, Gary
AU - Phillips, Andrew
AU - Freiberger, Friedrich
AU - Imre, Richard
AU - Taleski, Deni
AU - Payne, Richard
AU - Braun, Asolina
AU - Förster, Reinhold
AU - Mechtler, Karl
AU - Mühlenhoff, Martina
AU - Volkman, Brian
AU - Sixt, Michael K
ID - 1599
IS - 6269
JF - Science
TI - Polysialylation controls dendritic cell trafficking by regulating chemokine recognition
VL - 351
ER -
TY - JOUR
AB - We show that the Anderson model has a transition from localization to delocalization at exactly 2 dimensional growth rate on antitrees with normalized edge weights which are certain discrete graphs. The kinetic part has a one-dimensional structure allowing a description through transfer matrices which involve some Schur complement. For such operators we introduce the notion of having one propagating channel and extend theorems from the theory of one-dimensional Jacobi operators that relate the behavior of transfer matrices with the spectrum. These theorems are then applied to the considered model. In essence, in a certain energy region the kinetic part averages the random potentials along shells and the transfer matrices behave similar as for a one-dimensional operator with random potential of decaying variance. At d dimensional growth for d>2 this effective decay is strong enough to obtain absolutely continuous spectrum, whereas for some uniform d dimensional growth with d<2 one has pure point spectrum in this energy region. At exactly uniform 2 dimensional growth also some singular continuous spectrum appears, at least at small disorder. As a corollary we also obtain a change from singular spectrum (d≤2) to absolutely continuous spectrum (d≥3) for random operators of the type rΔdr+λ on ℤd, where r is an orthogonal radial projection, Δd the discrete adjacency operator (Laplacian) on ℤd and λ a random potential.
AU - Sadel, Christian
ID - 1608
IS - 7
JF - Annales Henri Poincare
TI - Anderson transition at 2 dimensional growth rate on antitrees and spectral theory for operators with one propagating channel
VL - 17
ER -
TY - JOUR
AB - We prove that whenever A is a 3-conservative relational structure with only binary and unary relations,then the algebra of polymorphisms of A either has no Taylor operation (i.e.,CSP(A)is NP-complete),or it generates an SD(∧) variety (i.e.,CSP(A)has bounded width).
AU - Kazda, Alexandr
ID - 1612
IS - 1
JF - Algebra Universalis
TI - CSP for binary conservative relational structures
VL - 75
ER -
TY - JOUR
AB - 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 - 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 -