TY - JOUR
AB - We introduce a new method for deriving the time-dependent Hartree or Hartree-Fock equations as an effective mean-field dynamics from the microscopic Schrödinger equation for fermionic many-particle systems in quantum mechanics. The method is an adaption of the method used in Pickl (Lett. Math. Phys. 97 (2) 151–164 2011) for bosonic systems to fermionic systems. It is based on a Gronwall type estimate for a suitable measure of distance between the microscopic solution and an antisymmetrized product state. We use this method to treat a new mean-field limit for fermions with long-range interactions in a large volume. Some of our results hold for singular attractive or repulsive interactions. We can also treat Coulomb interaction assuming either a mild singularity cutoff or certain regularity conditions on the solutions to the Hartree(-Fock) equations. In the considered limit, the kinetic and interaction energy are of the same order, while the average force is subleading. For some interactions, we prove that the Hartree(-Fock) dynamics is a more accurate approximation than a simpler dynamics that one would expect from the subleading force. With our method we also treat the mean-field limit coupled to a semiclassical limit, which was discussed in the literature before, and we recover some of the previous results. All results hold for initial data close (but not necessarily equal) to antisymmetrized product states and we always provide explicit rates of convergence.
AU - Petrat, Sören P
AU - Pickl, Peter
ID - 1493
IS - 1
JF - Mathematical Physics, Analysis and Geometry
TI - A new method and a new scaling for deriving fermionic mean-field dynamics
VL - 19
ER -
TY - JOUR
AB - The two-photon 1s2 2s 2p 3P0 1s22s2 1S0 transition in berylliumlike ions is theoretically investigated within a fully relativistic framework and a second-order perturbation theory. We focus our analysis on how electron correlation, as well as the negative-energy spectrum, can affect the forbidden E1M1 decay rate. For this purpose, we include the electronic correlation via an effective local potential and within a single configuration-state model. Due to its experimental interest, evaluations of decay rates are performed for berylliumlike xenon and uranium. We find that the negative-energy contribution can be neglected at the present level of accuracy in the evaluation of the decay rate. On the other hand, if contributions of electronic correlation are not carefully taken into account, it may change the lifetime of the metastable state by up to 20%. By performing a full-relativistic jj-coupling calculation, we found a decrease of the decay rate by two orders of magnitude compared to non-relativistic LS-coupling calculations, for the selected heavy ions.
AU - Amaro, Pedro
AU - Fratini, Filippo
AU - Safari, Laleh
AU - Machado, Jorge
AU - Guerra, Mauro
AU - Indelicato, Paul
AU - Santos, José
ID - 1496
IS - 3
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Relativistic evaluation of the two-photon decay of the metastable 1s22s2p3P0 state in berylliumlike ions with an effective-potential model
VL - 93
ER -
TY - JOUR
AB - The inference of demographic history from genome data is hindered by a lack of efficient computational approaches. In particular, it has proved difficult to exploit the information contained in the distribution of genealogies across the genome. We have previously shown that the generating function (GF) of genealogies can be used to analytically compute likelihoods of demographic models from configurations of mutations in short sequence blocks (Lohse et al. 2011). Although the GF has a simple, recursive form, the size of such likelihood calculations explodes quickly with the number of individuals and applications of this framework have so far been mainly limited to small samples (pairs and triplets) for which the GF can be written by hand. Here we investigate several strategies for exploiting the inherent symmetries of the coalescent. In particular, we show that the GF of genealogies can be decomposed into a set of equivalence classes that allows likelihood calculations from nontrivial samples. Using this strategy, we automated blockwise likelihood calculations for a general set of demographic scenarios in Mathematica. These histories may involve population size changes, continuous migration, discrete divergence, and admixture between multiple populations. To give a concrete example, we calculate the likelihood for a model of isolation with migration (IM), assuming two diploid samples without phase and outgroup information. We demonstrate the new inference scheme with an analysis of two individual butterfly genomes from the sister species Heliconius melpomene rosina and H. cydno.
AU - Lohse, Konrad
AU - Chmelik, Martin
AU - Martin, Simon
AU - Barton, Nicholas H
ID - 1518
IS - 2
JF - Genetics
TI - Efficient strategies for calculating blockwise likelihoods under the coalescent
VL - 202
ER -
TY - JOUR
AB - We classify smooth Brunnian (i.e., unknotted on both components) embeddings (S2 × S1) ⊔ S3 → ℝ6. Any Brunnian embedding (S2 × S1) ⊔ S3 → ℝ6 is isotopic to an explicitly constructed embedding fk,m,n for some integers k, m, n such that m ≡ n (mod 2). Two embeddings fk,m,n and fk′ ,m′,n′ are isotopic if and only if k = k′, m ≡ m′ (mod 2k) and n ≡ n′ (mod 2k). We use Haefliger’s classification of embeddings S3 ⊔ S3 → ℝ6 in our proof. The relation between the embeddings (S2 × S1) ⊔ S3 → ℝ6 and S3 ⊔ S3 → ℝ6 is not trivial, however. For example, we show that there exist embeddings f: (S2 ×S1) ⊔ S3 → ℝ6 and g, g′ : S3 ⊔ S3 → ℝ6 such that the componentwise embedded connected sum f # g is isotopic to f # g′ but g is not isotopic to g′.
AU - Avvakumov, Serhii
ID - 1522
IS - 1
JF - Moscow Mathematical Journal
TI - The classification of certain linked 3-manifolds in 6-space
VL - 16
ER -
TY - JOUR
AB - For random graphs, the containment problem considers the probability that a binomial random graph G(n, p) contains a given graph as a substructure. When asking for the graph as a topological minor, i.e., for a copy of a subdivision of the given graph, it is well known that the (sharp) threshold is at p = 1/n. We consider a natural analogue of this question for higher-dimensional random complexes Xk(n, p), first studied by Cohen, Costa, Farber and Kappeler for k = 2. Improving previous results, we show that p = Θ(1/ √n) is the (coarse) threshold for containing a subdivision of any fixed complete 2-complex. For higher dimensions k > 2, we get that p = O(n−1/k) is an upper bound for the threshold probability of containing a subdivision of a fixed k-dimensional complex.
AU - Gundert, Anna
AU - Wagner, Uli
ID - 1523
IS - 4
JF - Proceedings of the American Mathematical Society
TI - On topological minors in random simplicial complexes
VL - 144
ER -
TY - CONF
AB - 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 -
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 -