TY - JOUR
AB - We consider the low-density limit of a Fermi gas in the BCS approximation. We show that if the interaction potential allows for a two-particle bound state, the system at zero temperature is well approximated by the Gross-Pitaevskii functional, describing a Bose-Einstein condensate of fermion pairs.
AU - Hainzl, Christian
AU - Robert Seiringer
ID - 2397
IS - 2
JF - Letters in Mathematical Physics
TI - Low density limit of BCS theory and Bose-Einstein condensation of Fermion pairs
VL - 100
ER -
TY - GEN
AB - We extend the mathematical theory of quantum hypothesis testing to the general W*-algebraic setting and explore its relation with recent developments in non-equilibrium quantum statistical mechanics. In particular, we relate the large deviation principle for the full counting statistics of entropy flow to quantum hypothesis testing of the arrow of time.
AU - Jakšić, Vojkan
AU - Ogata, Yoshiko
AU - Pillet, Claude A
AU - Robert Seiringer
ID - 2398
IS - 6
T2 - Reviews in Mathematical Physics
TI - Quantum hypothesis testing and non-equilibrium statistical mechanics
VL - 24
ER -
TY - JOUR
AB - If the polaron coupling constant α is large enough, bipolarons or multi-polarons will form. When passing through the critical α c from above, does the radius of the system simply get arbitrarily large or does it reach a maximum and then explode? We prove that it is always the latter. We also prove the analogous statement for the Pekar-Tomasevich (PT) approximation to the energy, in which case there is a solution to the PT equation at α c. Similarly, we show that the same phenomenon occurs for atoms, e. g., helium, at the critical value of the nuclear charge. Our proofs rely only on energy estimates, not on a detailed analysis of the Schrödinger equation, and are very general. They use the fact that the Coulomb repulsion decays like 1/r, while 'uncertainty principle' localization energies decay more rapidly, as 1/r 2.
AU - Frank, Rupert L
AU - Lieb, Élliott H
AU - Robert Seiringer
ID - 2400
IS - 2
JF - Communications in Mathematical Physics
TI - Binding of polarons and atoms at threshold
VL - 313
ER -
TY - JOUR
AB - We find further implications of the BMV conjecture, which states that for hermitian matrices B≥0 and A, the function λ {mapping} Tr exp(A - λB) is the Laplace transform of a positive measure supported on [0,∞].
AU - Lieb, Élliott H
AU - Robert Seiringer
ID - 2401
IS - 1
JF - Journal of Statistical Physics
TI - Further implications of the Bessis-Moussa-Villani conjecture
VL - 149
ER -
TY - JOUR
AB - We consider a model of quantum-mechanical particles interacting via point interactions of infinite scattering length. In the case of fermions we prove a Lieb-Thirring inequality for the energy, i.e., we show that the energy is bounded from below by a constant times the integral of the particle density to the power.
AU - Frank, Rupert L
AU - Robert Seiringer
ID - 2402
IS - 9
JF - Journal of Mathematical Physics
TI - Lieb-Thirring inequality for a model of particles with point interactions
VL - 53
ER -
TY - JOUR
AB - We study the effects of random scatterers on the ground state of the one-dimensional Lieb-Liniger model of interacting bosons on the unit interval in the Gross-Pitaevskii regime. We prove that Bose-Einstein condensation survives even a strong random potential with a high density of scatterers. The character of the wavefunction of the condensate, however, depends in an essential way on the interplay between randomness and the strength of the two-body interaction. For low density of scatterers and strong interactions the wavefunction extends over the whole interval. A high density of scatterers and weak interactions, on the other hand, lead to localization of the wavefunction in a fragmented subset of the interval.
AU - Robert Seiringer
AU - Yngvason, Jakob
AU - Zagrebnov, Valentin A
ID - 2403
IS - 11
JF - Journal of Statistical Mechanics Theory and Experiment
TI - Disordered Bose-Einstein condensates with interaction in one dimension
VL - 2012
ER -
TY - JOUR
AB - The kingdom of fungi provides model organisms for biotechnology, cell biology, genetics, and life sciences in general. Only when their phylogenetic relationships are stably resolved, can individual results from fungal research be integrated into a holistic picture of biology. However, and despite recent progress, many deep relationships within the fungi remain unclear. Here, we present the first phylogenomic study of an entire eukaryotic kingdom that uses a consistency criterion to strengthen phylogenetic conclusions. We reason that branches (splits) recovered with independent data and different tree reconstruction methods are likely to reflect true evolutionary relationships. Two complementary phylogenomic data sets based on 99 fungal genomes and 109 fungal expressed sequence tag (EST) sets analyzed with four different tree reconstruction methods shed light from different angles on the fungal tree of life. Eleven additional data sets address specifically the phylogenetic position of Blastocladiomycota, Ustilaginomycotina, and Dothideomycetes, respectively. The combined evidence from the resulting trees supports the deep-level stability of the fungal groups toward a comprehensive natural system of the fungi. In addition, our analysis reveals methodologically interesting aspects. Enrichment for EST encoded data-a common practice in phylogenomic analyses-introduces a strong bias toward slowly evolving and functionally correlated genes. Consequently, the generalization of phylogenomic data sets as collections of randomly selected genes cannot be taken for granted. A thorough characterization of the data to assess possible influences on the tree reconstruction should therefore become a standard in phylogenomic analyses.
AU - Ebersberger, Ingo
AU - De Matos Simoes, Ricardo
AU - Kupczok, Anne
AU - Gube, Matthias
AU - Kothe, Erika
AU - Voigt, Kerstin
AU - Von Haeseler, Arndt
ID - 2411
IS - 5
JF - Molecular Biology and Evolution
TI - A consistent phylogenetic backbone for the fungi
VL - 29
ER -
TY - JOUR
AB - We investigate the first and second moments of shifted convolutions of the generalized divisor function d 3(n).
AU - Baier, Stephan
AU - Timothy Browning
AU - Marasingha, Gihan
AU - Zhao, Liangyi
ID - 242
IS - 3
JF - Proceedings of the Edinburgh Mathematical Society
TI - Averages of shifted convolutions of d3 (n)
VL - 55
ER -
TY - JOUR
AB - We investigate the solubility of the congruence xy ≡ 1 (mod p), where p is a prime and x, y are restricted to lie in suitable short intervals. Our work relies on a mean value theorem for incomplete Kloosterman sums.
AU - Timothy Browning
AU - Haynes, Alan K
ID - 244
IS - 2
JF - International Journal of Number Theory
TI - Incomplete kloosterman sums and multiplicative inverses in short intervals
VL - 9
ER -
TY - JOUR
AB - Coordinated, subcellular trafficking of proteins is one of the fundamental properties of the multicellular eukaryotic organisms. Trafficking involves a large diversity of compartments, pathways, cargo molecules, and vesicle-sorting events. It is also crucial in regulating the localization and, thus, the activity of various proteins, but the process is still poorly genetically defined in plants. In the past, forward genetics screens had been used to determine the function of genes by searching for a specific morphological phenotype in the organism population in which mutations had been induced chemically or by irradiation. Unfortunately, these straightforward genetic screens turned out to be limited in identifying new regulators of intracellular protein transport, because mutations affecting essential trafficking pathways often lead to lethality. In addition, the use of these approaches has been restricted by functional redundancy among trafficking regulators. Screens for mutants that rely on the observation of changes in the cellular localization or dynamics of fluorescent subcellular markers enable, at least partially, to circumvent these issues. Hence, such image-based screens provide the possibility to identify either alleles with weak effects or components of the subcellular trafficking machinery that have no strong impact on the plant growth.
AU - Zwiewka, Marta
AU - Friml, Jirí
ID - 2459
IS - May
JF - Frontiers in Plant Science
TI - Fluorescence imaging-based forward genetic screens to identify trafficking regulators in plants
VL - 3
ER -
TY - GEN
AU - László Erdös
ID - 2696
T2 - ArXiv
TI - Universality for random matrices and log-gases
ER -
TY - CONF
AU - László Erdös
ID - 2700
TI - Lecture notes on quantum Brownian motion
VL - 95
ER -
TY - CONF
AB - We consider Markov decision processes (MDPs) with specifications given as Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning vertices from where the objective can be ensured with probability 1. We study for the first time the average case complexity of the classical algorithm for computing the set of almost-sure winning vertices for MDPs with Büchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average case running time is linear (as compared to the worst case linear number of iterations and quadratic time complexity). Second, for the average case analysis over all MDPs we show that the expected number of iterations is constant and the average case running time is linear (again as compared to the worst case linear number of iterations and quadratic time complexity). Finally we also show that given that all MDPs are equally likely, the probability that the classical algorithm requires more than constant number of iterations is exponentially small.
AU - Chatterjee, Krishnendu
AU - Joglekar, Manas
AU - Shah, Nisarg
ID - 2715
TI - Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives
VL - 18
ER -
TY - JOUR
AB - We study evolutionary game theory in a setting where individuals learn from each other. We extend the traditional approach by assuming that a population contains individuals with different learning abilities. In particular, we explore the situation where individuals have different search spaces, when attempting to learn the strategies of others. The search space of an individual specifies the set of strategies learnable by that individual. The search space is genetically given and does not change under social evolutionary dynamics. We introduce a general framework and study a specific example in the context of direct reciprocity. For this example, we obtain the counter intuitive result that cooperation can only evolve for intermediate benefit-to-cost ratios, while small and large benefit-to-cost ratios favor defection. Our paper is a step toward making a connection between computational learning theory and evolutionary game dynamics.
AU - Chatterjee, Krishnendu
AU - Zufferey, Damien
AU - Nowak, Martin
ID - 2848
JF - Journal of Theoretical Biology
TI - Evolutionary game dynamics in populations with different learners
VL - 301
ER -
TY - JOUR
AU - Edelsbrunner, Herbert
AU - Strelkova, Nataliya
ID - 2849
IS - 6
JF - Russian Mathematical Surveys
TI - On the configuration space of Steiner minimal trees
VL - 67
ER -
TY - JOUR
AB - Phytohormones are important plant growth regulators that control many developmental processes, such as cell division, cell differentiation, organogenesis and morphogenesis. They regulate a multitude of apparently unrelated physiological processes, often with overlapping roles, and they mutually modulate their effects. These features imply important synergistic and antagonistic interactions between the various plant hormones. Auxin and cytokinin are central hormones involved in the regulation of plant growth and development, including processes determining root architecture, such as root pole establishment during early embryogenesis, root meristem maintenance and lateral root organogenesis. Thus, to control root development both pathways put special demands on the mechanisms that balance their activities and mediate their interactions. Here, we summarize recent knowledge on the role of auxin and cytokinin in the regulation of root architecture with special focus on lateral root organogenesis, discuss the latest findings on the molecular mechanisms of their interactions, and present forward genetic screen as a tool to identify novel molecular components of the auxin and cytokinin crosstalk.
AU - Bielach, Agnieszka
AU - Duclercq, Jérôme
AU - Peter Marhavy
AU - Eva Benková
ID - 2875
IS - 1595
JF - Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences
TI - Genetic approach towards the identification of auxin - cytokinin crosstalk components involved in root development
VL - 367
ER -
TY - CONF
AB - Quantitative automata are nondeterministic finite automata with edge weights. They value a
run by some function from the sequence of visited weights to the reals, and value a word by its
minimal/maximal run. They generalize boolean automata, and have gained much attention in
recent years. Unfortunately, important automaton classes, such as sum, discounted-sum, and
limit-average automata, cannot be determinized. Yet, the quantitative setting provides the potential
of approximate determinization. We define approximate determinization with respect to
a distance function, and investigate this potential.
We show that sum automata cannot be determinized approximately with respect to any
distance function. However, restricting to nonnegative weights allows for approximate determinization
with respect to some distance functions.
Discounted-sum automata allow for approximate determinization, as the influence of a word’s
suffix is decaying. However, the naive approach, of unfolding the automaton computations up
to a sufficient level, is shown to be doubly exponential in the discount factor. We provide an
alternative construction that is singly exponential in the discount factor, in the precision, and
in the number of states. We prove matching lower bounds, showing exponential dependency on
each of these three parameters.
Average and limit-average automata are shown to prohibit approximate determinization with
respect to any distance function, and this is the case even for two weights, 0 and 1.
AU - Boker, Udi
AU - Henzinger, Thomas A
ID - 2891
T2 - Leibniz International Proceedings in Informatics
TI - Approximate determinization of quantitative automata
VL - 18
ER -
TY - CONF
AB - In order to enjoy a digital version of the Jordan Curve Theorem, it is common to use the closed topology for the foreground and the open topology for the background of a 2-dimensional binary image. In this paper, we introduce a single topology that enjoys this theorem for all thresholds decomposing a real-valued image into foreground and background. This topology is easy to construct and it generalizes to n-dimensional images.
AU - Edelsbrunner, Herbert
AU - Symonova, Olga
ID - 2903
TI - The adaptive topology of a digital image
ER -
TY - JOUR
AB - Generalized van der Corput sequences are onedimensional, infinite sequences in the unit interval. They are generated from permutations in integer base b and are the building blocks of the multi-dimensional Halton sequences. Motivated by recent progress of Atanassov on the uniform distribution behavior of Halton sequences, we study, among others, permutations of the form P(i) = ai (mod b) for coprime integers a and b. We show that multipliers a that either divide b - 1 or b + 1 generate van der Corput sequences with weak distribution properties. We give explicit lower bounds for the asymptotic distribution behavior of these sequences and relate them to sequences generated from the identity permutation in smaller bases, which are, due to Faure, the weakest distributed generalized van der Corput sequences.
AU - Pausinger, Florian
ID - 2904
IS - 3
JF - Journal de Theorie des Nombres des Bordeaux
SN - 2118-8572
TI - Weak multipliers for generalized van der Corput sequences
VL - 24
ER -
TY - CONF
AB - The classical (boolean) notion of refinement for behavioral interfaces of system components is the alternating refinement preorder. In this paper, we define a quantitative measure for interfaces, called interface simulation distance. It makes the alternating refinement preorder quantitative by, intu- itively, tolerating errors (while counting them) in the alternating simulation game. We show that the interface simulation distance satisfies the triangle inequality, that the distance between two interfaces does not increase under parallel composition with a third interface, and that the distance between two interfaces can be bounded from above and below by distances between abstractions of the two interfaces. We illustrate the framework, and the properties of the distances under composition of interfaces, with two case studies.
AU - Cerny, Pavol
AU - Chmelik, Martin
AU - Henzinger, Thomas A
AU - Radhakrishna, Arjun
ID - 2916
T2 - Electronic Proceedings in Theoretical Computer Science
TI - Interface Simulation Distances
VL - 96
ER -
TY - GEN
AB - This paper addresses the problem of approximate MAP-MRF inference in general graphical models. Following [36], we consider a family of linear programming relaxations of the problem where each relaxation is specified by a set of nested pairs of factors for which the marginalization constraint needs to be enforced. We develop a generalization of the TRW-S algorithm [9] for this problem, where we use a decomposition into junction chains, monotonic w.r.t. some ordering on the nodes. This generalizes the monotonic chains in [9] in a natural way. We also show how to deal with nested factors in an efficient way. Experiments show an improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on a number of computer vision and natural language processing problems.
AU - Kolmogorov, Vladimir
AU - Schoenemann, Thomas
ID - 2928
T2 - arXiv
TI - Generalized sequential tree-reweighted message passing
ER -
TY - GEN
AU - Vladimir Kolmogorov
ID - 2929
TI - The power of linear programming for valued CSPs: a constructive characterization
ER -
TY - CONF
AB - In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k = 1 and k = 2 respectively.
In particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron.
AU - Huber, Anna
AU - Kolmogorov, Vladimir
ID - 2930
TI - Towards minimizing k-submodular functions
VL - 7422
ER -
TY - CONF
AB - The notion of delays arises naturally in many computational models, such as, in the design of circuits, control systems, and dataflow languages. In this work, we introduce automata with delay blocks (ADBs), extending finite state automata with variable time delay blocks, for deferring individual transition output symbols, in a discrete-time setting. We show that the ADB languages strictly subsume the regular languages, and are incomparable in expressive power to the context-free languages. We show that ADBs are closed under union, concatenation and Kleene star, and under intersection with regular languages, but not closed under complementation and intersection with other ADB languages. We show that the emptiness and the membership problems are decidable in polynomial time for ADBs, whereas the universality problem is undecidable. Finally we consider the linear-time model checking problem, i.e., whether the language of an ADB is contained in a regular language, and show that the model checking problem is PSPACE-complete. Copyright 2012 ACM.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Prabhu, Vinayak
ID - 2936
T2 - roceedings of the tenth ACM international conference on Embedded software
TI - Finite automata with time delay blocks
ER -
TY - CONF
AB - Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from this task by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is hard as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage, ZKCrypt provides assurance that the output implementation securely realizes the abstract proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system.
AU - Almeida, José
AU - Barbosa, Manuel
AU - Bangerter, Endre
AU - Barthe, Gilles
AU - Krenn, Stephan
AU - Béguelin, Santiago
ID - 2937
T2 - Proceedings of the 2012 ACM conference on Computer and communications security
TI - Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols
ER -
TY - JOUR
AU - Dolbilin, Nikolai
AU - Edelsbrunner, Herbert
AU - Musin, Oleg
ID - 2941
IS - 4
JF - Russian Mathematical Surveys
TI - On the optimality of functionals over triangulations of Delaunay sets
VL - 67
ER -
TY - JOUR
AB - We examine whether the Escherichia coli chromosome is folded into a self-adherent nucleoprotein complex, or alternately is a confined but otherwise unconstrained self-avoiding polymer. We address this through in vivo visualization, using an inducible GFP fusion to the nucleoid-associated protein Fis to non-specifically decorate the entire chromosome. For a range of different growth conditions, the chromosome is a compact structure that does not fill the volume of the cell, and which moves from the new pole to the cell centre. During rapid growth, chromosome segregation occurs well before cell division, with daughter chromosomes coupled by a thin inter-daughter filament before complete segregation, whereas during slow growth chromosomes stay adjacent until cell division occurs. Image correlation analysis indicates that sub-nucleoid structure is stable on a 1min timescale, comparable to the timescale for redistribution time measured for GFP-Fis after photobleaching. Optical deconvolution and writhe calculation analysis indicate that the nucleoid has a large-scale coiled organization rather than being an amorphous mass. Our observations are consistent with the chromosome having a self-adherent filament organization.
AU - Hadizadeh Yazdi, Nastaran
AU - Guet, Calin C
AU - Johnson, Reid
AU - Marko, John
ID - 2943
IS - 6
JF - Molecular Microbiology
TI - Variation of the folding and dynamics of the Escherichia coli chromosome with growth conditions
VL - 86
ER -
TY - JOUR
AB - MicroRNAs (miRNAs) are small noncoding RNAs that function in literally all cellular processes. miRNAs interact with Argonaute (Ago) proteins and guide them to specific target sites located in the 3′-untranslated region (3′-UTR) of target mRNAs leading to translational repression and deadenylation-induced mRNA degradation. Most miRNAs are processed from hairpin-structured precursors by the consecutive action of the RNase III enzymes Drosha and Dicer. However, processing of miR-451 is Dicer independent and cleavage is mediated by the endonuclease Ago2. Here we have characterized miR-451 sequence and structure requirements for processing as well as sorting of miRNAs into different Ago proteins. Pre-miR-451 appears to be optimized for Ago2 cleavage and changes result in reduced processing. In addition, we show that the mature miR-451 only associates with Ago2 suggesting that mature miRNAs are not exchanged between different members of the Ago protein family. Based on cloning and deep sequencing of endogenous miRNAs associated with Ago1-3, we do not find evidence for miRNA sorting in human cells. However, Ago identity appears to influence the length of some miRNAs, while others remain unaffected.
AU - Dueck, Anne
AU - Ziegler, Christian
AU - Eichner, Alexander
AU - Berezikov, Eugène
AU - Meister, Gunter
ID - 2946
IS - 19
JF - Nucleic Acids Research
TI - MicroRNAs associated with the different human Argonaute proteins
VL - 40
ER -
TY - CONF
AB - We introduce games with probabilistic uncertainty, a model for controller synthesis in which the controller observes the state through imprecise sensors that provide correct information about the current state with a fixed probability. That is, in each step, the sensors return an observed state, and given the observed state, there is a probability distribution (due to the estimation error) over the actual current state. The controller must base its decision on the observed state (rather than the actual current state, which it does not know). On the other hand, we assume that the environment can perfectly observe the current state. We show that controller synthesis for qualitative ω-regular objectives in our model can be reduced in polynomial time to standard partial-observation stochastic games, and vice-versa. As a consequence we establish the precise decidability frontier for the new class of games, and establish optimal complexity results for all the decidable problems.
AU - Chatterjee, Krishnendu
AU - Chmelik, Martin
AU - Majumdar, Ritankar
ID - 2947
TI - Equivalence of games with probabilistic uncertainty and partial observation games
VL - 7561
ER -
TY - JOUR
AB - Spontaneous postsynaptic currents (PSCs) provide key information about the mechanisms of synaptic transmission and the activity modes of neuronal networks. However, detecting spontaneous PSCs in vitro and in vivo has been challenging, because of the small amplitude, the variable kinetics, and the undefined time of generation of these events. Here, we describe a, to our knowledge, new method for detecting spontaneous synaptic events by deconvolution, using a template that approximates the average time course of spontaneous PSCs. A recorded PSC trace is deconvolved from the template, resulting in a series of delta-like functions. The maxima of these delta-like events are reliably detected, revealing the precise onset times of the spontaneous PSCs. Among all detection methods, the deconvolution-based method has a unique temporal resolution, allowing the detection of individual events in high-frequency bursts. Furthermore, the deconvolution-based method has a high amplitude resolution, because deconvolution can substantially increase the signal/noise ratio. When tested against previously published methods using experimental data, the deconvolution-based method was superior for spontaneous PSCs recorded in vivo. Using the high-resolution deconvolution-based detection algorithm, we show that the frequency of spontaneous excitatory postsynaptic currents in dentate gyrus granule cells is 4.5 times higher in vivo than in vitro.
AU - Pernia-Andrade, Alejandro
AU - Goswami, Sarit
AU - Stickler, Yvonne
AU - Fröbe, Ulrich
AU - Schlögl, Alois
AU - Jonas, Peter M
ID - 2954
IS - 7
JF - Biophysical Journal
TI - A deconvolution based method with high sensitivity and temporal resolution for detection of spontaneous synaptic currents in vitro and in vivo
VL - 103
ER -
TY - CONF
AB - We consider two-player stochastic games played on finite graphs with reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1), or positively (i.e., with positive probability), no matter the strategy of the second player. We classify such games according to the information and the power of randomization available to the players. On the basis of information, the game can be one-sided with either (a) player 1, or (b) player 2 having partial observation (and the other player has perfect observation), or two-sided with (c) both players having partial observation. On the basis of randomization, the players (a) may not be allowed to use randomization (pure strategies), or (b) may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) may use full randomization. Our main results for pure strategies are as follows. (1) For one-sided games with player 1 having partial observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strategies are not sufficient, and we present an exponential upper bound on memory both for almostsure and positive winning strategies; we show that the problem of deciding the existence of almost-sure and positive winning strategies for player 1 is EXPTIME-complete. (2) For one-sided games with player 2 having partial observation we show that non-elementary memory is both necessary and sufficient for both almost-sure and positive winning strategies. (3) We show that for the general (two-sided) case finite-memory strategies are sufficient for both positive and almost-sure winning, and at least non-elementary memory is required. We establish the equivalence of the almost-sure winning problems for pure strategies and for randomized strategies with actions invisible. Our equivalence result exhibits serious flaws in previous results of the literature: we show a non-elementary memory lower bound for almost-sure winning whereas an exponential upper bound was previously claimed.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
ID - 2955
T2 - Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science
TI - Partial-observation stochastic games: How to win when belief fails
ER -
TY - CONF
AB - We consider probabilistic automata on infinite words with acceptance defined by parity conditions. We consider three qualitative decision problems: (i) the positive decision problem asks whether there is a word that is accepted with positive probability; (ii) the almost decision problem asks whether there is a word that is accepted with probability 1; and (iii) the limit decision problem asks whether words are accepted with probability arbitrarily close to 1. We unify and generalize several decidability results for probabilistic automata over infinite words, and identify a robust (closed under union and intersection) subclass of probabilistic automata for which all the qualitative decision problems are decidable for parity conditions. We also show that if the input words are restricted to lasso shape (regular) words, then the positive and almost problems are decidable for all probabilistic automata with parity conditions. For most decidable problems we show an optimal PSPACE-complete complexity bound.
AU - Chatterjee, Krishnendu
AU - Tracol, Mathieu
ID - 2957
T2 - Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science
TI - Decidable problems for probabilistic automata on infinite words
ER -
TY - JOUR
AB - The activity of hippocampal pyramidal cells reflects both the current position of the animal and information related to its current behavior. Here we investigated whether single hippocampal neurons can encode several independent features defining trials during a memory task. We also tested whether task-related information is represented by partial remapping of the place cell population or, instead, via firing rate modulation of spatially stable place cells. To address these two questions, the activity of hippocampal neurons was recorded in rats performing a conditional discrimination task on a modified T-maze in which the identity of a food reward guided behavior. When the rat was on the central arm of the maze, the firing rate of pyramidal cells changed depending on two independent factors: (1) the identity of the food reward given to the animal and (2) the previous location of the animal on the maze. Importantly, some pyramidal cells encoded information relative to both factors. This trial-type specific and retrospective coding did not interfere with the spatial representation of the maze: hippocampal cells had stable place fields and their theta-phase precession profiles were unaltered during the task, indicating that trial-related information was encoded via rate remapping. During error trials, encoding of both trial-related information and spatial location was impaired. Finally, we found that pyramidal cells also encode trial-related information via rate remapping during the continuous version of the rewarded alternation task without delays. These results suggest that hippocampal neurons can encode several task-related cognitive aspects via rate remapping.
AU - Allen, Kevin
AU - Rawlins, J Nick
AU - Bannerman, David
AU - Csicsvari, Jozsef L
ID - 2958
IS - 42
JF - Journal of Neuroscience
TI - Hippocampal place cells can encode multiple trial-dependent features through rate remapping
VL - 32
ER -
TY - JOUR
AB - We study maximum likelihood estimation in Gaussian graphical models from a geometric point of view. An algebraic elimination criterion allows us to find exact lower bounds on the number of observations needed to ensure that the maximum likelihood estimator (MLE) exists with probability one. This is applied to bipartite graphs, grids and colored graphs. We also study the ML degree, and we present the first instance of a graph for which the MLE exists with probability one, even when the number of observations equals the treewidth.
AU - Uhler, Caroline
ID - 2959
IS - 1
JF - Annals of Statistics
TI - Geometry of maximum likelihood estimation in Gaussian graphical models
VL - 40
ER -
TY - JOUR
AB - The choice of summary statistics is a crucial step in approximate Bayesian computation (ABC). Since statistics are often not sufficient, this choice involves a trade-off between loss of information and reduction of dimensionality. The latter may increase the efficiency of ABC. Here, we propose an approach for choosing summary statistics based on boosting, a technique from the machine learning literature. We consider different types of boosting and compare them to partial least squares regression as an alternative. To mitigate the lack of sufficiency, we also propose an approach for choosing summary statistics locally, in the putative neighborhood of the true parameter value. We study a demographic model motivated by the re-introduction of Alpine ibex (Capra ibex) into the Swiss Alps. The parameters of interest are the mean and standard deviation across microsatellites of the scaled ancestral mutation rate (θanc = 4 Ne u), and the proportion of males obtaining access to matings per breeding season (ω). By simulation, we assess the properties of the posterior distribution obtained with the various methods. According to our criteria, ABC with summary statistics chosen locally via boosting with the L2-loss performs best. Applying that method to the ibex data, we estimate θanc ≈ 1.288, and find that most of the variation across loci of the ancestral mutation rate u is between 7.7×10−4 and 3.5×10−3 per locus per generation. The proportion of males with access to matings is estimated to ω ≈ 0.21, which is in good agreement with recent independent estimates.
AU - Aeschbacher, Simon
AU - Beaumont, Mark
AU - Futschik, Andreas
ID - 2962
IS - 3
JF - Genetics
TI - A novel approach for choosing summary statistics in approximate Bayesian computation
VL - 192
ER -
TY - JOUR
AB - Dieser Artikel soll die sechs verschiedenen Creative Commons Lizenzen erläutern und ihre Bedeutung im Rahmen des wissenschaftlichen Publizierens und des Open Access erklären (CC-BY, CC-BY-SA, CC-BY-NC, CC-BY-ND, CC-BYNC-SA, CC-BY-NC-ND).
AU - Danowski, Patrick
ID - 2965
IS - 2
JF - Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen & Bibliothekare
TI - Kontext Open Access: Creative Commons
VL - 65
ER -
TY - JOUR
AB - Background: The outcome of male-male competition can be predicted from the relative fighting qualities of the opponents, which often depend on their age. In insects, freshly emerged and still sexually inactive males are morphologically indistinct from older, sexually active males. These young inactive males may thus be easy targets for older males if they cannot conceal themselves from their attacks. The ant Cardiocondyla obscurior is characterised by lethal fighting between wingless (" ergatoid" ) males. Here, we analyse for how long young males are defenceless after eclosion, and how early adult males can detect the presence of rival males.Results: We found that old ergatoid males consistently won fights against ergatoid males younger than two days. Old males did not differentiate between different types of unpigmented pupae several days before emergence, but had more frequent contact to ready-to-eclose pupae of female sexuals and winged males than of workers and ergatoid males. In rare cases, old ergatoid males displayed alleviated biting of pigmented ergatoid male pupae shortly before adult eclosion, as well as copulation attempts to dark pupae of female sexuals and winged males. Ergatoid male behaviour may be promoted by a closer similarity of the chemical profile of ready-to-eclose pupae to the profile of adults than that of young pupae several days prior to emergence.Conclusion: Young ergatoid males of C. obscurior would benefit greatly by hiding their identity from older, resident males, as they are highly vulnerable during the first two days of their adult lives. In contrast to the winged males of the same species, which are able to prevent ergatoid male attacks by chemical female mimicry, young ergatoids do not seem to be able to produce a protective chemical profile. Conflicts in male-male competition between ergatoid males of different age thus seem to be resolved in favour of the older males. This might represent selection at the colony level rather than the individual level. © 2012 Cremer et al.; licensee BioMed Central Ltd.
AU - Cremer, Sylvia
AU - Suefuji, Masaki
AU - Schrempf, Alexandra
AU - Heinze, Jürgen
ID - 2966
JF - BMC Ecology
TI - The dynamics of male-male competition in Cardiocondyla obscurior ants
VL - 12
ER -
TY - JOUR
AB - Little is known about the stability of trophic relationships in complex natural communities over evolutionary timescales. Here, we use sequence data from 18 nuclear loci to reconstruct and compare the intraspecific histories of major Pleistocene refugial populations in the Middle East, the Balkans and Iberia in a guild of four Chalcid parasitoids (Cecidostiba fungosa, Cecidostiba semifascia, Hobbya stenonota and Mesopolobus amaenus) all attacking Cynipid oak galls. We develop a likelihood method to numerically estimate models of divergence between three populations from multilocus data. We investigate the power of this framework on simulated data, and-using triplet alignments of intronic loci-quantify the support for all possible divergence relationships between refugial populations in the four parasitoids. Although an East to West order of population divergence has highest support in all but one species, we cannot rule out alternative population tree topologies. Comparing the estimated times of population splits between species, we find that one species, M. amaenus, has a significantly older history than the rest of the guild and must have arrived in central Europe at least one glacial cycle prior to other guild members. This suggests that although all four species may share a common origin in the East, they expanded westwards into Europe at different times. © 2012 Blackwell Publishing Ltd.
AU - Lohse, Konrad
AU - Barton, Nicholas H
AU - Melika, George
AU - Stone, Graham
ID - 2968
IS - 18
JF - Molecular Ecology
TI - A likelihood based comparison of population histories in a parasitoid guild
VL - 21
ER -
TY - JOUR
AB - The coupling between presynaptic Ca^(2+) channels and Ca^(2+) sensors of exocytosis is a key determinant of synaptic transmission. Evoked release from parvalbumin (PV)-expressing interneurons is triggered by nanodomain coupling of P/Q-type Ca^(2+) channels, whereas release from cholecystokinin (CCK)-containing interneurons is generated by microdomain coupling of N-type channels. Nanodomain coupling has several functional advantages, including speed and efficacy of transmission. One potential disadvantage is that stochastic
opening of presynaptic Ca^(2+) channels may trigger spontaneous transmitter release. We addressed this possibility in rat hippocampal
granule cells, which receive converging inputs from different inhibitory sources. Both reduction of extracellular Ca^(2+) concentration and the unselective Ca^(2+) channel blocker Cd^(2+) reduced the frequency of miniature IPSCs (mIPSCs) in granule cells by ~50%, suggesting that the opening of presynaptic Ca^(2+) channels contributes to spontaneous release. Application of the selective P/Q-type Ca^(2+) channel blocker
ω-agatoxin IVa had no detectable effects, whereas both the N-type blocker ω-conotoxin GVIa and the L-type blocker nimodipine reduced
mIPSC frequency. Furthermore, both the fast Ca^(2+) chelator BAPTA-AM and the slow chelator EGTA-AM reduced the mIPSC frequency,
suggesting that Ca^(2+)-dependent spontaneous release is triggered by microdomain rather than nanodomain coupling. The CB_(1) receptor
agonist WIN 55212-2 also decreased spontaneous release; this effect was occluded by prior application of ω-conotoxin GVIa, suggesting that a major fraction of Ca^(2+)-dependent spontaneous release was generated at the terminals of CCK-expressing interneurons. Tonic inhibition generated by spontaneous opening of presynaptic N- and L-type Ca^(2+) channels may be important for hippocampal information processing.
AU - Goswami, Sarit
AU - Bucurenciu, Iancu
AU - Jonas, Peter M
ID - 2969
IS - 41
JF - Journal of Neuroscience
TI - Miniature IPSCs in hippocampal granule cells are triggered by voltage-gated Ca^(2+) channels via microdomain coupling
VL - 32
ER -
TY - JOUR
AB - Energy parity games are infinite two-player turn-based games played on weighted graphs. The objective of the game combines a (qualitative) parity condition with the (quantitative) requirement that the sum of the weights (i.e., the level of energy in the game) must remain positive. Beside their own interest in the design and synthesis of resource-constrained omega-regular specifications, energy parity games provide one of the simplest model of games with combined qualitative and quantitative objectives. Our main results are as follows: (a) exponential memory is sufficient and may be necessary for winning strategies in energy parity games; (b) the problem of deciding the winner in energy parity games can be solved in NP ∩ coNP; and (c) we give an algorithm to solve energy parity by reduction to energy games. We also show that the problem of deciding the winner in energy parity games is logspace-equivalent to the problem of deciding the winner in mean-payoff parity games, which can thus be solved in NP ∩ coNP. As a consequence we also obtain a conceptually simple algorithm to solve mean-payoff parity games.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
ID - 2972
JF - Theoretical Computer Science
TI - Energy parity games
VL - 458
ER -
TY - CONF
AB - We construct a perfectly binding string commitment scheme whose security is based on the learning parity with noise (LPN) assumption, or equivalently, the hardness of decoding random linear codes. Our scheme not only allows for a simple and efficient zero-knowledge proof of knowledge for committed values (essentially a Σ-protocol), but also for such proofs showing any kind of relation amongst committed values, i.e. proving that messages m_0,...,m_u, are such that m_0=C(m_1,...,m_u) for any circuit C.
To get soundness which is exponentially small in a security parameter t, and when the zero-knowledge property relies on the LPN problem with secrets of length l, our 3 round protocol has communication complexity O(t|C|l log(l)) and computational complexity of O(t|C|l) bit operations. The hidden constants are small, and the computation consists mostly of computing inner products of bit-vectors.
AU - Jain, Abhishek
AU - Krenn, Stephan
AU - Pietrzak, Krzysztof Z
AU - Tentes, Aris
ED - Wang, Xiaoyun
ED - Sako, Kazue
ID - 2974
TI - Commitments and efficient zero knowledge proofs from learning parity with noise
VL - 7658
ER -
TY - JOUR
AB - Using correlated live-cell imaging and electron tomography we found that actin branch junctions in protruding and treadmilling lamellipodia are not concentrated at the front as previously supposed, but link actin filament subsets in which there is a continuum of distances from a junction to the filament plus ends, for up to at least 1 mm. When branch sites were observed closely spaced on the same filament their separation was commonly a multiple of the actin helical repeat of 36 nm. Image averaging of branch junctions in the tomograms yielded a model for the in vivo branch at 2.9 nm resolution, which was comparable with that derived for the in vitro actin- Arp2/3 complex. Lamellipodium initiation was monitored in an intracellular wound-healing model and was found to involve branching from the sides of actin filaments oriented parallel to the plasmalemma. Many filament plus ends, presumably capped, terminated behind the lamellipodium tip and localized on the dorsal and ventral surfaces of the actin network. These findings reveal how branching events initiate and maintain a network of actin filaments of variable length, and provide the first structural model of the branch junction in vivo. A possible role of filament capping in generating the lamellipodium leaflet is discussed and a mathematical model of protrusion is also presented.
AU - Vinzenz, Marlene
AU - Nemethova, Maria
AU - Schur, Florian
AU - Mueller, Jan
AU - Narita, Akihiro
AU - Urban, Edit
AU - Winkler, Christoph
AU - Schmeiser, Christian
AU - Koestler, Stefan
AU - Rottner, Klemens
AU - Resch, Guenter
AU - Maéda, Yuichiro
AU - Small, John
ID - 808
IS - 11
JF - Journal of Cell Science
TI - Actin branching in the initiation and maintenance of lamellipodia
VL - 125
ER -
TY - JOUR
AB - For given non-zero integers a, b, q we investigate the density of solutions (x, y) ∈ ℤ2 to the binary cubic congruence ax2 + by3 ≡ 0 mod q, and use it to establish the Manin conjecture for a singular del Pezzo surface of degree 2 defined over ℚ.
AU - Timothy Browning
AU - Baier, Stephan
ID - 171
IS - 680
JF - Journal fur die Reine und Angewandte Mathematik
TI - Inhomogeneous cubic congruences and rational points on del Pezzo surfaces
VL - 2013
ER -
TY - JOUR
AB - We report on the electronic transport properties of multiple-gate devices fabricated from undoped silicon nanowires. Understanding and control of the relevant transport mechanisms was achieved by means of local electrostatic gating and temperature-dependent measurements. The roles of the source/drain contacts and of the silicon channel could be independently evaluated and tuned. Wrap gates surrounding the silicide-silicon contact interfaces were proved to be effective in inducing a full suppression of the contact Schottky barriers, thereby enabling carrier injection down to liquid helium temperature. By independently tuning the effective Schottky barrier heights, a variety of reconfigurable device functionalities could be obtained. In particular, the same nanowire device could be configured to work as a Schottky barrier transistor, a Schottky diode, or a p-n diode with tunable polarities. This versatility was eventually exploited to realize a NAND logic gate with gain well above one.
AU - Mongillo, Massimo
AU - Spathis, Panayotis N
AU - Georgios Katsaros
AU - Gentile, Pascal
AU - De Franceschi, Silvano
ID - 1756
IS - 6
JF - Nano Letters
TI - Multifunctional devices and logic gates with undoped silicon nanowires
VL - 12
ER -
TY - JOUR
AB - Self-assembled Ge wires with a height of only 3 unit cells and a length of up to 2 micrometers were grown on Si(001) by means of a catalyst-free method based on molecular beam epitaxy. The wires grow horizontally along either the [100] or the [010] direction. On atomically flat surfaces, they exhibit a highly uniform, triangular cross section. A simple thermodynamic model accounts for the existence of a preferential base width for longitudinal expansion, in quantitative agreement with the experimental findings. Despite the absence of intentional doping, the first transistor-type devices made from single wires show low-resistive electrical contacts and single-hole transport at sub-Kelvin temperatures. In view of their exceptionally small and self-defined cross section, these Ge wires hold promise for the realization of hole systems with exotic properties and provide a new development route for silicon-based nanoelectronics.
AU - Zhang, Jianjun
AU - Georgios Katsaros
AU - Montalenti, Francesco
AU - Scopece, Daniele
AU - Rezaev, Roman O
AU - Mickel, Christine H
AU - Rellinghaus, Bernd
AU - Miglio, Leo P
AU - De Franceschi, Silvano
AU - Rastelli, Armando
AU - Schmidt, Oliver G
ID - 1757
IS - 8
JF - Physical Review Letters
TI - Monolithic growth of ultrathin Ge nanowires on Si(001)
VL - 109
ER -
TY - JOUR
AB - We studied the low-energy states of spin-1/2 quantum dots defined in InAs/InP nanowires and coupled to aluminum superconducting leads. By varying the superconducting gap Δ with a magnetic field B we investigated the transition from strong coupling Δ≪T K to weak-coupling Δ≫T K, where T K is the Kondo temperature. Below the critical field, we observe a persisting zero-bias Kondo resonance that vanishes only for low B or higher temperatures, leaving the room to more robust subgap structures at bias voltages between Δ and 2Δ. For strong and approximately symmetric tunnel couplings, a Josephson supercurrent is observed in addition to the Kondo peak. We ascribe the coexistence of a Kondo resonance and a superconducting gap to a significant density of intragap quasiparticle states, and the finite-bias subgap structures to tunneling through Shiba states. Our results, supported by numerical calculations, own relevance also in relation to tunnel-spectroscopy experiments aiming at the observation of Majorana fermions in hybrid nanostructures.
AU - Lee, Eduardo J
AU - Jiang, Xiaocheng
AU - Aguado, Ramón
AU - Georgios Katsaros
AU - Lieber, Charles M
AU - De Franceschi, Silvano
ID - 1758
IS - 18
JF - Physical Review Letters
TI - Zero-bias anomaly in a nanowire quantum dot coupled to superconductors
VL - 109
ER -
TY - JOUR
AB - Steering a quantum harmonic oscillator state along cyclic trajectories leads to a path-dependent geometric phase. Here we describe its experimental observation in an electronic harmonic oscillator. We use a superconducting qubit as a nonlinear probe of the phase, which is otherwise unobservable due to the linearity of the oscillator. We show that the geometric phase is, for a variety of cyclic paths, proportional to the area enclosed in the quadrature plane. At the transition to the nonadiabatic regime, we study corrections to the phase and dephasing of the qubit caused by qubit-resonator entanglement. In particular, we identify parameters for which this dephasing mechanism is negligible even in the nonadiabatic regime. The demonstrated controllability makes our system a versatile tool to study geometric phases in open quantum systems and to investigate their potential for quantum information processing.
AU - Pechal, M
AU - Berger, Stefan T
AU - Abdumalikov, Abdufarrukh A
AU - Johannes Fink
AU - Mlynek, Jonas A
AU - Steffen, L. Kraig
AU - Wallraff, Andreas
AU - Filipp, Stefan
ID - 1782
IS - 17
JF - Physical Review Letters
TI - Geometric phase and nonadiabatic effects in an electronic harmonic oscillator
VL - 108
ER -
TY - JOUR
AB - Nonlinearity and entanglement are two important properties by which physical systems can be identified as nonclassical. We study the dynamics of the resonant interaction of up to N=3 two-level systems and a single mode of the electromagnetic field sharing a single excitation dynamically. We observe coherent vacuum Rabi oscillations and their nonlinear √N speedup by tracking the populations of all qubits and the resonator in time. We use quantum state tomography to show explicitly that the dynamics generates maximally entangled states of the W class in a time limited only by the collective interaction rate. We use an entanglement witness and the 3-tangle to characterize the state whose fidelity F=78% is limited in our experiments by crosstalk arising during the simultaneous qubit manipulations which is absent in a sequential approach with F=91%.
AU - Mlynek, Jonas A
AU - Abdumalikov, Abdufarrukh A
AU - Johannes Fink
AU - Steffen, L. Kraig
AU - Baur, Matthias P
AU - Lang, C
AU - Van Loo, Arjan F
AU - Wallraff, Andreas
ID - 1783
IS - 5
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Demonstrating W-type entanglement of Dicke states in resonant cavity quantum electrodynamics
VL - 86
ER -
TY - CONF
AB - Leakage resilient cryptography attempts to incorporate side-channel leakage into the black-box security model and designs cryptographic schemes that are provably secure within it. Informally, a scheme is leakage-resilient if it remains secure even if an adversary learns a bounded amount of arbitrary information about the schemes internal state. Unfortunately, most leakage resilient schemes are unnecessarily complicated in order to achieve strong provable security guarantees. As advocated by Yu et al. [CCS’10], this mostly is an artefact of the security proof and in practice much simpler construction may already suffice to protect against realistic side-channel attacks. In this paper, we show that indeed for simpler constructions leakage-resilience can be obtained when we aim for relaxed security notions where the leakage-functions and/or the inputs to the primitive are chosen non-adaptively. For example, we show that a three round Feistel network instantiated with a leakage resilient PRF yields a leakage resilient PRP if the inputs are chosen non-adaptively (This complements the result of Dodis and Pietrzak [CRYPTO’10] who show that if a adaptive queries are allowed, a superlogarithmic number of rounds is necessary.) We also show that a minor variation of the classical GGM construction gives a leakage resilient PRF if both, the leakage-function and the inputs, are chosen non-adaptively.
AU - Faust, Sebastian
AU - Pietrzak, Krzysztof Z
AU - Schipper, Joachim
ID - 2048
T2 - Conference proceedings CHES 2012
TI - Practical leakage-resilient symmetric cryptography
VL - 7428
ER -
TY - CONF
AB - We propose a new authentication protocol that is provably secure based on a ring variant of the learning parity with noise (LPN) problem. The protocol follows the design principle of the LPN-based protocol from Eurocrypt’11 (Kiltz et al.), and like it, is a two round protocol secure against active attacks. Moreover, our protocol has small communication complexity and a very small footprint which makes it applicable in scenarios that involve low-cost, resource-constrained devices.
Performance-wise, our protocol is more efficient than previous LPN-based schemes, such as the many variants of the Hopper-Blum (HB) protocol and the aforementioned protocol from Eurocrypt’11. Our implementation results show that it is even comparable to the standard challenge-and-response protocols based on the AES block-cipher. Our basic protocol is roughly 20 times slower than AES, but with the advantage of having 10 times smaller code size. Furthermore, if a few hundred bytes of non-volatile memory are available to allow the storage of some off-line pre-computations, then the online phase of our protocols is only twice as slow as AES.
AU - Heyse, Stefan
AU - Kiltz, Eike
AU - Lyubashevsky, Vadim
AU - Paar, Christof
AU - Pietrzak, Krzysztof Z
ID - 2049
T2 - Conference proceedings FSE 2012
TI - Lapin: An efficient authentication protocol based on ring-LPN
VL - 7549
ER -
TY - JOUR
AB - We consider a class of stochastic PDEs of Burgers type in spatial dimension 1, driven by space–time white noise. Even though it is well known that these equations are well posed, it turns out that if one performs a spatial discretization of the nonlinearity in the “wrong” way, then the sequence of approximate equations does converge to a limit, but this limit exhibits an additional correction term. This correction term is proportional to the local quadratic cross-variation (in space) of the gradient of the conserved quantity with the solution itself. This can be understood as a consequence of the fact that for any fixed time, the law of the solution is locally equivalent to Wiener measure, where space plays the role of time. In this sense, the correction term is similar to the usual Itô–Stratonovich correction term that arises when one considers different temporal discretizations of stochastic ODEs.
AU - Hairer, Martin M
AU - Jan Maas
ID - 2125
IS - 4
JF - Annals of Probability
TI - A spatial version of the Itô-Stratonovich correction
VL - 40
ER -
TY - JOUR
AB - We study a new notion of Ricci curvature that applies to Markov chains on discrete spaces. This notion relies on geodesic convexity of the entropy and is analogous to the one introduced by Lott, Sturm, and Villani for geodesic measure spaces. In order to apply to the discrete setting, the role of the Wasserstein metric is taken over by a different metric, having the property that continuous time Markov chains are gradient flows of the entropy. Using this notion of Ricci curvature we prove discrete analogues of fundamental results by Bakry–Émery and Otto–Villani. Further, we show that Ricci curvature bounds are preserved under tensorisation. As a special case we obtain the sharp Ricci curvature lower bound for the discrete hypercube.
AU - Erbar, Matthias
AU - Jan Maas
ID - 2127
IS - 3
JF - Archive for Rational Mechanics and Analysis
TI - Ricci curvature of finite Markov chains via convexity of the entropy
VL - 206
ER -
TY - JOUR
AB - We introduce a technique for handling Whitney decompositions in Gaussian harmonic analysis and apply it to the study of Gaussian analogues of the classical tent spaces T 1,q of Coifman–Meyer–Stein.
AU - Jan Maas
AU - van Neerven, Jan M
AU - Portal, Pierre
ID - 2128
IS - 2
JF - Arkiv för Matematik
TI - Whitney coverings and the tent spaces T 1,q (γ) for the Gaussian measure
VL - 50
ER -
TY - JOUR
AU - Mikhail Lemeshko
AU - Krems, Roman V
AU - Weimer, Hendrik A
ID - 2151
IS - 4
JF - Physical Review Letters
TI - Erratum: Nonadiabatic preparation of spin crystals with ultracold polar molecules
VL - 109
ER -
TY - JOUR
AB - We study the growth dynamics of ordered structures of strongly interacting polar molecules in optical lattices. Using a dipole blockade of microwave excitations, we map the system onto an interacting spin-1/2 model possessing ground states with crystalline order, and describe a way to prepare these states by nonadiabatically driving the transitions between molecular rotational levels. The proposed technique bypasses the need to cross a phase transition and allows for the creation of ordered domains of considerably larger size compared to approaches relying on adiabatic preparation.
AU - Mikhail Lemeshko
AU - Krems, Roman V
AU - Weimer, Hendrik
ID - 2201
IS - 3
JF - Physical Review Letters
TI - Nonadiabatic preparation of spin crystals with ultracold polar molecules
VL - 109
ER -
TY - JOUR
AB - We propose a method for sensitive parallel detection of low-frequency electromagnetic fields based on the fine structure interactions in paramagnetic polar molecules. Compared to the recently implemented scheme employing ultracold 87Rb atoms by Böhi, the technique based on molecules offers a 100-fold higher sensitivity, the possibility to measure both the electric and magnetic field components, and a probe of a wide range of frequencies from the dc limit to the THz regime.
AU - Alyabyshev, Sergey V
AU - Mikhail Lemeshko
AU - Krems, Roman V
ID - 2202
IS - 1
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Sensitive imaging of electromagnetic fields with paramagnetic polar molecules
VL - 86
ER -
TY - JOUR
AB - We show that the electric dipole-dipole interaction between a pair of polar molecules undergoes an all-out transformation when superimposed by a far-off-resonant optical field. The combined interaction potential becomes tunable by variation of wavelength, polarisation and intensity of the optical field and its dependence on the intermolecular separation exhibits a crossover from an inverse-power to an oscillating behaviour. The ability thereby offered to control molecular interactions opens up avenues toward the creation and manipulation of novel phases of ultracold polar gases among whose characteristics is a long-range entanglement of the dipoles' mutual orientation. We devised an accurate analytic model of such optical-field-dressed dipole-dipole interaction potentials, which enables a straightforward access to the optical-field parameters required for the design of intermolecular interactions in the laboratory.
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
ID - 2203
IS - 15-16
JF - Molecular Physics
TI - Interaction between polar molecules subject to a far-off-resonant optical field: Entangled dipoles up- or down-holding each other
VL - 110
ER -
TY - JOUR
AB - Background: Characterizing root system architecture (RSA) is essential to understanding the development and function of vascular plants. Identifying RSA-associated genes also represents an underexplored opportunity for crop improvement. Software tools are needed to accelerate the pace at which quantitative traits of RSA are estimated from images of root networks.Results: We have developed GiA Roots (General Image Analysis of Roots), a semi-automated software tool designed specifically for the high-throughput analysis of root system images. GiA Roots includes user-assisted algorithms to distinguish root from background and a fully automated pipeline that extracts dozens of root system phenotypes. Quantitative information on each phenotype, along with intermediate steps for full reproducibility, is returned to the end-user for downstream analysis. GiA Roots has a GUI front end and a command-line interface for interweaving the software into large-scale workflows. GiA Roots can also be extended to estimate novel phenotypes specified by the end-user.Conclusions: We demonstrate the use of GiA Roots on a set of 2393 images of rice roots representing 12 genotypes from the species Oryza sativa. We validate trait measurements against prior analyses of this image set that demonstrated that RSA traits are likely heritable and associated with genotypic differences. Moreover, we demonstrate that GiA Roots is extensible and an end-user can add functionality so that GiA Roots can estimate novel RSA traits. In summary, we show that the software can function as an efficient tool as part of a workflow to move from large numbers of root images to downstream analysis.
AU - Galkovskyi, Taras
AU - Mileyko, Yuriy
AU - Bucksch, Alexander
AU - Moore, Brad
AU - Symonova, Olga
AU - Price, Charles
AU - Topp, Chrostopher
AU - Iyer Pascuzzi, Anjali
AU - Zurek, Paul
AU - Fang, Suqin
AU - Harer, John
AU - Benfey, Philip
AU - Weitz, Joshua
ID - 492
JF - BMC Plant Biology
TI - GiA Roots: Software for the high throughput analysis of plant root system architecture
VL - 12
ER -
TY - JOUR
AB - The BCI competition IV stands in the tradition of prior BCI competitions that aim to provide high quality neuroscientific data for open access to the scientific community. As experienced already in prior competitions not only scientists from the narrow field of BCI compete, but scholars with a broad variety of backgrounds and nationalities. They include high specialists as well as students.The goals of all BCI competitions have always been to challenge with respect to novel paradigms and complex data. We report on the following challenges: (1) asynchronous data, (2) synthetic, (3) multi-class continuous data, (4) sessionto-session transfer, (5) directionally modulated MEG, (6) finger movements recorded by ECoG. As after past competitions, our hope is that winning entries may enhance the analysis methods of future BCIs.
AU - Tangermann, Michael
AU - Müller, Klaus
AU - Aertsen, Ad
AU - Birbaumer, Niels
AU - Braun, Christoph
AU - Brunner, Clemens
AU - Leeb, Robert
AU - Mehring, Carsten
AU - Miller, Kai
AU - Müller Putz, Gernot
AU - Nolte, Guido
AU - Pfurtscheller, Gert
AU - Preissl, Hubert
AU - Schalk, Gerwin
AU - Schlögl, Alois
AU - Vidaurre, Carmen
AU - Waldert, Stephan
AU - Blankertz, Benjamin
ID - 493
JF - Frontiers in Neuroscience
TI - Review of the BCI competition IV
VL - 6
ER -
TY - CONF
AB - An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with advice. We do the same for tree automata with advice.
AU - Kruckman, Alex
AU - Rubin, Sasha
AU - Sheridan, John
AU - Zax, Ben
ID - 495
T2 - Proceedings GandALF 2012
TI - A Myhill Nerode theorem for automata with advice
VL - 96
ER -
TY - CONF
AB - We study the expressive power of logical interpretations on the class of scattered trees, namely those with countably many infinite branches. Scattered trees can be thought of as the tree analogue of scattered linear orders. Every scattered tree has an ordinal rank that reflects the structure of its infinite branches. We prove, roughly, that trees and orders of large rank cannot be interpreted in scattered trees of small rank. We consider a quite general notion of interpretation: each element of the interpreted structure is represented by a set of tuples of subsets of the interpreting tree. Our trees are countable, not necessarily finitely branching, and may have finitely many unary predicates as labellings. We also show how to replace injective set-interpretations in (not necessarily scattered) trees by 'finitary' set-interpretations.
AU - Rabinovich, Alexander
AU - Rubin, Sasha
ID - 496
TI - Interpretations in trees with countably many branches
ER -
TY - CONF
AB - One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n 3·m) time as compared to the previous known O(n 6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n·m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm. © Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath.
AU - Chatterjee, Krishnendu
AU - Chaubal, Siddhesh
AU - Kamath, Pritish
ID - 497
TI - Faster algorithms for alternating refinement relations
VL - 16
ER -
TY - JOUR
AB - Understanding patterns and correlates of local adaptation in heterogeneous landscapes can provide important information in the selection of appropriate seed sources for restoration. We assessed the extent of local adaptation of fitness components in 12 population pairs of the perennial herb Rutidosis leptorrhynchoides (Asteraceae) and examined whether spatial scale (0.7-600 km), environmental distance, quantitative (QST) and neutral (FST) genetic differentiation, and size of the local and foreign populations could predict patterns of adaptive differentiation. Local adaptation varied among populations and fitness components. Including all population pairs, local adaptation was observed for seedling survival, but not for biomass, while foreign genotype advantage was observed for reproduction (number of inflorescences). Among population pairs, local adaptation increased with QST and local population size for biomass. QST was associated with environmental distance, suggesting ecological selection for phenotypic divergence. However, low FST and variation in population structure in small populations demonstrates the interaction of gene flow and drift in constraining local adaptation in R. leptorrhynchoides. Our study indicates that for species in heterogeneous landscapes, collecting seed from large populations from similar environments to candidate sites is likely to provide the most appropriate seed sources for restoration.
AU - Pickup, Melinda
AU - Field, David
AU - Rowell, David
AU - Young, Andrew
ID - 498
IS - 8
JF - Evolutionary Applications
TI - Predicting local adaptation in fragmented plant populations: Implications for restoration genetics
VL - 5
ER -
TY - JOUR
AU - Sixt, Michael K
ID - 506
IS - 3
JF - Journal of Cell Biology
TI - Cell migration: Fibroblasts find a new way to get ahead
VL - 197
ER -
TY - GEN
AB - Two-player games on graphs are central in many problems in formal verification and program analysis such as synthesis and verification of open systems. In this work we consider solving recursive game graphs (or pushdown game graphs) that can model the control flow of sequential programs with recursion. While pushdown games have been studied before with qualitative objectives, such as reachability and ω-regular objectives, in this work we study for the first time such games with the most well-studied quantitative objective, namely, mean-payoff objectives. In pushdown games two types of strategies are relevant: (1) global strategies, that depend on the entire global history; and (2) modular strategies, that have only local memory and thus do not depend on the context of invocation, but only on the history of the current invocation of the module. Our main results are as follows: (1) One-player pushdown games with mean-payoff objectives under global strategies are decidable in polynomial time. (2) Two- player pushdown games with mean-payoff objectives under global strategies are undecidable. (3) One-player pushdown games with mean-payoff objectives under modular strategies are NP- hard. (4) Two-player pushdown games with mean-payoff objectives under modular strategies can be solved in NP (i.e., both one-player and two-player pushdown games with mean-payoff objectives under modular strategies are NP-complete). We also establish the optimal strategy complexity showing that global strategies for mean-payoff objectives require infinite memory even in one-player pushdown games; and memoryless modular strategies are sufficient in two- player pushdown games. Finally we also show that all the problems have the same complexity if the stack boundedness condition is added, where along with the mean-payoff objective the player must also ensure that the stack height is bounded.
AU - Chatterjee, Krishnendu
AU - Velner, Yaron
ID - 5377
SN - 2664-1690
TI - Mean-payoff pushdown games
ER -
TY - GEN
AB - One central issue in the formal design and analysis of reactive systems is the notion of refinement that asks whether all behaviors of the implementation is allowed by the specification. The local interpretation of behavior leads to the notion of simulation. Alternating transition systems (ATSs) provide a general model for composite reactive systems, and the simulation relation for ATSs is known as alternating simulation. The simulation relation for fair transition systems is called fair simulation. In this work our main contributions are as follows: (1) We present an improved algorithm for fair simulation with Büchi fairness constraints; our algorithm requires O(n3 · m) time as compared to the previous known O(n6)-time algorithm, where n is the number of states and m is the number of transitions. (2) We present a game based algorithm for alternating simulation that requires O(m2)-time as compared to the previous known O((n · m)2)-time algorithm, where n is the number of states and m is the size of transition relation. (3) We present an iterative algorithm for alternating simulation that matches the time complexity of the game based algorithm, but is more space efficient than the game based algorithm.
AU - Chatterjee, Krishnendu
AU - Chaubal, Siddhesh
AU - Kamath, Pritish
ID - 5378
SN - 2664-1690
TI - Faster algorithms for alternating refinement relations
ER -
TY - GEN
AB - We consider the problem of inference in agraphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can out-perform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.
AU - Korc, Filip
AU - Kolmogorov, Vladimir
AU - Lampert, Christoph
ID - 5396
SN - 2664-1690
TI - Approximating marginals using discrete energy minimization
ER -
TY - GEN
AB - This document is created as a part of the project “Repository for Research Data on IST Austria”. It summarises the actual state of research data at IST Austria, based on survey results. It supports the choice of appropriate software, which would best fit the requirements of their users, the researchers.
AU - Porsche, Jana
ID - 5398
TI - Actual state of research data @ ISTAustria
ER -
TY - CHAP
AU - Gupta, Ashutosh
ID - 5745
SN - 0302-9743
T2 - Automated Technology for Verification and Analysis
TI - Improved Single Pass Algorithms for Resolution Proof Reduction
VL - 7561
ER -
TY - JOUR
AB - Canny's edge detection algorithm is a classical and robust method for edge detection in gray-scale images. The two
significant features of this method are introduction of NMS (Non-Maximum Suppression) and double thresholding of
the gradient image. Due to poor illumination, the region boundaries in an image may become vague, creating
uncertainties in the gradient image. In this paper, we have proposed an algorithm based on the concept of type-2 fuzzy sets to handle uncertainties that automatically selects the threshold values needed to segment the gradient image using classical Canny’s edge detection algorithm. The results show that our algorithm works significantly well on different benchmark images as well as medical images (hand radiography images).
AU - Biswas, Ranita
AU - Sil, Jaya
ID - 5839
JF - Procedia Technology
SN - 2212-0173
TI - An Improved Canny Edge Detection Algorithm Based on Type-2 Fuzzy Sets
VL - 4
ER -
TY - JOUR
AB - The human Mediator complex controls RNA polymerase II (pol II) function in ways that remain incompletely understood. Activator-Mediator binding alters Mediator structure, and these activator-induced structural shifts appear to play key roles in regulating transcription. A recent cryo-electron microscopy (EM) analysis revealed that pol II adopted a stable orientation within a Mediator-pol II-TFIIF assembly in which Mediator was bound to the activation domain of viral protein 16 (VP16). Whereas TFIIF was shown to be important for orienting pol II within this assembly, the potential role of the activator was not assessed. To determine how activator binding might affect pol II orientation, we isolated human Mediator-pol II-TFIIF complexes in which Mediator was not bound to an activator. Cryo-EM analysis of this assembly, coupled with pol II crystal structure docking, revealed that pol II binds Mediator at the same general location; however, in contrast to VP16-bound Mediator, pol II does not appear to stably orient in the absence of an activator. Variability in pol II orientation might be important mechanistically, perhaps to enable sense and antisense transcription at human promoters. Because Mediator interacts extensively with pol II, these results suggest that Mediator structural shifts induced by activator binding help stably orient pol II prior to transcription initiation.
AU - Bernecky, Carrie A
AU - Taatjes, Dylan
ID - 596
IS - 5
JF - Journal of Molecular Biology
TI - Activator-mediator binding stabilizes RNA polymerase II orientation within the human mediator-RNA polymerase II-TFIIF assembly
VL - 417
ER -
TY - JOUR
AB - Tonic receptors convey stimulus duration and intensity and are implicated in homeostatic control. However, how tonic homeostatic signals are generated and how they reconfigure neural circuits and modify animal behavior is poorly understood. Here we show that Caenorhabditis elegans O2-sensing neurons are tonic receptors that continuously signal ambient [O2] to set the animal's behavioral state. Sustained signaling relied on a Ca2+ relay involving L-type voltage-gated Ca2+ channels, the ryanodine and the inositol-1,4,5-trisphosphate receptors. Tonic activity evoked continuous neuropeptide release, which helps elicit the enduring behavioral state associated with high [O2]. Sustained O2 receptor signaling was propagated to downstream neural circuits, including the hub interneuron RMG. O2 receptors evoked similar locomotory states at particular O2 concentrations, regardless of previous d[O2]/dt. However, a phasic component of the URX receptors' response to high d[O2]/dt, as well as tonic-to-phasic transformations in downstream interneurons, enabled transient reorientation movements shaped by d[O2]/dt. Our results highlight how tonic homeostatic signals can generate both transient and enduring behavioral change.
AU - Busch, Karl Emanuel
AU - Laurent, Patrick
AU - Soltesz, Zoltan
AU - Murphy, Robin Joseph
AU - Faivre, Olivier
AU - Hedwig, Berthold
AU - Thomas, Martin
AU - Smith, Heather L
AU - de Bono, Mario
ID - 6136
IS - 4
JF - Nature Neuroscience
SN - 1097-6256
TI - Tonic signaling from O2 sensors sets neural circuit activity and behavioral state
VL - 15
ER -
TY - JOUR
AB - First we note that the best polynomial approximation to vertical bar x vertical bar on the set, which consists of an interval on the positive half-axis and a point on the negative half-axis, can be given by means of the classical Chebyshev polynomials. Then we explore the cases when a solution of the related problem on two intervals can be given in elementary functions.
AU - Pausinger, Florian
ID - 6588
IS - 1
JF - Journal of Mathematical Physics, Analysis, Geometry
SN - 1812-9471
TI - Elementary solutions of the Bernstein problem on two intervals
VL - 8
ER -
TY - CONF
AB - Software model checking, as an undecidable problem, has three possible outcomes: (1) the program satisfies the specification, (2) the program does not satisfy the specification, and (3) the model checker fails. The third outcome usually manifests itself in a space-out, time-out, or one component of the verification tool giving up; in all of these failing cases, significant computation is performed by the verification tool before the failure, but no result is reported. We propose to reformulate the model-checking problem as follows, in order to have the verification tool report a summary of the performed work even in case of failure: given a program and a specification, the model checker returns a condition Ψ - usually a state predicate - such that the program satisfies the specification under the condition Ψ - that is, as long as the program does not leave the states in which Ψ is satisfied. In our experiments, we investigated as one major application of conditional model checking the sequential combination of model checkers with information passing. We give the condition that one model checker produces, as input to a second conditional model checker, such that the verification problem for the second is restricted to the part of the state space that is not covered by the condition, i.e., the second model checker works on the problems that the first model checker could not solve. Our experiments demonstrate that repeated application of conditional model checkers, passing information from one model checker to the next, can significantly improve the verification results and performance, i.e., we can now verify programs that we could not verify before.
AU - Beyer, Dirk
AU - Henzinger, Thomas A
AU - Keremoglu, Mehmet
AU - Wendler, Philipp
ID - 1384
T2 - Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering
TI - Conditional model checking: A technique to pass information between verifiers
ER -
TY - JOUR
AB - Given a possibly reducible and non-reduced spectral cover π: X → C over a smooth projective complex curve C we determine the group of connected components of the Prym variety Prym(X/C). As an immediate application we show that the finite group of n-torsion points of the Jacobian of C acts trivially on the cohomology of the twisted SL n-Higgs moduli space up to the degree which is predicted by topological mirror symmetry. In particular this yields a new proof of a result of Harder-Narasimhan, showing that this finite group acts trivially on the cohomology of the twisted SL n stable bundle moduli space.
AU - Tamas Hausel
AU - Pauly, Christian
ID - 1471
IS - 3
JF - Geometry and Topology
TI - Prym varieties of spectral covers
VL - 16
ER -
TY - JOUR
AB - For G = GL 2, PGL 2, SL 2 we prove that the perverse filtration associated with the Hitchin map on the rational cohomology of the moduli space of twisted G-Higgs bundles on a compact Riemann surface C agrees with the weight filtration on the rational cohomology of the twisted G character variety of C when the cohomologies are identified via non-Abelian Hodge theory. The proof is accomplished by means of a study of the topology of the Hitchin map over the locus of integral spectral curves.
AU - De Cataldo, Mark A
AU - Tamas Hausel
AU - Migliorini, Luca
ID - 1472
IS - 3
JF - Annals of Mathematics
TI - Topology of hitchin systems and Hodge theory of character varieties: The case A 1
VL - 175
ER -
TY - JOUR
AB - We prepare and study a metastable attractive Mott-insulator state formed with bosonic atoms in a three-dimensional optical lattice. Starting from a Mott insulator with Cs atoms at weak repulsive interactions, we use a magnetic Feshbach resonance to tune the interactions to large attractive values and produce a metastable state pinned by attractive interactions with a lifetime on the order of 10 s. We probe the (de)excitation spectrum via lattice modulation spectroscopy, measuring the interaction dependence of two- and three-body bound-state energies. As a result of increased on-site three-body loss we observe resonance broadening and suppression of tunneling processes that produce three-body occupation.
AU - Mark, Manfred
AU - Haller, Elmar
AU - Lauber, Katharina
AU - Danzl, Johann G
AU - Janisch, Alexander
AU - Büchler, Hans
AU - Daley, Andrew
AU - Nägerl, Hanns
ID - 1056
IS - 21
JF - Physical Review Letters
TI - Preparation and spectroscopy of a metastable mott-insulator state with attractive interactions
VL - 108
ER -
TY - JOUR
AB - We report on an investigation of the solidification of a cornstarch and water suspension during normal impact on its surface. We find that a finite time after impact, the suspension displays characteristics reminiscent of a solid, including localized stress transmission, the development of a yield stress, and some elastic energy storage. The time dependence of these characteristics depends on the thickness of the cornstarch layer, showing that the solidification is a dynamic process driven by the impacting object. These findings confirm previous speculations that rapidly applied normal stress transforms the normally fluid-like suspension into a temporarily jammed solid and draw a clear distinction between the effects of normal stress and shear stress in dense suspensions.
AU - Waitukaitis, Scott R
AU - Jaeger, Heinrich
ID - 114
IS - 1E
JF - Revista Cubana de Fisica
TI - Solidification of a cornstarch and water suspension
VL - 29
ER -
TY - JOUR
AB - In this Letter, we explore experimentally the phase behavior of a dense active suspension of self-propelled colloids. In addition to a solidlike and gaslike phase observed for high and low densities, a novel cluster phase is reported at intermediate densities. This takes the form of a stationary assembly of dense aggregates—resulting from a permanent dynamical merging and separation of active colloids—whose average size grows with activity as a linear function of the self-propelling velocity. While different possible scenarios can be considered to account for these observations—such as a generic velocity weakening instability recently put forward—we show that the experimental results are reproduced mathematically by a chemotactic aggregation mechanism, originally introduced to account for bacterial aggregation and accounting here for diffusiophoretic chemical interaction between colloidal swimmers.
AU - Theurkauff, I.
AU - Cottin-Bizonne, C.
AU - Palacci, Jérémie A
AU - Ybert, C.
AU - Bocquet, L.
ID - 9014
IS - 26
JF - Physical Review Letters
SN - 00319007
TI - Dynamic clustering in active colloidal suspensions with chemical signaling
VL - 108
ER -
TY - JOUR
AB - In models of radiative–convective equilibrium it is known that convection can spontaneously aggregate into one single localized moist region if the domain is large enough. The large changes in the mean climate state and radiative fluxes accompanying this self-aggregation raise questions as to what simulations at lower resolutions with parameterized convection, in similar homogeneous geometries, should be expected to produce to be considered successful in mimicking a cloud-resolving model.
The authors investigate this self-aggregation in a nonrotating, three-dimensional cloud-resolving model on a square domain without large-scale forcing. It is found that self-aggregation is sensitive not only to the domain size, but also to the horizontal resolution. With horizontally homogeneous initial conditions, convective aggregation only occurs on domains larger than about 200km and with resolutions coarser than about 2km in the model examined. The system exhibits hysteresis, so that with aggregated initial conditions, convection remains aggregated even at our finest resolution, 500m, as long as the domain is greater than 200–300km.
The sensitivity of self-aggregation to resolution and domain size in this model is due to the sensitivity of the distribution of low clouds to these two parameters. Indeed, the mechanism responsible for the aggregation of convection is the dynamical response to the longwave radiative cooling from low clouds. Strong longwave cooling near cloud top in dry regions forces downward motion, which by continuity generates inflow near cloud top and near-surface outflow from dry regions. This circulation results in the net export of moist static energy from regions with low moist static energy, yielding a positive feedback.
AU - MULLER, Caroline J
AU - Held, Isaac M.
ID - 9142
IS - 8
JF - Journal of the Atmospheric Sciences
KW - Atmospheric Science
SN - 0022-4928
TI - Detailed investigation of the self-aggregation of convection in cloud-resolving simulations
VL - 69
ER -
TY - JOUR
AB - We study theoretically the morphologies of biological tubes affected by various pathologies. When epithelial cells grow, the negative tension produced by their division provokes a buckling instability. Several shapes are investigated: varicose, dilated, sinuous, or sausagelike. They are all found in pathologies of tracheal, renal tubes, or arteries. The final shape depends crucially on the mechanical parameters of the tissues: Young's modulus, wall-to-lumen ratio, homeostatic pressure. We argue that since tissues must be in quasistatic mechanical equilibrium, abnormal shapes convey information as to what causes the pathology. We calculate a phase diagram of tubular instabilities which could be a helpful guide for investigating the underlying genetic regulation.
AU - Hannezo, Edouard B
AU - Prost, Jacques
AU - Joanny, Jean
ID - 922
IS - 1
JF - Physical Review Letters
TI - Mechanical instabilities of biological tubes
VL - 109
ER -
TY - JOUR
AB - Motivated by recent experiments on Ba3NiSb2O 9, we investigate possible quantum spin liquid ground states for spin S=1 Heisenberg models on the triangular lattice. We use variational Monte Carlo techniques to calculate the energies of microscopic spin liquid wave functions where spin is represented by three flavors of fermionic spinon operators. These energies are compared with the energies of various competing three-sublattice ordered states. Our approach shows that the antiferromagnetic Heisenberg model with biquadratic term and single-ion anisotropy does not have a low-temperature spin liquid phase. However, for an SU(3)-invariant model with sufficiently strong ring-exchange terms, we find a paired chiral quantum spin liquid with a Fermi surface of deconfined spinons that is stable against all types of ordering patterns we considered. We discuss the physics of this exotic spin liquid state in relation to the recent experiment and suggest new ways to test this scenario.
AU - Bieri, Samuel
AU - Maksym Serbyn
AU - Senthil, Todadri S
AU - Lee, Patrick
ID - 966
IS - 22
JF - Physical Review B - Condensed Matter and Materials Physics
TI - Paired chiral spin liquid with a Fermi surface in S=1 model on the triangular lattice
VL - 86
ER -
TY - JOUR
AB - We summarize classical and recent results about two-player games played on graphs with ω-regular objectives. These games have applications in the verification and synthesis of reactive systems. Important distinctions are whether a graph game is turn-based or concurrent; deterministic or stochastic; zero-sum or not. We cluster known results and open problems according to these classifications.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
ID - 3846
IS - 2
JF - Journal of Computer and System Sciences
TI - A survey of stochastic ω regular games
VL - 78
ER -
TY - JOUR
AB - In this Letter we present detailed study of the density of states near defects in Bi 2Se 3. In particular, we present data on the commonly found triangular defects in this system. While we do not find any measurable quasiparticle scattering interference effects, we do find localized resonances, which can be well fitted by theory once the potential is taken to be extended to properly account for the observed defects. The data together with the fits confirm that while the local density of states around the Dirac point of the electronic spectrum at the surface is significantly disrupted near the impurity by the creation of low-energy resonance state, the Dirac point is not locally destroyed. We discuss our results in terms of the expected protected surface state of topological insulators. © 2012 American Physical Society.
AU - Alpichshev, Zhanybek
AU - Biswas, Rudro
AU - Balatsky, Alexander
AU - Analytis, James
AU - Chu, Jiunhaw
AU - Fisher, Ian
AU - Kapitulnik, Aharon
ID - 387
IS - 20
JF - Physical Review Letters
TI - STM imaging of impurity resonances on Bi 2Se 3
VL - 108
ER -
TY - JOUR
AB - We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance ε in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(nlogn)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. A variant of the algorithm, which we have implemented using the cgal library, is based on rational arithmetic and answers the same deconstruction problem up to an uncertainty parameter δ its running time additionally depends on δ. If the input shape is found to be approximable, this algorithm also computes an approximate solution for the problem. It also allows us to solve parameter-optimization problems induced by the offset-deconstruction problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution P with at most one more vertex than a vertex-minimal one.
AU - Berberich, Eric
AU - Halperin, Dan
AU - Kerber, Michael
AU - Pogalnikova, Roza
ID - 3115
IS - 4
JF - Discrete & Computational Geometry
TI - Deconstructing approximate offsets
VL - 48
ER -
TY - JOUR
AB - We consider the problem of minimizing a function represented as a sum of submodular terms. We assume each term allows an efficient computation of exchange capacities. This holds, for example, for terms depending on a small number of variables, or for certain cardinality-dependent terms. A naive application of submodular minimization algorithms would not exploit the existence of specialized exchange capacity subroutines for individual terms. To overcome this, we cast the problem as a submodular flow (SF) problem in an auxiliary graph in such a way that applying most existing SF algorithms would rely only on these subroutines. We then explore in more detail Iwata's capacity scaling approach for submodular flows (Iwata 1997 [19]). In particular, we show how to improve its complexity in the case when the function contains cardinality-dependent terms.
AU - Kolmogorov, Vladimir
ID - 3117
IS - 15
JF - Discrete Applied Mathematics
TI - Minimizing a sum of submodular functions
VL - 160
ER -
TY - JOUR
AB - We present a method for recovering a temporally coherent, deforming triangle mesh with arbitrarily changing topology from an incoherent sequence of static closed surfaces. We solve this problem using the surface geometry alone, without any prior information like surface templates or velocity fields. Our system combines a proven strategy for triangle mesh improvement, a robust multi-resolution non-rigid registration routine, and a reliable technique for changing surface mesh topology. We also introduce a novel topological constraint enforcement algorithm to ensure that the output and input always have similar topology. We apply our technique to a series of diverse input data from video reconstructions, physics simulations, and artistic morphs. The structured output of our algorithm allows us to efficiently track information like colors and displacement maps, recover velocity information, and solve PDEs on the mesh as a post process.
AU - Bojsen-Hansen, Morten
AU - Li, Hao
AU - Wojtan, Christopher J
ID - 3118
IS - 4
JF - ACM Transactions on Graphics
TI - Tracking surfaces with evolving topology
VL - 31
ER -
TY - CONF
AB - We present an approach for artist-directed animation of liquids using multiple levels of control over the simulation, ranging from the overall tracking of desired shapes to highly detailed secondary effects such as dripping streams, separating sheets of fluid, surface waves and ripples. The first portion of our technique is a volume preserving morph that allows the animator to produce a plausible fluid-like motion from a sparse set of control meshes. By rasterizing the resulting control meshes onto the simulation grid, the mesh velocities act as boundary conditions during the projection step of the fluid simulation. We can then blend this motion together with uncontrolled fluid velocities to achieve a more relaxed control over the fluid that captures natural inertial effects. Our method can produce highly detailed liquid surfaces with control over sub-grid details by using a mesh-based surface tracker on top of a coarse grid-based fluid simulation. We can create ripples and waves on the fluid surface attracting the surface mesh to the control mesh with spring-like forces and also by running a wave simulation over the surface mesh. Our video results demonstrate how our control scheme can be used to create animated characters and shapes that are made of water.
AU - Raveendran, Karthik
AU - Thuerey, Nils
AU - Wojtan, Christopher J
AU - Turk, Greg
ID - 3119
T2 - Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation
TI - Controlling liquids using meshes
ER -
TY - JOUR
AB - We introduce a strategy based on Kustin-Miller unprojection that allows us to construct many hundreds of Gorenstein codimension 4 ideals with 9 × 16 resolutions (that is, nine equations and sixteen first syzygies). Our two basic games are called Tom and Jerry; the main application is the biregular construction of most of the anticanonically polarised Mori Fano 3-folds of Altinok's thesis. There are 115 cases whose numerical data (in effect, the Hilbert series) allow a Type I projection. In every case, at least one Tom and one Jerry construction works, providing at least two deformation families of quasismooth Fano 3-folds having the same numerics but different topology. © 2012 Copyright Foundation Compositio Mathematica.
AU - Brown, Gavin
AU - Kerber, Michael
AU - Reid, Miles
ID - 3120
IS - 4
JF - Compositio Mathematica
TI - Fano 3 folds in codimension 4 Tom and Jerry Part I
VL - 148
ER -
TY - JOUR
AB - Voltage-activated Ca(2+) channels (VACCs) mediate Ca(2+) influx to trigger action potential-evoked neurotransmitter release, but the mechanism by which Ca(2+) regulates spontaneous transmission is unclear. We found that VACCs are the major physiological triggers for spontaneous release at mouse neocortical inhibitory synapses. Moreover, despite the absence of a synchronizing action potential, we found that spontaneous fusion of a GABA-containing vesicle required the activation of multiple tightly coupled VACCs of variable type.
AU - Williams, Courtney
AU - Chen, Wenyan
AU - Lee, Chia
AU - Yaeger, Daniel
AU - Vyleta, Nicholas
AU - Smith, Stephen
ID - 3121
IS - 9
JF - Nature Neuroscience
TI - Coactivation of multiple tightly coupled calcium channels triggers spontaneous release of GABA
VL - 15
ER -
TY - CONF
AB - We introduce the idea of using an explicit triangle mesh to track the air/fluid interface in a smoothed particle hydrodynamics (SPH) simulator. Once an initial surface mesh is created, this mesh is carried forward in time using nearby particle velocities to advect the mesh vertices. The mesh connectivity remains mostly unchanged across time-steps; it is only modified locally for topology change events or for the improvement of triangle quality. In order to ensure that the surface mesh does not diverge from the underlying particle simulation, we periodically project the mesh surface onto an implicit surface defined by the physics simulation. The mesh surface gives us several advantages over previous SPH surface tracking techniques. We demonstrate a new method for surface tension calculations that clearly outperforms the state of the art in SPH surface tension for computer graphics. We also demonstrate a method for tracking detailed surface information (like colors) that is less susceptible to numerical diffusion than competing techniques. Finally, our temporally-coherent surface mesh allows us to simulate high-resolution surface wave dynamics without being limited by the particle resolution of the SPH simulation.
AU - Yu, Jihun
AU - Wojtan, Christopher J
AU - Turk, Greg
AU - Yap, Chee
ID - 3123
IS - 2
T2 - Computer Graphics Forum
TI - Explicit mesh surfaces for particle based fluids
VL - 31
ER -
TY - CONF
AB - We consider the problem of inference in a graphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pairwise terms over a discretized domain. This allows the use of techniques originally developed for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can outperform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.
AU - Korc, Filip
AU - Kolmogorov, Vladimir
AU - Lampert, Christoph
ID - 3124
TI - Approximating marginals using discrete energy minimization
ER -
TY - CONF
AB - We propose a new learning method to infer a mid-level feature representation that combines the advantage of semantic attribute representations with the higher expressive power of non-semantic features. The idea lies in augmenting an existing attribute-based representation with additional dimensions for which an autoencoder model is coupled with a large-margin principle. This construction allows a smooth transition between the zero-shot regime with no training example, the unsupervised regime with training examples but without class labels, and the supervised regime with training examples and with class labels. The resulting optimization problem can be solved efficiently, because several of the necessity steps have closed-form solutions. Through extensive experiments we show that the augmented representation achieves better results in terms of object categorization accuracy than the semantic representation alone.
AU - Sharmanska, Viktoriia
AU - Quadrianto, Novi
AU - Lampert, Christoph
ID - 3125
IS - PART 5
TI - Augmented attribute representations
VL - 7576
ER -
TY - CONF
AB - When searching for characteristic subpatterns in potentially noisy graph data, it appears self-evident that having multiple observations would be better than having just one. However, it turns out that the inconsistencies introduced when different graph instances have different edge sets pose a serious challenge. In this work we address this challenge for the problem of finding maximum weighted cliques.
We introduce the concept of most persistent soft-clique. This is subset of vertices, that 1) is almost fully or at least densely connected, 2) occurs in all or almost all graph instances, and 3) has the maximum weight. We present a measure of clique-ness, that essentially counts the number of edge missing to make a subset of vertices into a clique. With this measure, we show that the problem of finding the most persistent soft-clique problem can be cast either as: a) a max-min two person game optimization problem, or b) a min-min soft margin optimization problem. Both formulations lead to the same solution when using a partial Lagrangian method to solve the optimization problems. By experiments on synthetic data and on real social network data, we show that the proposed method is able to reliably find soft cliques in graph data, even if that is distorted by random noise or unreliable observations.
AU - Quadrianto, Novi
AU - Lampert, Christoph
AU - Chen, Chao
ID - 3127
T2 - Proceedings of the 29th International Conference on Machine Learning
TI - The most persistent soft-clique in a set of sampled graphs
ER -
TY - JOUR
AB - We consider two-player zero-sum stochastic games on graphs with ω-regular winning conditions specified as parity objectives. These games have applications in the design and control of reactive systems. We survey the complexity results for the problem of deciding the winner in such games, and in classes of interest obtained as special cases, based on the information and the power of randomization available to the players, on the class of objectives and on the winning mode. On the basis of information, these games can be classified as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided partial-observation (one player has partial-observation and the other player has complete-observation); and (c) complete-observation (both players have complete view of the game). The one-sided partial-observation games have two important subclasses: the one-player games, known as partial-observation Markov decision processes (POMDPs), and the blind one-player games, known as probabilistic automata. On the basis of randomization, (a) the players may not be allowed to use randomization (pure strategies), or (b) they may choose a probability distribution over actions but the actual random choice is external and not visible to the player (actions invisible), or (c) they may use full randomization. Finally, various classes of games are obtained by restricting the parity objective to a reachability, safety, Büchi, or coBüchi condition. We also consider several winning modes, such as sure-winning (i.e., all outcomes of a strategy have to satisfy the winning condition), almost-sure winning (i.e., winning with probability 1), limit-sure winning (i.e., winning with probability arbitrarily close to 1), and value-threshold winning (i.e., winning with probability at least ν, where ν is a given rational).
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Henzinger, Thomas A
ID - 3128
IS - 2
JF - Formal Methods in System Design
TI - A survey of partial-observation stochastic parity games
VL - 43
ER -
TY - CONF
AB - Let K be a simplicial complex and g the rank of its p-th homology group Hp(K) defined with ℤ2 coefficients. We show that we can compute a basis H of Hp(K) and annotate each p-simplex of K with a binary vector of length g with the following property: the annotations, summed over all p-simplices in any p-cycle z, provide the coordinate vector of the homology class [z] in the basis H. The basis and the annotations for all simplices can be computed in O(n ω ) time, where n is the size of K and ω < 2.376 is a quantity so that two n×n matrices can be multiplied in O(n ω ) time. The precomputed annotations permit answering queries about the independence or the triviality of p-cycles efficiently.
Using annotations of edges in 2-complexes, we derive better algorithms for computing optimal basis and optimal homologous cycles in 1 - dimensional homology. Specifically, for computing an optimal basis of H1(K) , we improve the previously known time complexity from O(n 4) to O(n ω + n 2 g ω − 1). Here n denotes the size of the 2-skeleton of K and g the rank of H1(K) . Computing an optimal cycle homologous to a given 1-cycle is NP-hard even for surfaces and an algorithm taking 2 O(g) nlogn time is known for surfaces. We extend this algorithm to work with arbitrary 2-complexes in O(n ω ) + 2 O(g) n 2logn time using annotations.
AU - Busaryev, Oleksiy
AU - Cabello, Sergio
AU - Chen, Chao
AU - Dey, Tamal
AU - Wang, Yusu
ID - 3129
TI - Annotating simplices with a homology basis and its applications
VL - 7357
ER -
TY - JOUR
AB - Essential genes code for fundamental cellular functions required for the viability of an organism. For this reason, essential genes are often highly conserved across organisms. However, this is not always the case: orthologues of genes that are essential in one organism are sometimes not essential in other organisms or are absent from their genomes. This suggests that, in the course of evolution, essential genes can be rendered nonessential. How can a gene become non-essential? Here we used genetic manipulation to deplete the products of 26 different essential genes in Escherichia coli. This depletion results in a lethal phenotype, which could often be rescued by the overexpression of a non-homologous, non-essential gene, most likely through replacement of the essential function. We also show that, in a smaller number of cases, the essential genes can be fully deleted from the genome, suggesting that complete functional replacement is possible. Finally, we show that essential genes whose function can be replaced in the laboratory are more likely to be non-essential or not present in other taxa. These results are consistent with the notion that patterns of evolutionary conservation of essential genes are influenced by their compensability-that is, by how easily they can be functionally replaced, for example through increased expression of other genes.
AU - Bergmiller, Tobias
AU - Ackermann, Martin
AU - Silander, Olin
ID - 3130
IS - 6
JF - PLoS Genetics
TI - Patterns of evolutionary conservation of essential genes correlate with their compensability
VL - 8
ER -
TY - JOUR
AB - In large populations, many beneficial mutations may be simultaneously available and may compete with one another, slowing adaptation. By finding the probability of fixation of a favorable allele in a simple model of a haploid sexual population, we find limits to the rate of adaptive substitution, Λ, that depend on simple parameter combinations. When variance in fitness is low and linkage is loose, the baseline rate of substitution is Λ 0=2NU〈s〉 is the population size, U is the rate of beneficial mutations per genome, and 〈s〉 is their mean selective advantage. Heritable variance ν in log fitness due to unlinked loci reduces Λ by e -4ν under polygamy and e -8ν under monogamy. With a linear genetic map of length R Morgans, interference is yet stronger. We use a scaling argument to show that the density of adaptive substitutions depends on s, N, U, and R only through the baseline density: Λ/R=F(Λ 0/R). Under the approximation that the interference due to different sweeps adds up, we show that Λ/R~(Λ 0/R)/(1+2Λ 0/R), implying that interference prevents the rate of adaptive substitution from exceeding one per centimorgan per 200 generations. Simulations and numerical calculations confirm the scaling argument and confirm the additive approximation for Λ 0/R 1; for higher Λ 0/R, the rate of adaptation grows above R/2, but only very slowly. We also consider the effect of sweeps on neutral diversity and show that, while even occasional sweeps can greatly reduce neutral diversity, this effect saturates as sweeps become more common-diversity can be maintained even in populations experiencing very strong interference. Our results indicate that for some organisms the rate of adaptive substitution may be primarily recombination-limited, depending only weakly on the mutation supply and the strength of selection.
AU - Weissman, Daniel
AU - Barton, Nicholas H
ID - 3131
IS - 6
JF - PLoS Genetics
TI - Limits to the rate of adaptive substitution in sexual populations
VL - 8
ER -
TY - CONF
AB - This note contributes to the point calculus of persistent homology by extending Alexander duality from spaces to real-valued functions. Given a perfect Morse function f: S n+1 →[0, 1 and a decomposition S n+1 = U ∪ V into two (n + 1)-manifolds with common boundary M, we prove elementary relationships between the persistence diagrams of f restricted to U, to V, and to M.
AU - Edelsbrunner, Herbert
AU - Kerber, Michael
ID - 3133
T2 - Proceedings of the twenty-eighth annual symposium on Computational geometry
TI - Alexander duality for functions: The persistent behavior of land and water and shore
ER -
TY - CONF
AB - We introduce consumption games, a model for discrete interactive system with multiple resources that are consumed or reloaded independently. More precisely, a consumption game is a finite-state graph where each transition is labeled by a vector of resource updates, where every update is a non-positive number or ω. The ω updates model the reloading of a given resource. Each vertex belongs either to player □ or player ◇, where the aim of player □ is to play so that the resources are never exhausted. We consider several natural algorithmic problems about consumption games, and show that although these problems are computationally hard in general, they are solvable in polynomial time for every fixed number of resource types (i.e., the dimension of the update vectors) and bounded resource updates.
AU - Brázdil, Brázdil
AU - Chatterjee, Krishnendu
AU - Kučera, Antonín
AU - Novotny, Petr
ID - 3135
TI - Efficient controller synthesis for consumption games with multiple resource types
VL - 7358
ER -