TY - GEN
AB - Soon, the genetic basis of most human Mendelian diseases will be solved. The next challenge will be to leverage this information to uncover basic mechanisms of disease and develop new therapies. To understand how this transformation is already beginning to unfold, we focus on the ciliopathies, a class of multi-organ diseases caused by disruption of the primary cilium. Through a convergence of data involving mutant gene discovery, proteomics, and cell biology, more than a dozen phenotypically distinguishable conditions are now united as ciliopathies. Sitting at the interface between simple and complex genetic conditions, these diseases provide clues to the future direction of human genetics.
AU - Gaia Novarino
AU - Akizu, Naiara
AU - Gleeson, Joseph G
ID - 2312
IS - 1
T2 - Cell
TI - Modeling human disease in humans: The ciliopathies
VL - 147
ER -
TY - CONF
AB - The binding of polarons, or its absence, is an old and subtle topic. After defining the model we state some recent theorems of ours. First, the transition from many-body collapse to the existence of a thermodynamic limit for N polarons occurs precisely at U = 2α, where U is the electronic Coulomb repulsion and α is the polaron coupling constant. Second, if U is large enough, there is no multi-polaron binding of any kind. We also discuss the Pekar-Tomasevich approximation to the ground state energy, which is valid for large α. Finally, we derive exact results, not reported before, about the one-dimensional toy model introduced by E. P. Gross.
AU - Frank, Rupert L
AU - Lieb, Élliott H
AU - Robert Seiringer
AU - Thomas, Lawrence E
ID - 2320
TI - Binding, stability, and non-binding of multi-polaron systems
ER -
TY - CONF
AB - We derive a sharp bound on the location of non-positive eigenvalues of Schrödinger operators on the half-line with complex-valued potentials.
AU - Frank, Rupert L
AU - Laptev, Ari
AU - Robert Seiringer
ID - 2321
TI - A sharp bound on eigenvalues of Schrödinger operators on the halfline with complex-valued potentials
VL - 214
ER -
TY - JOUR
AB - For an irreducible polynomial in at most two variables the problem of representing power-free integers is investigated.
AU - Timothy Browning
ID - 233
IS - 2
JF - Archiv der Mathematik
TI - Power-free values of polynomials
VL - 96
ER -
TY - JOUR
AB - We investigate the average order of the divisor function at values of binary cubic forms that are reducible over Q and discuss some applications.
AU - Timothy Browning
ID - 234
IS - 3
JF - Journal de Theorie des Nombres de Bordeaux
TI - The divisor problem for binary cubic forms
VL - 23
ER -
TY - JOUR
AB - For given positive integers m and n, we consider the frequency of representations of m/n as a sum of unit fractions.
AU - Browning, Timothy D
AU - Elsholtz, Christian
ID - 235
IS - 2
JF - Illinois Journal of Mathematics
TI - The number of representations of rationals as a sum of unit fractions
VL - 55
ER -
TY - JOUR
AB - An asymptotic formula is established for the number of Q-rational points of bounded height on a nonsingular quartic Del Pezzo surface with a conic bundle structure.
AU - de la Bretèche, Régis
AU - Timothy Browning
ID - 236
IS - 1
JF - Duke Mathematical Journal
TI - Manin's conjecture for quartic Del Pezzo surfaces with a conic fibration
VL - 160
ER -
TY - JOUR
AB - An effective search bound is established for the least non-trivial integer zero of an arbitrary cubic form C ε ℤ[X 1,...,X n], provided that n ≥ 17.
AU - Timothy Browning
AU - Dietmann, Rainer
AU - Elliott, Peter
ID - 239
IS - 3
JF - Mathematische Annalen
TI - Least zero of a cubic form
VL - 352
ER -
TY - JOUR
AB - We resolve several longstanding problems concerning the stability and the absence of multi-particle binding for N≥2 polarons. Fröhlich's 1937 polaron model describes non-relativistic particles interacting with a scalar quantized field with coupling √α, and with each other by Coulomb repulsion of strength U. We prove the following: (i) While there is a known thermodynamic instability for U<2α, stability of matter does hold for U>2α, that is, the ground state energy per particle has a finite limit as N→∞. (ii) There is no binding of any kind if U exceeds a critical value that depends on α but not on N. The same results are shown to hold for the Pekar-Tomasevich model.
AU - Frank, Rupert L
AU - Lieb, Élliott H
AU - Robert Seiringer
AU - Thomas, Lawrence E
ID - 2390
IS - 1
JF - Publications Mathematiques de l Institut des Hautes Etudes Scientifiques
TI - Stability and absence of binding for multi-polaron systems
VL - 113
ER -
TY - JOUR
AB - The change in energy of an ideal Fermi gas when a local one-body potential is inserted into the system, or when the density is changed locally, are important quantities in condensed matter physics. We show that they can be rigorously bounded from below by a universal constant times the value given by the semiclassical approximation.
AU - Frank, Rupert L
AU - Lewin, Mathieu
AU - Lieb, Élliott H
AU - Robert Seiringer
ID - 2391
IS - 15
JF - Physical Review Letters
TI - Energy cost to make a hole in the fermi sea
VL - 106
ER -
TY - JOUR
AB - We investigate the low energy excitation spectrum of a Bose gas with weak, long range repulsive interactions. In particular, we prove that the Bogoliubov spectrum of elementary excitations with linear dispersion relation for small momentum becomes exact in the mean-field limit.
AU - Robert Seiringer
ID - 2393
IS - 2
JF - Communications in Mathematical Physics
TI - The excitation spectrum for weakly interacting Bosons
VL - 306
ER -
TY - JOUR
AB - Let EMBEDk→d be the following algorithmic problem: Given a finite simplicial complex K of dimension at most k, does there exist a (piecewise linear) embedding of K into Rd? Known results easily imply the polynomiality of EMBEDk→2 (k = 1; 2; the case k = 1, d = 2 is graph planarity) and of EMBEDk→2k for all k ≥ 3. We show that the celebrated result of Novikov on the algorithmic unsolvability of recognizing the 5-sphere implies that EMBEDd→d and EMBED (d-1)→d are undecidable for each d ≥ 5. Our main result is the NP-hardness of EMBED2→4 and, more generally, of EMBED k→d for all k; d with d ≥ 4 and d ≥ k ≥ (2d - 2)/3. These dimensions fall outside the metastable range of a theorem of Haefliger and Weber, which characterizes embeddability using the deleted product obstruction. Our reductions are based on examples, due to Segal, Spież, Freedman, Krushkal, Teichner, and Skopenkov, showing that outside the metastable range the deleted product obstruction is not sufficient to characterize embeddability.
AU - Matoušek, Jiří
AU - Martin Tancer
AU - Uli Wagner
ID - 2436
IS - 2
JF - Journal of the European Mathematical Society
TI - Hardness of embedding simplicial complexes in Rd
VL - 13
ER -
TY - CONF
AB - We introduce a new notion of minors for simplicial complexes (hypergraphs), so-called homological minors. Our motivation is to propose a general approach to attack certain extremal problems for sparse simplicial complexes and the corresponding threshold problems for random complexes. In this paper, we focus on threshold problems. The basic model for random complexes is the Linial-Meshulam model Xk(n, p). By definition, such a complex has n vertices, a complete (k -1)-dimensional skeleton, and every possible k-dimensional simplex is chosen independently with probability p. We show that for every k, t≥ 1, there is a constant C = C(k, t) such that for p≥ C/n, the random complex Xk(n, p) asymptotically almost surely contains K tk (the complete k-dimensional complex on t vertices) as a homological minor. As corollary, the threshold for (topological) embeddability of Xk(n, p) into R2k is at p = θ(1/n). The method can be extended to other models of random complexes (for which the lower skeleta are not necessarily complete) and also to more general Tverberg-type problems, where instead of continuous maps without doubly covered image points (embeddings), we consider maps without qfold covered image points.
AU - Uli Wagner
ID - 2437
TI - Minors in random and expanding hypergraphs
ER -
TY - JOUR
AB - Within a multicellular tissue cells may coordinately form a singular or multiple polar axes, but it is unclear whether a common mechanism governs different types of polar axis formation. The phosphorylation status of PIN proteins, which is directly affected by the PINOID (PID) protein kinase and the PP2A protein phosphatase, is known to regulate the apical-basal polarity of PIN localization in bipolar cells of roots and shoot apices. Here, we provide evidence that the phosphorylation status-mediated PIN polarity switch is widely used to modulate cellular processes in Arabidopsis including multipolar pavement cells (PC) with interdigitated lobes and indentations. The degree of PC interdigitation was greatly reduced either when the FYPP1 gene, which encodes a PP2A called phytochrome-associated serine/threonine protein phosphatase, was knocked out or when the PID gene was overexpressed (35S:PID). These genetic modifications caused PIN1 localization to switch from lobe to indentation regions. The PP2A and PID mediated switching of PIN1 localization is strikingly similar to their regulation of the apical-basal polarity switch of PIN proteins in other cells. Our findings suggest a common mechanism for the regulation of PIN1 polarity formation, a fundamental cellular process that is crucial for pattern formation both at the tissue/organ and cellular levels.
AU - Hongjiang Li
AU - Lin, Deshu
AU - Dhonukshe, Pankaj B
AU - Nagawa, Shingo
AU - Chen, Dandan
AU - Jirí Friml
AU - Scheres, Ben
AU - Guo, Hongwei
AU - Yang, Zhenbiao
ID - 2454
IS - 6
JF - Cell Research
TI - Phosphorylation switch modulates the interdigitated pattern of PIN1 localization and cell expansion in Arabidopsis leaf epidermis
VL - 21
ER -
TY - JOUR
AB - In unicellular and multicellular organisms, cell polarity is essential for a wide range of biological processes. An important feature of cell polarity is the asymmetric distribution of proteins in or at the plasma membrane. In plants such polar localized proteins play various specific roles ranging from organizing cell morphogenesis, asymmetric cell division, pathogen defense, nutrient transport and establishment of hormone gradients for developmental patterning. Moreover, flexible respecification of cell polarities enables plants to adjust their physiology and development to environmental changes. Having evolved multicellularity independently and lacking major cell polarity mechanisms of animal cells, plants came up with alternative solutions to generate and respecify cell polarity as well as to regulate polar domains at the plasma membrane.
AU - Dettmer, Jan
AU - Friml, Jirí
ID - 2460
IS - 6
JF - Current Opinion in Cell Biology
TI - Cell polarity in plants: When two do the same, it is not the same...
VL - 23
ER -
TY - JOUR
AB - Parkinson's disease is a common neurodegenerative disorder characterized by a profound motor disability that is traceable to the emergence of synchronous, rhythmic spiking in neurons of the external segment of the globus pallidus (GPe). The origins of this pathophysiology are poorly defined for the generation of pacemaking. After the induction of a parkinsonian state in mice, there was a progressive decline in autonomous GPe pacemaking, which normally serves to desynchronize activity. The loss was attributable to the downregulation of an ion channel that is essential in pacemaking, the hyperpolarization and cyclic nucleotide-gated (HCN) channel. Viral delivery of HCN2 subunits restored pacemaking and reduced burst spiking in GPe neurons. However, the motor disability induced by dopamine (DA) depletion was not reversed, suggesting that the loss of pacemaking was a consequence, rather than a cause, of key network pathophysiology, a conclusion that is consistent with the ability of L-type channel antagonists to attenuate silencing after DA depletion.
AU - Chan, Savio
AU - Glajch, Kelly E
AU - Gertler, Tracy S
AU - Guzmán, Jaime N
AU - Mercer, Jeff N
AU - Lewis, Alan S
AU - Goldberg, Alan B
AU - Tkatch, Tatiana
AU - Ryuichi Shigemoto
AU - Fleming, Sheila M
AU - Chetkovich, Dane M
AU - Osten, Pavel
AU - Kita, Hitoshi
AU - Surmeier, James D
ID - 2511
IS - 1
JF - Nature Neuroscience
TI - HCN channelopathy in external globus pallidus neurons in models of Parkinson s disease
VL - 14
ER -
TY - JOUR
AB - GABAergic inhibition plays a central role in the control of pyramidal cell ensemble activities; thus, any signaling mechanism that regulates inhibition is able to fine-tune network patterns. Here, we provide evidence that the retrograde nitric oxide (NO)- cGMP cascade triggered by NMDA receptor (NMDAR) activation plays a role in the control of hippocampal GABAergic transmission in mice. GABAergic synapses express neuronal nitric oxide synthase (nNOS) postsynaptically and NO receptors (NO-sensitive guanylyl cyclase) in the presynaptic terminals. We hypothesized that-similar to glutamatergic synapses-the Ca 2+ transients required to activate nNOS were provided by NMDA receptor activation. Indeed, administration of 5 μm NMDA induced a robust nNOS-dependent cGMP production in GABAergic terminals, selectively in the CA1 and CA3c areas. Furthermore, using preembedding, postembedding, and SDS-digested freeze-fracture replica immunogold labeling, we provided quantitative immunocytochemical evidence that NMDAR subunits GluN1, GluN2A, and GluN2B were present in most somatic GABAergic synapses postsynaptically. These data indicate that NMDARs can modulate hippocampal GABAergic inhibition via NO- cGMP signaling in an activity-dependent manner and that this effect is subregion specific in the mouse hippocampus.
AU - Szabadits, Eszter
AU - Cserép, Csaba
AU - Szonyi, András
AU - Fukazawa, Yugo
AU - Ryuichi Shigemoto
AU - Watanabe, Masahiko
AU - Itohara, Shigeyoshi
AU - Freund, Tamás F
AU - Nyíri, Gábor
ID - 2512
IS - 16
JF - Journal of Neuroscience
TI - NMDA receptors in hippocampal GABAergic synapses and their role in nitric oxide signaling
VL - 31
ER -
TY - JOUR
AB - SK2-containing channels are expressed in the postsynaptic density (PSD) of dendritic spines on mouse hippocampal area CA1 pyramidal neurons and influence synaptic responses, plasticity and learning. The Sk2 gene (also known as Kcnn2) encodes two isoforms that differ only in the length of their N-terminal domains. SK2-long (SK2-L) and SK2-short (SK2-S) are coexpressed in CA1 pyramidal neurons and likely form heteromeric channels. In mice lacking SK2-L (SK2-S only mice), SK2-S-containing channels were expressed in the extrasynaptic membrane, but were excluded from the PSD. The SK channel contribution to excitatory postsynaptic potentials was absent in SK2-S only mice and was restored by SK2-L re-expression. Blocking SK channels increased the amount of long-term potentiation induced in area CA1 in slices from wild-type mice but had no effect in slices from SK2-S only mice. Furthermore, SK2-S only mice outperformed wild-type mice in the novel object recognition task. These results indicate that SK2-L directs synaptic SK2-containing channel expression and is important for normal synaptic signaling, plasticity and learning.
AU - Allen, Duane H
AU - Bond, Chris T
AU - Luján, Rafael
AU - Ballesteros-Merino, Carmen
AU - Lin, Michael T
AU - Wang, Kang
AU - Klett, Nathan
AU - Watanabe, Masahiko
AU - Ryuichi Shigemoto
AU - Stackman, Robert W
AU - Maylie, James G
AU - Adelman, John P
ID - 2513
IS - 6
JF - Nature Neuroscience
TI - The SK2-long isoform directs synaptic localization and function of SK2-containing channels
VL - 14
ER -
TY - JOUR
AB - We consider Hermitian and symmetric random band matrices H in d ≥ 1 dimensions. The matrix elements H xy, indexed by, are independent, uniformly distributed random variables if {pipe}x-y{pipe} is less than the band width W, and zero otherwise. We prove that the time evolution of a quantum particle subject to the Hamiltonian H is diffusive on time scales. We also show that the localization length of the eigenvectors of H is larger than a factor W d/6 times the band width. All results are uniform in the size of the matrix.
AU - László Erdös
AU - Knowles, Antti
ID - 2717
IS - 2
JF - Communications in Mathematical Physics
TI - Quantum diffusion and eigenfunction delocalization in a random band matrix model
VL - 303
ER -
TY - JOUR
AB - Consider the Dyson Brownian motion with parameter β, where β=1,2,4 corresponds to the eigenvalue flows for the eigenvalues of symmetric, hermitian and quaternion self-dual ensembles. For any β≥1, we prove that the relaxation time to local equilibrium for the Dyson Brownian motion is bounded above by N -ζ for some ζ> 0. The proof is based on an estimate of the entropy flow of the Dyson Brownian motion w. r. t. a "pseudo equilibrium measure". As an application of this estimate, we prove that the eigenvalue spacing statistics in the bulk of the spectrum for N×N symmetric Wigner ensemble is the same as that of the Gaussian Orthogonal Ensemble (GOE) in the limit N→∞. The assumptions on the probability distribution of the matrix elements of the Wigner ensemble are a subexponential decay and some minor restriction on the support.
AU - László Erdös
AU - Schlein, Benjamin
AU - Yau, Horng-Tzer
ID - 2764
IS - 1
JF - Inventiones Mathematicae
TI - Universality of random matrices and local relaxation flow
VL - 185
ER -
TY - GEN
AB - This is a study of the universality of spectral statistics for large random matrices. Considered are N×N symmetric, Hermitian, or quaternion self-dual random matrices with independent identically distributed entries (Wigner matrices), where the probability distribution of each matrix element is given by a measure v with zero expectation and with subexponential decay. The main result is that the correlation functions of the local eigenvalue statistics in the bulk of the spectrum coincide with those of the Gaussian Orthogonal Ensemble (GOE), the Gaussian Unitary Ensemble (GUE), and the Gaussian Symplectic Ensemble (GSE), respectively, in the limit as N → ∞. This approach is based on a study of the Dyson Brownian motion via a related new dynamics, the local relaxation flow. As a main input, it is established that the density of the eigenvalues converges to the Wigner semicircle law, and this holds even down to the smallest possible scale. Moreover, it is shown that the eigenvectors are completely delocalized. These results hold even without the condition that the matrix elements are identically distributed: only independence is used. In fact, for the matrix elements of the Green function strong estimates are given that imply that the local statistics of any two ensembles in the bulk are identical if the first four moments of the matrix elements match. Universality at the spectral edges requires matching only two moments. A Wigner-type estimate is also proved, and it is shown that the eigenvalues repel each other on arbitrarily small scales.
AU - László Erdös
ID - 2765
IS - 3
T2 - Russian Mathematical Surveys
TI - Universality of Wigner random matrices: A survey of recent results
VL - 66
ER -
TY - JOUR
AB - We consider Hermitian and symmetric random band matrices H in d ≥ dimensions. The matrix elements Hxy, indexed by x,y ∈ Λ ⊂ ℤd are independent and their variances satisfy σ2xy:= E{pipe}Hxy{pipe}2 = W-d f((x-y)/W for some probability density f. We assume that the law of each matrix element Hxy is symmetric and exhibits subexponential decay. We prove that the time evolution of a quantum particle subject to the Hamiltonian H is diffusive on time scales ≪ Wd/3. We also show that the localization length of the eigenvectors of H is larger than a factor Wd/6 times the band width W. All results are uniform in the size {pipe}Λ{pipe} of the matrix. This extends our recent result (Erdo{double acute}s and Knowles in Commun. Math. Phys., 2011) to general band matrices. As another consequence of our proof we show that, for a larger class of random matrices satisfying Σx σ2xy for all y, the largest eigenvalue of H is bounded with high probability by 2+M-2/3+e{open} for any e{open} > 0, where M:= 1/(maxx,y σ2xy).
AU - László Erdös
AU - Knowles, Antti
ID - 2766
IS - 7
JF - Annales Henri Poincare
TI - Quantum diffusion and delocalization for band matrices with general distribution
VL - 12
ER -
TY - JOUR
AB - Shear flows undergo a sudden transition from laminar to turbulent motion as the velocity increases, and the onset of turbulence radically changes transport efficiency and mixing properties. Even for the well-studied case of pipe flow, it has not been possible to determine at what Reynolds number the motion will be either persistently turbulent or ultimately laminar. We show that in pipes, turbulence that is transient at low Reynolds numbers becomes sustained at a distinct critical point. Through extensive experiments and computer simulations, we were able to identify and characterize the processes ultimately responsible for sustaining turbulence. In contrast to the classical Landau-Ruelle-Takens view that turbulence arises from an increase in the temporal complexity of fluid motion, here, spatial proliferation of chaotic domains is the decisive process and intrinsic to the nature of fluid turbulence.
AU - Avila, Kerstin
AU - Moxey, David
AU - de Lózar, Alberto
AU - Avila, Marc
AU - Barkley, Dwight
AU - Björn Hof
ID - 2799
IS - 6039
JF - Science
TI - The onset of turbulence in pipe flow
VL - 333
ER -
TY - JOUR
AB - In shear flows, turbulence first occurs in the form of localized structures (puffs/spots) surrounded by laminar fluid. We here investigate such spatially intermittent flows in a pipe experiment showing that turbulent puffs have a well-defined interaction distance, which sets their minimum spacing as well as the maximum observable turbulent fraction. Two methodologies are employed. Starting from a laminar flow, puffs are first created by locally injecting a jet of fluid through the pipe wall. When the perturbation is applied periodically at low frequencies, as expected, a regular sequence of puffs is observed where the puff spacing is given by the ratio of the mean flow speed to the perturbation frequency. At large frequencies however puffs are found to interact and annihilate each other. Varying the perturbation frequency, an interaction distance is determined which sets the highest possible turbulence fraction. This enables us to establish an upper bound for the friction factor in the transitional regime, which provides a well-defined link between the Blasius and the Hagen-Poiseuille friction laws. In the second set of experiments, the Reynolds number is reduced suddenly from fully turbulent to the intermittent regime. The resulting flow reorganizes itself to a sequence of constant size puffs which, unlike in Couette and Taylor–Couette flow are randomly spaced. The minimum distance between the turbulent patches is identical to the puff interaction length. The puff interaction length is found to be in agreement with the wavelength of regular stripe and spiral patterns in plane Couette and Taylor–Couette flow.
AU - Samanta, Devranjan
AU - de Lózar, Alberto
AU - Björn Hof
ID - 2800
JF - Journal of Fluid Mechanics
TI - Experimental investigation of laminar turbulent intermittency in pipe flow
VL - 681
ER -
TY - CONF
AB - Turbulent puffs in pipe flow are characterized by a sharp laminar-turbulent interface at the trailing edge and a more diffused leading interface. It is known that these laminar-turbulent interfaces propagate at a speed that is approximately equal to the flow rate. Our results from direct numerical simulation show that, locally, the interface velocity relative to the fluid (i) counteracts the advection due to the laminar velocity profile so that the puff can preserve its characteristic overall shape, (ii) is very small in magnitude, but involves a large interface area so that the global propagation velocity relative to the mean flow can be large and (iii) is determined by both inertial and viscous effects. The analysis provides some new insights into the mechanisms that sustain or expand localized turbulence and might be relevant for the design of new control strategies.
AU - Holzner, Markus
AU - Avila, Marc
AU - de Lózar, Alberto
AU - Björn Hof
ID - 2801
IS - 5
TI - A Lagrangian approach to the interface velocity of turbulent puffs in pipe flow
VL - 318
ER -
TY - JOUR
AB - Despite their relatively simple appearance, roots are incredibly complex organs that are highly adapted to differing environments. Many aspects of root development are co-ordinated by subtle spatial differences in the concentrations of the phytohormones auxin and cytokinin. Events from the formation of a root during embryogenesis to the determination of the network of lateral roots are controlled by interactions between these hormones. Recently, interactions have been defined where auxin signaling promotes the expression of cytokinin signaling inhibitors, cytokinin signaling promotes the expression of auxin signaling inhibitors and finally where cytokinin signaling regulates the complex network of auxin transport proteins to position zones of high auxin signaling. We are witnessing a period of discovery in which we are beginning to understand how these hormonal pathways communicate to regulate root formation.
AU - Bishopp, Anthony
AU - Eva Benková
AU - Helariutta, Ykä
ID - 2871
IS - 1
JF - Current Opinion in Plant Biology
TI - Sending mixed messages: Auxin-cytokinin crosstalk in roots
VL - 14
ER -
TY - JOUR
AB - The apical hook develops in the upper part of the hypocotyl when seeds buried in the soil germinate, and serves to protect cotyledons and the shoot apical meristem from possible damage caused by pushing through the soil. The curvature is formed through differential cell growth that occurs at the two opposite sides of the hypocotyl, and it is established by a gradient of auxin activity and refined by the coordinated action of auxin and ethylene. Here we show that gibberellins (GAs) promote hook development through the transcriptional regulation of several genes of the ethylene and auxin pathways in Arabidopsis. The level of GA activity determines the speed of hook formation and the extent of the curvature during the formation phase independently of ethylene, probably by modulating auxin transport and response through HLS1, PIN3, and PIN7. Moreover, GAs cooperate with ethylene in preventing hook opening, in part through the induction of ethylene production mediated by ACS5/ETO2 and ACS8.
AU - Gallego-Bartolomé, Javier
AU - Arana, María V
AU - Vandenbussche, Filip
AU - Žádníková, Petra
AU - Minguet, Eugenio G
AU - Guardiola, Vicente
AU - Van Der Straeten, Dominique
AU - Eva Benková
AU - Alabadí, David
AU - Blázquez, Miguel A
ID - 2874
IS - 4
JF - Plant Journal
TI - Hierarchy of hormone action controlling apical hook development in Arabidopsis
VL - 67
ER -
TY - JOUR
AU - Tiago Paixao
AU - Azevedo, Ricardo B
ID - 2897
IS - 7
JF - PLoS Computational Biology
TI - Redundancy and the Evolution of Cis Regulatory Element Multiplicity
VL - 6
ER -
TY - JOUR
AB - Sex allocation theory has been remarkably successful at explaining the prevalence of even sex ratios in natural populations and at identifying specific conditions that can result in biased sex ratios. Much of this theory focuses on parental sex determination (SD) strategies. Here, we consider instead the evolutionary causes and consequences of mixed offspring SD strategies, in which the genotype of an individual determines not its sex, but the probability of developing one of multiple sexes. We find that alleles specifying mixed offspring SD strategies can generally outcompete alleles that specify pure strategies, but generate constraints that may prevent a population from reaching an even sex ratio. We use our model to analyze sex ratios in natural populations of Tetrahymena thermophila, a ciliate with seven sexes determined by mixed SD alleles. We show that probabilistic SD is sufficient to account for the occurrence of skewed sex ratios in natural populations of T. thermophila, provided that their effective population sizes are small. Our results highlight the importance of genetic drift in sex ratio evolution and suggest that mixed offspring SD strategies should be more common than currently thought.
AU - Tiago Paixao
AU - Phadke, Sujal S
AU - Azevedo, Ricardo B
AU - Zufall, Rebecca A
ID - 2898
IS - 7
JF - Evolution; International Journal of Organic Evolution
TI - Sex ratio evolution under probabilistic sex determination
VL - 65
ER -
TY - CHAP
AU - Vicente, Sara
AU - Vladimir Kolmogorov
AU - Rother, Carsten
ED - Blake, Andrew
ED - Kohli, Pushmeet
ED - Rother, Carsten
ID - 2922
T2 - Markov Random Fields for Vision and Image Processing
TI - Graph-cut Based Image Segmentation with Connectivity Priors
ER -
TY - CHAP
AU - Kumar, M Pawan
AU - Vladimir Kolmogorov
AU - Torr, Philip H
ED - Blake, Andrew
ED - Kohli, Pushmeet
ED - Rother, Carsten
ID - 2923
T2 - Markov Random Fields for Vision and Image Processing
TI - Analyzing Convex Relaxations for MAP Estimation
ER -
TY - CHAP
AU - Criminisi, Antonio
AU - Cross, Geoffrey
AU - Blake, Andrew
AU - Vladimir Kolmogorov
ED - Blake, Andrew
ED - Kohli, Pushmeet
ED - Rother, Carsten
ID - 2924
T2 - Markov Random Fields for Vision and Image Processing
TI - Bilayer Segmentation of Video
ER -
TY - CHAP
AU - Rother, Carsten
AU - Vladimir Kolmogorov
AU - Boykov, Yuri
AU - Blake, Andrew
ED - Blake, Andrew
ED - Kohli, Pushmeet
ED - Rother, Carsten
ID - 2925
T2 - Markov Random Fields for Vision and Image Processing
TI - Interactive Foreground Extraction using graph cut
ER -
TY - CHAP
AU - Boykov, Yuri
AU - Vladimir Kolmogorov
ED - Blake, Andrew
ED - Kohli, Pushmeet
ED - Rother, Carsten
ID - 2935
T2 - Markov Random Fields for Vision and Image Processing
TI - Basic graph cut algorithms
ER -
TY - CONF
AB - Traditional statistical methods for the confidentiality protection for statistical databases do not scale well to deal with GWAS (genome-wide association studies) databases and external information on them. The more recent concept of differential privacy, introduced by the cryptographic community, is an approach which provides a rigorous definition of privacy with meaningful privacy guarantees in the presence of arbitrary external information. Building on such notions, we propose new methods to release aggregate GWAS data without compromising an individual's privacy. We present methods for releasing differentially private minor allele frequencies, chi-square statistics and p-values. We compare these approaches on simulated data and on a GWAS study of canine hair length involving 685 dogs. We also propose a privacy-preserving method for finding genome-wide associations based on a differentially private approach to penalized logistic regression.
AU - Fienberg, Stephen E
AU - Slavkovic, Aleksandra
AU - Caroline Uhler
ID - 2960
TI - Privacy Preserving GWAS Data Sharing
ER -
TY - JOUR
AB - Rapid research progress in genotyping techniques have allowed large genome-wide association studies. Existing methods often focus on determining associations between single loci and a specic phenotype. However, a particular phenotype is usually the result of complex relationships between multiple loci and the environment. In this paper, we describe a two-stage method for detecting epistasis by combining the traditionally used single-locus search with a search for multiway interactions. Our method is based on an extended version of Fisher's exact test. To
perform this test, a Markov chain is constructed on the space of multidimensional contingency tables using the elements of a Markov basis as moves. We test our method on simulated data and compare it to a two-stage logistic regression method and to a fully Bayesian method, showing that we are able to detect the interacting loci when other methods fail to do so. Finally, we apply our method to a genome-wide data set consisting of 685 dogs and identify epistasis associated with canine hair length for four pairs of single nucleotide polymorphisms (SNPs).
AU - Malaspinas, Anna-Sapfo
AU - Caroline Uhler
ID - 2961
IS - 1
JF - Journal of Algebraic Statistics
TI - Detecting epistasis via Markov bases
VL - 2
ER -
TY - CONF
AB - Zero-knowledge proofs of knowledge (ZK-PoK) for discrete logarithms and related problems are indispensable for practical cryptographic protocols. Recently, Camenisch, Kiayias, and Yung provided a specification language (the CKY-language) for such protocols which allows for a modular design and protocol analysis: for every zero-knowledge proof specified in this language, protocol designers are ensured that there exists an efficient protocol which indeed proves the specified statement.
However, the protocols resulting from their compilation techniques only satisfy the classical notion of ZK-PoK, which is not retained are when they used as building blocks for higher-level applications or composed with other protocols.
This problem can be tackled by moving to the Universal Composability (UC) framework, which guarantees retention of security when composing protocols in arbitrary ways.
While there exist generic transformations from $\Sigma$-protocols to UC-secure protocols, these transformation are often too inefficient for practice.
In this paper we introduce a specification language akin to the CKY-language and a compiler such that the resulting protocols are UC-secure and efficient.
To this end, we propose an extension of the UC-framework addressing the
issue that UC-secure zero-knowledge proofs are by definition proofs of knowledge, and state a special composition theorem which allows one to use the weaker -- but more efficient and often sufficient -- notion of proofs of membership in the UC-framework.
We believe that our contributions enable the design of practically efficient protocols that are UC-secure and thus themselves can be used as building blocks.
AU - Camenisch, Jan
AU - Stephan Krenn
AU - Shoup, Victor
ED - Lee, Dong Hoon
ED - Wang, Xiaoyun
ID - 2975
TI - A Framework for Practical Universally Composable Zero-Knowledge Protocols
VL - 7073
ER -
TY - CONF
AB - Side channel attacks on cryptographic systems exploit information
gained from physical implementations rather than theoretical
weaknesses of a scheme. In recent years, major achievements were made
for the class of so called access-driven cache attacks. Such attacks
exploit the leakage of the memory locations accessed by a victim
process.
In this paper we consider the AES block cipher and present an attack
which is capable of recovering the full secret key in almost realtime
for AES-128, requiring only a very limited number of observed
encryptions. Unlike previous attacks, we do not require any
information about the plaintext (such as its distribution, etc.).
Moreover, for the first time, we also show how the plaintext can be
recovered without having access to the ciphertext at all. It is the
first working attack on AES implementations using compressed
tables. There, no efficient techniques to identify the beginning
of AES rounds is known, which is the fundamental assumption underlying previous
attacks.
We have a fully working implementation of our attack which is able to
recover AES keys after observing as little as 100 encryptions. It
works against the OpenSSL 0.9.8n implementation of AES on Linux
systems. Our spy process does not require any special privileges
beyond those of a standard Linux user. A contribution of probably
independent interest is a denial of service attack on the task scheduler of
current Linux systems (CFS), which allows one to observe (on average)
every single memory access of a victim process.
AU - Gullasch, David
AU - Bangerter, Endre
AU - Stephan Krenn
ID - 2976
TI - Cache Games - Bringing Access-Based Cache Attacks on AES to Practice
ER -
TY - CONF
AB - Cryptographic two-party protocols are used ubiquitously in
everyday life. While some of these protocols are easy to
understand and implement (e.g., key exchange or transmission of
encrypted data), many of them are much more complex (e.g.,
e-banking and e-voting applications, or anonymous authentication
and credential systems).
For a software engineer without appropriate cryptographic skills
the implementation of such protocols is often difficult, time
consuming and error-prone. For this reason, a number of compilers
supporting programmers have been published in recent
years. However, they are either designed for very specific
cryptographic primitives (e.g., zero-knowledge proofs of
knowledge), or they only offer a very low level of abstraction and
thus again demand substantial mathematical and cryptographic
skills from the programmer. Finally, some of the existing
compilers do not produce executable code, but only metacode which
has to be instantiated with mathematical libraries, encryption
routines, etc. before it can actually be used.
In this paper we present a cryptographically aware compiler which
is equally useful to cryptographers who want to benchmark
protocols designed on paper, and to programmers who want to
implement complex security sensitive protocols without having to
understand all subtleties. Our tool offers a high level of
abstraction and outputs well-structured and documented Java
code. We believe that our compiler can contribute to shortening
the development cycles of cryptographic applications and to
reducing their error-proneness.
AU - Bangerter, Endre
AU - Stephan Krenn
AU - Seifriz, Martial
AU - Ultes-Nitsche, Ulrich
ED - Venter, Hein S.
ED - Coetzee, Marijke
ED - Loock, Marianne
ID - 2977
TI - cPLC - A Cryptographic Programming Language and Compiler
ER -
TY - JOUR
AB - Chandelier (axoaxonic) cells (ChCs) are a distinct group of GABAergic interneurons that innervate the axon initial segments of pyramidal cells. However, their circuit role and the function of their clearly defined anatomical specificity remain unclear. Recent work has demonstrated that chandelier cells can produce depolarizing GABAergic PSPs, occasionally driving postsynaptic targets to spike. On the other hand, other work suggests that ChCs are hyperpolarizing and may have an inhibitory role. These disparate functional effects may reflect heterogeneity among ChCs. Here, using brain slices from transgenic mouse strains, we first demonstrate that, across different neocortical areas and genetic backgrounds, upper Layer 2/3 ChCs belong to a single electrophysiologically and morphologically defined population, extensively sampling Layer 1 inputs with asymmetric dendrites. Consistent with being a single cell type, we find electrical coupling between ChCs. We then investigate the effect of chandelier cell activation on pyramidal neuron spiking in several conditions, ranging from the resting membrane potential to stimuli designed to approximate in vivo membrane potential dynamics. We find that under quiescent conditions, chandelier cells are capable of both promoting and inhibiting spike generation, depending on the postsynaptic membrane potential. However, during in vivo-like membrane potential fluctuations, the dominant postsynaptic effect was a strong inhibition. Thus, neocortical chandelier cells, even from within a homogeneous population, appear to play a dual role in the circuit, helping to activate quiescent pyramidal neurons, while at the same time inhibiting active ones.
AU - Woodruff, A. R.
AU - McGarry, L. M.
AU - Vogels, Tim P
AU - Inan, M.
AU - Anderson, S. A.
AU - Yuste, R.
ID - 8025
IS - 49
JF - Journal of Neuroscience
SN - 0270-6474
TI - State-dependent function of neocortical chandelier cells
VL - 31
ER -
TY - JOUR
AB - Cortical neurons receive balanced excitatory and inhibitory synaptic currents. Such a balance could be established and maintained in an experience-dependent manner by synaptic plasticity at inhibitory synapses. We show that this mechanism provides an explanation for the sparse firing patterns observed in response to natural stimuli and fits well with a recently observed interaction of excitatory and inhibitory receptive field plasticity. The introduction of inhibitory plasticity in suitable recurrent networks provides a homeostatic mechanism that leads to asynchronous irregular network states. Further, it can accommodate synaptic memories with activity patterns that become indiscernible from the background state but can be reactivated by external stimuli. Our results suggest an essential role of inhibitory plasticity in the formation and maintenance of functional cortical circuitry.
AU - Vogels, Tim P
AU - Sprekeler, H.
AU - Zenke, F.
AU - Clopath, C.
AU - Gerstner, W.
ID - 8074
IS - 6062
JF - Science
SN - 0036-8075
TI - Inhibitory plasticity balances excitation and inhibition in sensory pathways and memory networks
VL - 334
ER -
TY - JOUR
AB - Nonsymmetric motion: Solid‐state NMR measurements of dipolar coupling tensors provide insight into protein dynamics. The hitherto ignored asymmetry of the dipolar coupling tensor contains valuable information about motional asymmetry, which was used in the first direct site‐resolved measurement of such tensors. Important motions such as rotamer jumps can now be directly detected in the solid state.
AU - Schanda, Paul
AU - Huber, Matthias
AU - Boisbouvier, Jérôme
AU - Meier, Beat H.
AU - Ernst, Matthias
ID - 8464
IS - 46
JF - Angewandte Chemie International Edition
SN - 1433-7851
TI - Solid-state NMR measurements of asymmetric dipolar couplings provide insight into protein side-chain motion
VL - 50
ER -
TY - JOUR
AU - Lalli, Daniela
AU - Schanda, Paul
AU - Chowdhury, Anup
AU - Retel, Joren
AU - Hiller, Matthias
AU - Higman, Victoria A.
AU - Handel, Lieselotte
AU - Agarwal, Vipin
AU - Reif, Bernd
AU - van Rossum, Barth
AU - Akbey, Ümit
AU - Oschkinat, Hartmut
ID - 8468
IS - 4
JF - Journal of Biomolecular NMR
SN - 0925-2738
TI - Three-dimensional deuterium-carbon correlation experiments for high-resolution solid-state MAS NMR spectroscopy of large proteins
VL - 51
ER -
TY - JOUR
AB - The accurate experimental determination of dipolar-coupling constants for one-bond heteronuclear dipolar couplings in solids is a key for the quantification of the amplitudes of motional processes. Averaging of the dipolar coupling reports on motions on time scales up to the inverse of the coupling constant, in our case tens of microseconds. Combining dipolar-coupling derived order parameters that characterize the amplitudes of the motion with relaxation data leads to a more precise characterization of the dynamical parameters and helps to disentangle the amplitudes and the time scales of the motional processes, which impact relaxation rates in a highly correlated way. Here. we describe and characterize an improved experimental protocol – based on REDOR – to measure these couplings in perdeuterated proteins with a reduced sensitivity to experimental missettings. Because such effects are presently the dominant source of systematic errors in experimental dipolar-coupling measurements, these compensated experiments should help to significantly improve the precision of such data. A detailed comparison with other commonly used pulse sequences (T-MREV, phase-inverted CP,R18 5/2, and R18 7/1) is provided.
AU - Schanda, Paul
AU - Meier, Beat H.
AU - Ernst, Matthias
ID - 8469
IS - 2
JF - Journal of Magnetic Resonance
KW - Nuclear and High Energy Physics
KW - Biophysics
KW - Biochemistry
KW - Condensed Matter Physics
SN - 1090-7807
TI - Accurate measurement of one-bond H–X heteronuclear dipolar couplings in MAS solid-state NMR
VL - 210
ER -
TY - JOUR
AB - Adding a new dimension: 4D or 3D proton‐detected spectra of perdeuterated protein samples with 1H labelled amides and methyl groups permit collecting unambiguous distance restraints with high sensitivity and determining protein structure by solid‐state NMR (see picture).
AU - Huber, Matthias
AU - Hiller, Sebastian
AU - Schanda, Paul
AU - Ernst, Matthias
AU - Böckmann, Anja
AU - Verel, René
AU - Meier, Beat H.
ID - 8470
IS - 5
JF - ChemPhysChem
KW - Physical and Theoretical Chemistry
KW - Atomic and Molecular Physics
KW - and Optics
SN - 1439-4235
TI - A proton-detected 4D solid-state NMR experiment for protein structure determination
VL - 12
ER -
TY - JOUR
AB - Despite the importance of protein fibrils in the context of conformational diseases, information on their structure is still sparse. Hydrogen/deuterium exchange measurements of backbone amide protons allow the identification hydrogen-bonding patterns and reveal pertinent information on the amyloid β-sheet architecture. However, they provide only little information on the identity of residues exposed to solvent or buried inside the fibril core. NMR spectroscopy is a potent method for identifying solvent-accessible residues in proteins via observation of polarization transfer between chemically exchanging side-chain protons and water protons. We show here that the combined use of highly deuterated samples and fast magic-angle spinning greatly attenuates unwanted spin diffusion and allows identification of polarization exchange with the solvent in a site-specific manner. We apply this measurement protocol to HET-s(218–289) prion fibrils under different conditions (including physiological pH, where protofibrils assemble together into thicker fibrils) and demonstrate that each protofibril of HET-s(218–289), is surrounded by water, thus excluding the existence of extended dry interfibril contacts. We also show that exchangeable side-chain protons inside the hydrophobic core of HET-s(218–289) do not exchange over time intervals of weeks to months. The experiments proposed in this study can provide insight into the detailed structural features of amyloid fibrils in general.
AU - Van Melckebeke, Hélène
AU - Schanda, Paul
AU - Gath, Julia
AU - Wasmer, Christian
AU - Verel, René
AU - Lange, Adam
AU - Meier, Beat H.
AU - Böckmann, Anja
ID - 8471
IS - 3
JF - Journal of Molecular Biology
SN - 0022-2836
TI - Probing water accessibility in HET-s(218–289) amyloid fibrils by solid-state NMR
VL - 405
ER -
TY - JOUR
AB - The classical principle of least action says that orbits of mechanical systems extremize action; an important subclass are those orbits that minimize action. In this paper we utilize this principle along with Aubry-Mather theory to construct (Birkhoff) regions of instability for a certain three-body problem, given by a Hamiltonian system of 2 degrees of freedom. We believe that these methods can be applied to construct instability regions for a variety of Hamiltonian systems with 2 degrees of freedom. The Hamiltonian model we consider describes dynamics of a Sun-Jupiter-comet system, and under some simplifying assumptions, we show the existence of instabilities for the orbit of the comet. In particular, we show that a comet which starts close to an orbit in the shape of an ellipse of eccentricity e=0.66 can increase in eccentricity up to e=0.96. In the sequels to this paper, we extend the result to beyond e=1 and show the existence of ejection orbits. Such orbits are initially well within the range of our solar system. This might give an indication of why most objects rotating around the Sun in our solar system have relatively low eccentricity.
AU - Galante, Joseph
AU - Kaloshin, Vadim
ID - 8505
IS - 2
JF - Duke Mathematical Journal
KW - General Mathematics
SN - 0012-7094
TI - Destruction of invariant curves in the restricted circular planar three-body problem by using comparison of action
VL - 159
ER -
TY - CHAP
AU - Fyodor Kondrashov
ID - 881
T2 - Evolution after Gene Duplication
TI - Gene Dosage and Duplication
ER -
TY - JOUR
AB - The emergence of differences in the arrangement of cells is the first step towards the establishment of many organs. Understanding this process is limited by the lack of systematic characterization of epithelial organisation. Here we apply network theory at the scale of individual cells to uncover patterns in cell-to-cell contacts that govern epithelial organisation. We provide an objective characterisation of epithelia using network representation, where cells are nodes and cell contacts are links. The features of individual cells, together with attributes of the cellular network, produce a defining signature that distinguishes epithelia from different organs, species, developmental stages and genetic conditions. The approach permits characterization, quantification and classification of normal and perturbed epithelia, and establishes a framework for understanding molecular mechanisms that underpin the architecture of complex tissues.
AU - Escudero, Luis M
AU - Costa, Luciano
AU - Anna Kicheva
AU - Briscoe, James
AU - Freeman, Matthew
AU - Babu, Madan M
ID - 1723
IS - 1
JF - Nature Communications
TI - Epithelial organisation revealed by a network of cellular contacts
VL - 2
ER -
TY - JOUR
AB - Morphogens, such as Decapentaplegic (Dpp) in the fly imaginal discs, form graded concentration profiles that control patterning and growth of developing organs. In the imaginal discs, proliferative growth is homogeneous in space, posing the conundrum of how morphogen concentration gradients could control position-independent growth. To understand the mechanism of proliferation control by the Dpp gradient, we quantified Dpp concentration and signaling levels during wing disc growth. Both Dpp concentration and signaling gradients scale with tissue size during development. On average, cells divide when Dpp signaling levels have increased by 50%. Our observations are consistent with a growth control mechanism based on temporal changes of cellular morphogen signaling levels. For a scaling gradient, this mechanism generates position-independent growth rates.
AU - Wartlick, Ortrud
AU - Mumcu, Peer
AU - Anna Kicheva
AU - Bittig, Thomas
AU - Seum, Carole
AU - Jülicher, Frank
AU - González-Gaitán, Marcos A
ID - 1724
IS - 6021
JF - Science
TI - Dynamics of Dpp signaling and proliferation control
VL - 331
ER -
TY - JOUR
AB - We report on a technique enabling electrical control of the contact silicidation process in silicon nanowire devices. Undoped silicon nanowires were contacted by pairs of nickel electrodes and each contact was selectively silicided by means of the Joule effect. By a realtime monitoring of the nanowire electrical resistance during the contact silicidation process we were able to fabricate nickel-silicide/silicon/nickel- silicide devices with controlled silicon channel length down to 8 nm.
AU - Mongillo, Massimo
AU - Spathis, Panayotis
AU - Katsaros, Georgios
AU - Gentile, Pascal
AU - Sanquer, Marc
AU - De Franceschi, Silvano
ID - 1754
IS - 9
JF - ACS Nano
TI - Joule-assisted silicidation for short-channel silicon nanowire devices
VL - 5
ER -
TY - JOUR
AB - Spin-selective tunneling of holes in SiGe nanocrystals contacted by normal-metal leads is reported. The spin selectivity arises from an interplay of the orbital effect of the magnetic field with the strong spin-orbit interaction present in the valence band of the semiconductor. We demonstrate both experimentally and theoretically that spin-selective tunneling in semiconductor nanostructures can be achieved without the use of ferromagnetic contacts. The reported effect, which relies on mixing the light and heavy holes, should be observable in a broad class of quantum-dot systems formed in semiconductors with a degenerate valence band.
AU - Georgios Katsaros
AU - Golovach, Vitaly N
AU - Spathis, Panayotis N
AU - Ares, Natalia
AU - Stoffel, Mathieu
AU - Fournel, Frank
AU - Schmidt, Oliver G
AU - Glazman, Leonid I
AU - De Franceschi, Silvano
ID - 1755
IS - 24
JF - Physical Review Letters
TI - Observation of spin-selective tunneling in sige nanocrystals
VL - 107
ER -
TY - JOUR
AB - At optical frequencies the radiation produced by a source, such as a laser, a black body or a single-photon emitter, is frequently characterized by analysing the temporal correlations of emitted photons using single-photon counters. At microwave frequencies, however, there are no efficient single-photon counters yet. Instead, well-developed linear amplifiers allow for efficient measurement of the amplitude of an electromagnetic field. Here, we demonstrate first- and second-order correlation function measurements of a pulsed microwave-frequency single-photon source integrated on the same chip with a 50/50 beam splitter followed by linear amplifiers and quadrature amplitude detectors. We clearly observe single-photon coherence in first-order and photon antibunching in second-order correlation function measurements of the propagating fields.
AU - Bozyigit, Deniz
AU - Lang, C
AU - Steffen, L. Kraig
AU - Johannes Fink
AU - Eichler, Christopher
AU - Baur, Matthias P
AU - Bianchetti, R
AU - Leek, Peter J
AU - Filipp, Stefan
AU - Da Silva, Marcus P
AU - Blais, Alexandre
AU - Wallraff, Andreas
ID - 1775
IS - 2
JF - Nature Physics
TI - Antibunching of microwave-frequency photons observed in correlation measurements using linear detectors
VL - 7
ER -
TY - CONF
AB - Superconducting circuits have been successfully established as systems to prepare and investigate microwave light fields at the quantum level. In contrast to optical experiments where light is detected using photon counters, microwaves are usually measured with well developed linear amplifiers. This makes measurements of correlation functions - one of the important tools in optics - harder to achieve because they traditionally rely on photon counters and beam splitters. Here, we demonstrate a system where we can prepare on demand single microwave photons in a cavity and detect them at the two outputs of the cavity using linear amplifiers. Together with efficient data processing, this allows us to measure different observables of the cavity photons, including the first-order correlation function. Using these techniques we demonstrate cooling of a thermal background field in the cavity.
AU - Bozyigit, Deniz
AU - Lang, C
AU - Steffen, L. Kraig
AU - Johannes Fink
AU - Eichler, Christopher
AU - Baur, Matthias P
AU - Bianchetti, R
AU - Leek, Peter J
AU - Filipp, Stefan
AU - Wallraff, Andreas
AU - Da Silva, Marcus P
AU - Blais, Alexandre
ID - 1776
IS - 1
TI - Correlation measurements of individual microwave photons emitted from a symmetric cavity
VL - 264
ER -
TY - JOUR
AB - A wide range of experiments studying microwave photons localized in superconducting cavities have made important contributions to our understanding of the quantum properties of radiation. Propagating microwave photons, however, have so far been studied much less intensely. Here we present measurements in which we reconstruct the quantum state of itinerant single photon Fock states and their superposition with the vacuum by analyzing moments of the measured amplitude distribution up to fourth order. Using linear amplifiers and quadrature amplitude detectors, we have developed efficient methods to separate the detected single photon signal from the noise added by the amplifier. From our measurement data we have also reconstructed the corresponding Wigner function.
AU - Eichler, Christopher
AU - Bozyigit, Deniz
AU - Lang, C
AU - Steffen, L. Kraig
AU - Johannes Fink
AU - Wallraff, Andreas
ID - 1777
IS - 22
JF - Physical Review Letters
TI - Experimental state tomography of itinerant single microwave photons
VL - 106
ER -
TY - JOUR
AB - Creating a train of single photons and monitoring its propagation and interaction is challenging in most physical systems, as photons generally interact very weakly with other systems. However, when confining microwave frequency photons in a transmission line resonator, effective photon-photon interactions can be mediated by qubits embedded in the resonator. Here, we observe the phenomenon of photon blockade through second-order correlation function measurements. The experiments clearly demonstrate antibunching in a continuously pumped source of single microwave photons measured by using microwave beam splitters, linear amplifiers, and quadrature amplitude detectors. We also investigate resonance fluorescence and Rayleigh scattering in Mollow-triplet-like spectra.
AU - Lang, C
AU - Bozyigit, Deniz
AU - Eichler, Christopher
AU - Steffen, L. Kraig
AU - Johannes Fink
AU - Abdumalikov, Abdufarrukh A
AU - Baur, Matthias P
AU - Filipp, Stefan
AU - Da Silva, Marcus P
AU - Blais, Alexandre
AU - Wallraff, Andreas
ID - 1778
IS - 24
JF - Physical Review Letters
TI - Observation of resonant photon blockade at microwave frequencies using correlation function measurements
VL - 106
ER -
TY - JOUR
AU - Eichler, Christopher
AU - Bozyigit, Deniz
AU - Lang, C
AU - Steffen, L. Kraig
AU - Johannes Fink
AU - Wallraff, Andreas
ID - 1779
IS - 24
JF - Physical Review Letters
TI - Erratum: Experimental state tomography of itinerant single microwave photons (Physical Review Letters (2011) 106 (220503))
VL - 106
ER -
TY - JOUR
AB - Continuous variable entanglement between two modes of a radiation field is usually studied at optical frequencies. Here we demonstrate experiments that show the entanglement between microwave photons of different energy in a broadband squeezed beam. We use a Josephson parametric amplifier to generate the two-mode correlated state and detect all four quadrature components simultaneously in a two-channel heterodyne setup using amplitude detectors. Analyzing two-dimensional phase space histograms for all possible pairs of quadratures allows us to determine the full covariance matrix, which is in good agreement with the one expected for a two-mode squeezed state.
AU - Eichler, Christopher
AU - Bozyigit, Deniz
AU - Lang, C
AU - Baur, Matthias P
AU - Steffen, L. Kraig
AU - Johannes Fink
AU - Filipp, Stefan
AU - Wallraff, Andreas
ID - 1780
IS - 11
JF - Physical Review Letters
TI - Observation of two-mode squeezing in the microwave frequency domain
VL - 107
ER -
TY - JOUR
AB - Microwave cavities with high quality factors enable coherent coupling of distant quantum systems. Virtual photons lead to a transverse interaction between qubits when they are nonresonant with the cavity but resonant with each other. We experimentally investigate the inverse scaling of the interqubit coupling with the detuning from a cavity mode and its proportionality to the qubit-cavity interaction strength. We demonstrate that the enhanced coupling at higher frequencies is mediated by multiple higher-harmonic cavity modes. Moreover, we observe dark states of the coupled qubit-qubit system and analyze their relation to the symmetry of the applied driving field at different frequencies.
AU - Filipp, Stefan
AU - Göppl, M
AU - Johannes Fink
AU - Baur, Matthias P
AU - Bianchetti, R
AU - Steffen, L. Kraig
AU - Wallraff, Andreas
ID - 1781
IS - 6
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Multimode mediated qubit-qubit coupling and dark-state symmetries in circuit quantum electrodynamics
VL - 83
ER -
TY - JOUR
AB - Many membrane channels and receptors exhibit adaptive, or desensitized, response to a strong sustained input stimulus, often supported by protein activity-dependent inactivation. Adaptive response is thought to be related to various cellular functions such as homeostasis and enlargement of dynamic range by background compensation. Here we study the quantitative relation between adaptive response and background compensation within a modeling framework. We show that any particular type of adaptive response is neither sufficient nor necessary for adaptive enlargement of dynamic range. In particular a precise adaptive response, where system activity is maintained at a constant level at steady state, does not ensure a large dynamic range neither in input signal nor in system output. A general mechanism for input dynamic range enlargement can come about from the activity-dependent modulation of protein responsiveness by multiple biochemical modification, regardless of the type of adaptive response it induces. Therefore hierarchical biochemical processes such as methylation and phosphorylation are natural candidates to induce this property in signaling systems.
AU - Tamar Friedlander
AU - Brenner, Naama
ID - 1815
IS - 2
JF - Mathematical Biosciences and Engineering
TI - Adaptive response and enlargement of dynamic range
VL - 8
ER -
TY - JOUR
AB - The Levene model is the simplest mathematical model to describe the evolution of gene frequencies in spatially subdivided populations. It provides insight into how locally varying selection promotes a population’s genetic diversity. Despite its simplicity, interesting problems have remained unsolved even in the diallelic case. In this paper we answer an open problem by establishing that for two alleles at one locus and J demes, up to 2J−1 polymorphic equilibria may coexist. We first present a proof for the case of stable monomorphisms and then show that the result also holds for protected alleles. These findings allow us to prove that any odd number (up to 2J−1) of equilibria is possible, before we extend the proof to even numbers. We conclude with some numerical results and show that for J>2, the proportion of parameter space affording this maximum is extremely small.
AU - Sebastian Novak
ID - 1863
IS - 3
JF - Theoretical Population Biology
TI - The number of equilibria in the diallelic Levene model with multiple demes
VL - 79
ER -
TY - JOUR
AB - Complex I is the first and largest enzyme of the respiratory chain, coupling electron transfer between NADH and ubiquinone to the translocation of four protons across the membrane. It has a central role in cellular energy production and has been implicated in many human neurodegenerative diseases. The L-shaped enzyme consists of hydrophilic and membrane domains. Previously, we determined the structure of the hydrophilic domain. Here we report the crystal structure of the Esherichia coli complex I membrane domain at 3.0 Ã. resolution. It includes six subunits, NuoL, NuoM, NuoN, NuoA, NuoJ and NuoK, with 55 transmembrane helices. The fold of the homologous antiporter-like subunits L, M and N is novel, with two inverted structural repeats of five transmembrane helices arranged, unusually, face-to-back. Each repeat includes a discontinuous transmembrane helix and forms half of a channel across the membrane. A network of conserved polar residues connects the two half-channels, completing the proton translocation pathway. Unexpectedly, lysines rather than carboxylate residues act as the main elements of the proton pump in these subunits. The fourth probable proton-translocation channel is at the interface of subunits N, K, J and A. The structure indicates that proton translocation in complex I, uniquely, involves coordinated conformational changes in six symmetrical structural elements.
AU - Efremov, Rouslan G
AU - Leonid Sazanov
ID - 1973
IS - 7361
JF - Nature
TI - Structure of the membrane domain of respiratory complex i
VL - 476
ER -
TY - JOUR
AB - Complex I is the first enzyme of the respiratory chain and plays a central role in cellular energy production. It has been implicated in many human neurodegenerative diseases, as well as in ageing. One of the biggest membrane protein complexes, it is an L-shaped assembly consisting of hydrophilic and membrane domains. Previously, we have determined structures of the hydrophilic domain in several redox states. Last year was marked by fascinating breakthroughs in the understanding of the complete structure. We described the architecture of the membrane domain and of the entire bacterial complex I. X-ray analysis of the larger mitochondrial enzyme has also been published. The core subunits of the bacterial and mitochondrial enzymes have remarkably similar structures. The proposed mechanism of coupling between electron transfer and proton translocation involves long-range conformational changes, coordinated in part by a long α-helix, akin to the coupling rod of a steam engine.
AU - Efremov, Rouslan G
AU - Leonid Sazanov
ID - 1974
IS - 4
JF - Current Opinion in Structural Biology
TI - Respiratory complex I: 'steam engine' of the cell?
VL - 21
ER -
TY - JOUR
AB - Modern α-proteobacteria are thought to be closely related to the ancient symbiont of eukaryotes, an ancestor of mitochondria. Respiratory complex I from α-proteobacteria and mitochondria is well conserved at the level of the 14 "core" subunits, consistent with that notion. Mitochondrial complex I contains the core subunits, present in all species, and up to 31 "supernumerary" subunits, generally thought to have originated only within eukaryotic lineages. However, the full protein composition of an α-proteobacterial complex I has not been established previously. Here, we report the first purification and characterization of complex I from the α-proteobacterium Paracoccus denitrificans. Single particle electron microscopy shows that the complex has a well defined L-shape. Unexpectedly, in addition to the 14 core subunits, the enzyme also contains homologues of three supernumerary mitochondrial subunits as follows: B17.2, AQDQ/18, and 13 kDa (bovine nomenclature). This finding suggests that evolution of complex I via addition of supernumerary or "accessory" subunits started before the original endosymbiotic event that led to the creation of the eukaryotic cell. It also provides further confirmation that α-proteobacteria are the closest extant relatives of mitochondria.
AU - Yip, Chui Y
AU - Harbour, Michael E
AU - Jayawardena, Kamburapola G
AU - Fearnley, Ian M
AU - Leonid Sazanov
ID - 1975
IS - 7
JF - Journal of Biological Chemistry
TI - Evolution of respiratory complex I "Supernumerary" subunits are present in the α-proteobacterial enzyme
VL - 286
ER -
TY - JOUR
AB -
In Escherichia coli, the pole-to-pole oscillation of the Min proteins directs septum formation to midcell, which is required for symmetric cell division. In vitro, protein waves emerge from the self-organization of MinD, a membrane-binding ATPase, and its activator MinE. For wave propagation, the proteins need to cycle through states of collective membrane binding and unbinding. Although MinD presumably undergoes cooperative membrane attachment, it is unclear how synchronous detachment is coordinated. We used confocal and single-molecule microscopy to elucidate the order of events during Min wave propagation. We propose that protein detachment at the rear of the wave, and the formation of the E-ring, are accomplished by two complementary processes: first, local accumulation of MinE due to rapid rebinding, leading to dynamic instability; and second, a structural change induced by membrane-interaction of MinE in an equimolar MinD-MinE (MinDE) complex, which supports the robustness of pattern formation.
AU - Martin Loose
AU - Fischer-Friedrich, Elisabeth
AU - Herold, Christoph
AU - Kruse, Karsten
AU - Schwille, Petra
ID - 1985
IS - 5
JF - Nature Structural and Molecular Biology
TI - Min protein patterns emerge from rapid rebinding and membrane interaction of MinE
VL - 18
ER -
TY - JOUR
AB - One of the most fundamental features of biological systems is probably their ability to self-organize in space and time on different scales. Despite many elaborate theoretical models of how molecular self-organization can come about, only a few experimental systems of biological origin have so far been rigorously described, due mostly to their inherent complexity. The most promising strategy of modern biophysics is thus to identify minimal biological systems showing self-organized emergent behavior. One of the best-understood examples of protein self-organization, which has recently been successfully reconstituted in vitro, is represented by the oscillations of the Min proteins in Escherichia coli. In this review, we summarize the current understanding of the mechanism of Min protein self-organization in vivo and in vitro. We discuss the potential of the Min oscillations to sense the geometry of the cell and suggest that spontaneous protein waves could be a general means of intracellular organization. We hypothesize that cooperative membrane binding and unbinding, e.g., as an energy-dependent switch, may act as an important regulatory mechanism for protein oscillations and pattern formation in the cell.
AU - Martin Loose
AU - Kruse, Karsten
AU - Schwille, Petra
ID - 1986
IS - 1
JF - Annual Review of Biophysics
TI - Protein self-organization: Lessons from the min system
VL - 40
ER -
TY - JOUR
AB - Many species have morphologically and genetically differentiated sex chromosomes, such as the XY pair of mammals. Y chromosomes are often highly degenerated and carry few functional genes, so that XY males have only one copy of most Xlinked genes (whereas females have two). As a result, chromosome-wide mechanisms of dosage compensation, such as the mammalian X-inactivation, often evolve to reestablish expression balance. A similar phenomenon is expected in femaleheterogametic species, where ZW females should suffer from imbalances due to W-chromosome degeneration. However, no global dosage compensation mechanisms have been detected in the two independent ZW systems that have been studied systematically (birds and silkworm), leading to the suggestion that lack of global dosage compensation may be a general feature of female-heterogametic species. However, analyses of other independently evolved ZW systems are required to test if this is the case. In this study, we use published genomic and expression data to test for the presence of global dosage compensation in Schistosoma mansoni, a trematode parasite that causes schistosomiasis in humans. We find that Z-linked expression is reduced relative to autosomal expression in females but not males, consistent with incomplete or localized dosage compensation. This gives further support to the theory that female-heterogametic species may not require global mechanisms of dosage compensation.
AU - Vicoso, Beatriz
AU - Bachtrog, Doris
ID - 2072
IS - 1
JF - Genome Biology and Evolution
TI - Lack of global dosage compensation in Schistosoma mansoni, a female-heterogametic parasite
VL - 3
ER -
TY - CHAP
AB - This chapter presents a method for real-time animation of highly detailed facial expressions based on sparse motion captures data and a limited set of static example poses. The method for real-time animation of highly detailed facial expressions decomposes geometry into large-scale motion and fine-scale details, such as expression wrinkles. Both large- and fine-scale deformation algorithms run entirely on the GPU, and our implementation based on CUDA achieves an overall performance of about 30 fps. The face conveys the most relevant visual characteristics of human identity and expression. Hence, realistic facial animations or interactions with virtual avatars are important for storytelling and gameplay. However, current approaches are either computationally expensive, require very specialized capture hardware, or are extremely labor intensive. At runtime, given an arbitrary facial expression, the algorithm computes the skin strain from the relative distance between marker points and derives fine-scale corrections for the largescale deformation. During gameplay only the sparse set of marker-point positions is transmitted to the GPU. The face animation is entirely computed on the GPU where the resulting mesh can directly be used as input for the rendering stages. This data can be easily obtained by traditional capture hardware. The proposed in-game algorithm is fast. It also is easy to implement and maps well onto programmable GPUs.
AU - Bernd Bickel
AU - Lang, Manuel
ID - 2098
T2 - GPU Computing Gems Emerald Edition
TI - From sparse mocap to highly detailed facial animation
ER -
TY - JOUR
AB - We present a new technique for passive and markerless facial performance capture based on anchor frames. Our method starts with high resolution per-frame geometry acquisition using state-of-theart stereo reconstruction, and proceeds to establish a single triangle mesh that is propagated through the entire performance. Leveraging the fact that facial performances often contain repetitive subsequences, we identify anchor frames as those which contain similar facial expressions to a manually chosen reference expression. Anchor frames are automatically computed over one or even multiple performances. We introduce a robust image-space tracking method that computes pixel matches directly from the reference frame to all anchor frames, and thereby to the remaining frames in the sequence via sequential matching. This allows us to propagate one reconstructed frame to an entire sequence in parallel, in contrast to previous sequential methods. Our anchored reconstruction approach also limits tracker drift and robustly handles occlusions and motion blur. The parallel tracking and mesh propagation offer low computation times. Our technique will even automatically match anchor frames across different sequences captured on different occasions, propagating a single mesh to all performances.
AU - Beeler, Thabo
AU - Hahn, Fabian
AU - Bradley, Derek J
AU - Bernd Bickel
AU - Beardsley, Paul A
AU - Gotsman, Craig
AU - Sumner, Robert W
AU - Groß, Markus S
ID - 2099
IS - 4
JF - ACM Transactions on Graphics
TI - High-quality passive facial performance capture using anchor frames
VL - 30
ER -
TY - CONF
AB - Acquiring panoramic images using stitching takes a lot of time and moving objects may cause ghosting. It is also difficult to obtain a full spherical panorama, because the downward picture cannot be captured while the camera is mounted on the tripod.
AU - Pfeil, Jonas
AU - Hildebrand, Kristian
AU - Gremzow, Carsten
AU - Bernd Bickel
AU - Alexa, Marc
ID - 2100
TI - Throwable panoramic ball camera
ER -
TY - CHAP
AB - Let P be the Ornstein-Uhlenbeck semigroup associated with the stochastic Cauchy problem dU(t)=AU(t)dt+dWH(t), where A is the generator of a C 0-semigroup S on a Banach space E, H is a Hilbert subspace of E, and W H is an H-cylindrical Brownian motion. Assuming that S restricts to a C 0-semigroup on H, we obtain L p -bounds for D H P(t). We show that if P is analytic, then the invariance assumption is fulfilled. As an application we determine the L p -domain of the generator of P explicitly in the case where S restricts to a C 0-semigroup on H which is similar to an analytic contraction semigroup. The results are applied to the 1D stochastic heat equation driven by additive space-time white noise.
AU - Jan Maas
AU - Van Neerven, Jan
ID - 2116
T2 - Parabolic Problems
TI - Gradient estimates and domain identification for analytic Ornstein-Uhlenbeck operators
VL - 80
ER -
TY - JOUR
AB - We study, in L1(R̃n; γ) with respect to the gaussian measure, non- tangential maximal functions and conical square functions associ- ated with the Ornstein-Uhlenbeck operator by developing a set of techniques which allow us, to some extent, to compensate for the non-doubling character of the gaussian measure. The main result asserts that conical square functions can be controlled in L1-norm by non-tangential maximal functions. Along the way we prove a change of aperture result for the latter. This complements recent results on gaussian Hardy spaces due to Mauceri and Meda.
AU - Jan Maas
AU - van Neerven, Jan M
AU - Portal, Pierre
ID - 2122
IS - 2
JF - Publicacions Matemàtiques
TI - Conical square functions and non-tangential maximal functions with respect to the Gaussian measure
VL - 55
ER -
TY - JOUR
AB - We prove a Trotter product formula for gradient flows in metric spaces. This result is applied to establish convergence in the L 2-Wasserstein metric of the splitting method for some Fokker-Planck equations and porous medium type equations perturbed by a potential.
AU - Clément, Philippe H
AU - Jan Maas
ID - 2123
IS - 2
JF - Journal of Evolution Equations
TI - A Trotter product formula for gradient flows in metric spaces
VL - 11
ER -
TY - JOUR
AB - Let K be an irreducible and reversible Markov kernel on a finite set X. We construct a metric W on the set of probability measures on X and show that with respect to this metric, the law of the continuous time Markov chain evolves as the gradient flow of the entropy. This result is a discrete counterpart of the Wasserstein gradient flow interpretation of the heat flow in Rn by Jordan, Kinderlehrer and Otto (1998). The metric W is similar to, but different from, the L2-Wasserstein metric, and is defined via a discrete variant of the Benamou–Brenier formula.
AU - Jan Maas
ID - 2126
IS - 8
JF - Journal of Functional Analysis
TI - Gradient flows of the entropy for finite Markov chains
VL - 261
ER -
TY - GEN
AB - A (diatomic) shape resonance is a metastable state of a pair of colliding atoms quasi-bound by the centrifugal barrier imposed by the angular momentum involved in the collision. The temporary trapping of the atoms' scattering wavefunction corresponds to an enhanced atom pair density at low interatomic separations. This leads to larger overlap of the wavefunctions involved in a molecule formation process such as photoassociation, rendering the process more efficient. However, for an ensemble of atoms, the atom pair density will only be enhanced if the energy of the resonance comes close to the temperature of the atomic ensemble. Herein we explore the possibility of controlling the energy of a shape resonance by shifting it toward the temperature of atoms confined in a trap. The shifts are imparted by the interaction of non-resonant light with the anisotropic polarizability of the atom pair, which affects both the centrifugal barrier and the pair's rotational and vibrational levels. We find that at laser intensities of up to 5×109 W/cm2 the pair density is increased by one order of magnitude for 87Rb atoms at 100μK and by two orders of magnitude for 88Sr atoms at 20μK.
AU - Ağanoğlu, Ruzin
AU - Mikhail Lemeshko
AU - Friedrich, Břetislav
AU - González-Férez, Rosario
AU - Koch, Christiane P
ID - 2138
T2 - Unknown
TI - Controlling a diatomic shape resonance with non-resonant light
ER -
TY - JOUR
AB - We show that dressing polar molecules with a far-off-resonant optical field leads to new types of intermolecular potentials, which undergo a crossover from the inverse power to oscillating behavior depending on the intermolecular distance, and whose parameters can be tuned by varying the laser intensity and wavelength. We present analytic expressions for the potential energy surfaces, thereby providing direct access to the parameters of an optical field required to design intermolecular interactions experimentally.
AU - Mikhail Lemeshko
ID - 2198
IS - 5
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Shaping interactions between polar molecules with far-off-resonant light
VL - 83
ER -
TY - JOUR
AB - By invoking supersymmetry, we found a condition under which the Stark-effect problem for a polar and polarizable molecule subject to nonresonant electric fields becomes exactly solvable for the family of stretched states. The analytic expressions for the wave function and eigenenergy and other expectation values allow one to readily reverse-engineer the problem of finding the values of the interaction parameters required for creating quantum states with preordained characteristics. The method also allows the construction of families of isospectral potentials, realizable with combined fields.
AU - Mikhail Lemeshko
AU - Mustafa, Mustafa K
AU - Kais, Sabre
AU - Friedrich, Břetislav
ID - 2199
IS - 4
JF - Physical Review A - Atomic, Molecular, and Optical Physics
TI - Supersymmetric factorization yields exact solutions to the molecular Stark-effect problem for "stretched" states
VL - 83
ER -
TY - JOUR
AB - We made use of supersymmetric (SUSY) quantum mechanics to find the condition under which the Stark effect problem for a polar and polarizable closed-shell diatomic molecule subjected to collinear electrostatic and nonresonant radiative fields becomes exactly solvable. The condition Δω = ω2/4(m+1)2 connects values of the dimensionless parameters ω and Δω that characterize the strengths of the permanent and induced dipole interactions of the molecule with the respective fields. The exact solutions are obtained for the \J̃ = m, m; ω, Δω) family of 'stretched' states. The field-free and strong-field limits of the combined-fields problem were found to exhibit supersymmetry and shape invariance, which is indeed the reason why they are analytically solvable. By making use of the analytic form of the \J̃ = m,m; ω, Δω) wavefunctions, we obtained simple formulae for the expectation values of the space-fixed electric dipole moment, the alignment cosine and the angular momentum squared, and derived a 'sum rule' that combines the above expectation values into a formula for the eigenenergy. The analytic expressions for the characteristics of the strongly oriented and aligned states provide direct access to the values of the interaction parameters required for creating such states in the laboratory.
AU - Mikhail Lemeshko
AU - Mustafa, Mustafa K
AU - Kais, Sabre
AU - Friedrich, Břetislav
ID - 2200
JF - New Journal of Physics
TI - Supersymmetry identifies molecular Stark states whose eigenproperties can be obtained analytically
VL - 13
ER -
TY - JOUR
AB - Li-ion batteries have transformed portable electronics and will play a key role in the electrification of transport. However, the highest energy storage possible for Li-ion batteries is insufficient for the long-term needs of society, for example, extended-range electric vehicles. To go beyond the horizon of Li-ion batteries is a formidable challenge; there are few options. Here we consider two: Li–air (O2) and Li–S. The energy that can be stored in Li–air (based on aqueous or non-aqueous electrolytes) and Li–S cells is compared with Li-ion; the operation of the cells is discussed, as are the significant hurdles that will have to be overcome if such batteries are to succeed. Fundamental scientific advances in understanding the reactions occurring in the cells as well as new materials are key to overcoming these obstacles. The potential benefits of Li–air and Li–S justify the continued research effort that will be needed.
AU - Bruce, Peter G.
AU - Freunberger, Stefan Alexander
AU - Hardwick, Laurence J.
AU - Tarascon, Jean-Marie
ID - 7313
IS - 1
JF - Nature Materials
SN - 1476-1122
TI - Li–O2 and Li–S batteries with high energy storage
VL - 11
ER -
TY - JOUR
AB - The electrolyte is one of the greatest challenges facing the development of the non‐aqueous Li–O2 battery. Although ether‐based electrolytes do from Li2O2 on the first discharge, it is shown by various techniques that they also decompose and that decomposition increases while Li2O2 decreases on cycling (see picture). Thus, these electrolytes are not suitable.
AU - Freunberger, Stefan Alexander
AU - Chen, Yuhui
AU - Drewett, Nicholas E.
AU - Hardwick, Laurence J.
AU - Bardé, Fanny
AU - Bruce, Peter G.
ID - 7314
IS - 37
JF - Angewandte Chemie International Edition
SN - 1433-7851
TI - The Lithium-Oxygen battery with ether-based electrolytes
VL - 50
ER -
TY - JOUR
AB - Spectroscopic data (see picture) provide direct evidence that in non‐aqueous Li+ electrolyte, O2 is reduced to O2−, which then forms LiO2 on the electrode surface which disproportionates to Li2O2. On charging, Li2O2 decomposes directly, in a one‐step reaction to evolve O2 and does not pass through LiO2 as an intermediate.
AU - Peng, Zhangquan
AU - Freunberger, Stefan Alexander
AU - Hardwick, Laurence J.
AU - Chen, Yuhui
AU - Giordani, Vincent
AU - Bardé, Fanny
AU - Novák, Petr
AU - Graham, Duncan
AU - Tarascon, Jean-Marie
AU - Bruce, Peter G.
ID - 7315
IS - 28
JF - Angewandte Chemie International Edition
SN - 1433-7851
TI - Oxygen reactions in a non-aqueous Li+ electrolyte
VL - 50
ER -
TY - JOUR
AB - The nonaqueous rechargeable lithium–O2 battery containing an alkyl carbonate electrolyte discharges by formation of C3H6(OCO2Li)2, Li2CO3, HCO2Li, CH3CO2Li, CO2, and H2O at the cathode, due to electrolyte decomposition. Charging involves oxidation of C3H6(OCO2Li)2, Li2CO3, HCO2Li, CH3CO2Li accompanied by CO2 and H2O evolution. Mechanisms are proposed for the reactions on discharge and charge. The different pathways for discharge and charge are consistent with the widely observed voltage gap in Li–O2 cells. Oxidation of C3H6(OCO2Li)2 involves terminal carbonate groups leaving behind the OC3H6O moiety that reacts to form a thick gel on the Li anode. Li2CO3, HCO2Li, CH3CO2Li, and C3H6(OCO2Li)2 accumulate in the cathode on cycling correlating with capacity fading and cell failure. The latter is compounded by continuous consumption of the electrolyte on each discharge.
AU - Freunberger, Stefan Alexander
AU - Chen, Yuhui
AU - Peng, Zhangquan
AU - Griffin, John M.
AU - Hardwick, Laurence J.
AU - Bardé, Fanny
AU - Novák, Petr
AU - Bruce, Peter G.
ID - 7316
IS - 20
JF - Journal of the American Chemical Society
SN - 0002-7863
TI - Reactions in the rechargeable Lithium–O2 battery with alkyl carbonate electrolytes
VL - 133
ER -
TY - JOUR
AB - Lithium-metal oxides with a high formal Li2O content, such as Li5FeO4 (5Li2O•Fe2O3) and a Li2MnO3•LiFeO2 composite ({Li2O•MnO2}•{Li2O•Fe2O3}) have been explored as electrocatalysts for primary and rechargeable Li-O2 cells. Activation occurs predominantly by Li2O removal, either electrochemically or chemically by acid-treatment. Superior electrochemical behavior is obtained if activation occurs by acid-treatment; Li2MnO3•LiFeO2 catalysts provide 2516 mAh/g (carbon) corresponding to 931 mAh/g (electrocatalyst + carbon) during the initial discharge. The reaction is reasonably reversible during the early cycles. The approach has implications for designing electrocatalysts that participate through electrochemical Li2O extraction/reformation reactions, offering exceptionally high capacities.
AU - Trahey, L.
AU - Johnson, C. S.
AU - Vaughey, J. T.
AU - Kang, S.-H.
AU - Hardwick, L. J.
AU - Freunberger, Stefan Alexander
AU - Bruce, P. G.
AU - Thackeray, M. M.
ID - 7317
IS - 5
JF - Electrochemical and Solid-State Letters
SN - 1099-0062
TI - Activated Lithium-Metal-Oxides as catalytic electrodes for Li–O2 cells
VL - 14
ER -
TY - CONF
AB - Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficiently transform an algorithm that relies on synchronization into an algorithm that tolerates asynchronous executions. We introduce a transformation technique from synchronous algorithms to indulgent algorithms [1], which induces only a constant overhead in terms of time complexity in well-behaved executions. Our technique is based on a new abstraction we call an asynchrony detector, which the participating processes implement collectively. The resulting transformation works for a large class of colorless tasks, including consensus and set agreement. Interestingly, we also show that our technique is relevant for colored tasks, by applying it to the renaming problem, to obtain the first indulgent renaming algorithm.
AU - Alistarh, Dan-Adrian
AU - Gilbert, Seth
AU - Guerraoui, Rachid
AU - Travers, Corentin
ID - 757
TI - Generating fast indulgent algorithms
VL - 6522 LNCS
ER -
TY - CONF
AB - We study the complexity of renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct names from a given namespace. We prove an individual lower bound of Ω(k) process steps for deterministic renaming into any namespace of size sub-exponential in k, where k is the number of participants. This bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic fetch-and-increment registers, queues and stacks. The proof of the bound is interesting in its own right, for it relies on the first reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement our individual bound with a global lower bound of Ω(k log (k/c)) on the total step complexity of renaming into a namespace of size ck, for any c ≥ 1. This applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter and fetch-and-increment implementations, all tight within logarithmic factors.
AU - Alistarh, Dan-Adrian
AU - Aspnes, James
AU - Gilbert, Seth
AU - Guerraoui, Rachid
ID - 759
TI - The complexity of renaming
ER -
TY - CONF
AB - A randomized implementation is given of a test-and-set register with O(log log n) individual step complexity and O(n) total step complexity against an oblivious adversary. The implementation is linearizable and multi-shot, and shows an exponential complexity improvement over previous solutions designed to work against a strong adversary.
AU - Alistarh, Dan-Adrian
AU - Aspnes, James
ID - 760
TI - Sub-logarithmic test-and-set against a weak adversary
VL - 6950 LNCS
ER -
TY - CONF
AB - We give two new randomized algorithms for strong renaming, both of which work against an adaptive adversary in asynchronous shared memory. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of n processes with step complexity O(log3 n). The second transforms any sorting network into a strong adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a strong adaptive renaming algorithm with step complexity O(log k), where k is the contention in the current execution. We show this to be optimal based on a classic lower bound of Jayanti. We also show that any such strong renaming protocol can be used to build a monotone-consistent counter with logarithmic step complexity (at the cost of adding a max register) or a linearizable fetch-and-increment register (at the cost of increasing the step complexity by a logarithmic factor).
AU - Alistarh, Dan-Adrian
AU - Aspnes, James
AU - Censor Hillel, Keren
AU - Gilbert, Seth
AU - Zadimoghaddam, Morteza
ID - 761
TI - Optimal-time adaptive strong renaming, with applications to counting
ER -
TY - JOUR
AB - During assembly of the Drosophila olfactory circuit, projection neuron (PN) dendrites prepattern the developing antennal lobe before the arrival of axons from their presynaptic partners, the adult olfactory receptor neurons (ORNs). We previously found that levels of transmembrane Semaphorin-1a, which acts as a receptor, instruct PN dendrite targeting along the dorsolateral-ventromedial axis. Here we show that two secreted semaphorins, Sema-2a and Sema-2b, provide spatial cues for PN dendrite targeting. Sema-2a and Sema-2b proteins are distributed in gradients opposing the Sema-1a protein gradient, and Sema-1a binds to Sema-2a-expressing cells. In Sema-2a and Sema-2b double mutants, PN dendrites that normally target dorsolaterally in the antennal lobe mistarget ventromedially, phenocopying cell-autonomous Sema-1a removal from these PNs. Cell ablation, cell-specific knockdown, and rescue experiments indicate that secreted semaphorins from degenerating larval ORN axons direct dendrite targeting. Thus, a degenerating brain structure instructs the wiring of a developing circuit through the repulsive action of secreted semaphorins.
AU - Sweeney, Lora Beatrice Jaeger
AU - Chou, Ya-Hui
AU - Wu, Zhuhao
AU - Joo, William
AU - Komiyama, Takaki
AU - Potter, Christopher J.
AU - Kolodkin, Alex L.
AU - Garcia, K. Christopher
AU - Luo, Liqun
ID - 7701
IS - 5
JF - Neuron
SN - 0896-6273
TI - Secreted semaphorins from degenerating larval ORN axons direct adult projection neuron dendrite targeting
VL - 72
ER -
TY - JOUR
AB - Longitudinal axon fascicles within the Drosophila embryonic CNS provide connections between body segments and are required for coordinated neural signaling along the anterior-posterior axis. We show here that establishment of select CNS longitudinal tracts and formation of precise mechanosensory afferent innervation to the same CNS region are coordinately regulated by the secreted semaphorins Sema-2a and Sema-2b. Both Sema-2a and Sema-2b utilize the same neuronal receptor, plexin B (PlexB), but serve distinct guidance functions. Localized Sema-2b attraction promotes the initial assembly of a subset of CNS longitudinal projections and subsequent targeting of chordotonal sensory afferent axons to these same longitudinal connectives, whereas broader Sema-2a repulsion serves to prevent aberrant innervation. In the absence of Sema-2b or PlexB, chordotonal afferent connectivity within the CNS is severely disrupted, resulting in specific larval behavioral deficits. These results reveal that distinct semaphorin-mediated guidance functions converge at PlexB and are critical for functional neural circuit assembly.
AU - Wu, Zhuhao
AU - Sweeney, Lora Beatrice Jaeger
AU - Ayoob, Joseph C.
AU - Chak, Kayam
AU - Andreone, Benjamin J.
AU - Ohyama, Tomoko
AU - Kerr, Rex
AU - Luo, Liqun
AU - Zlatic, Marta
AU - Kolodkin, Alex L.
ID - 7702
IS - 2
JF - Neuron
SN - 0896-6273
TI - A combinatorial semaphorin code instructs the initial steps of sensory circuit assembly in the Drosophila CNS
VL - 70
ER -
TY - JOUR
AU - Robinson, Matthew Richard
ID - 7750
IS - 6
JF - Behavioral Ecology
SN - 1465-7279
TI - Understanding intrasexual competition and sexual selection requires an evolutionary ecology framework
VL - 22
ER -
TY - JOUR
AB - Spontaneous release of glutamate is important for maintaining synaptic strength and controlling spike timing in the brain. Mechanisms regulating spontaneous exocytosis remain poorly understood. Extracellular calcium concentration ([Ca2+]o) regulates Ca2+ entry through voltage-activated calcium channels (VACCs) and consequently is a pivotal determinant of action potential-evoked vesicle fusion. Extracellular Ca 2+ also enhances spontaneous release, but via unknown mechanisms. Here we report that external Ca2+ triggers spontaneous glutamate release more weakly than evoked release in mouse neocortical neurons. Blockade of VACCs has no effect on the spontaneous release rate or its dependence on [Ca2+]o. Intracellular [Ca2+] slowly increases in a minority of neurons following increases in [Ca2+]o. Furthermore, the enhancement of spontaneous release by extracellular calcium is insensitive to chelation of intracellular calcium by BAPTA. Activation of the calcium-sensing receptor (CaSR), a G-protein-coupled receptor present in nerve terminals, by several specific agonists increased spontaneous glutamate release. The frequency of spontaneous synaptic transmission was decreased in CaSR mutant neurons. The concentration-effect relationship for extracellular calcium regulation of spontaneous release was well described by a combination of CaSR-dependent and CaSR-independent mechanisms. Overall these results indicate that extracellular Ca2+ does not trigger spontaneous glutamate release by simply increasing calcium influx but stimulates CaSR and thereby promotes resting spontaneous glutamate release.
AU - Vyleta, Nicholas
AU - Smith, Stephen
ID - 469
IS - 12
JF - European Journal of Neuroscience
TI - Spontaneous glutamate release is independent of calcium influx and tonically activated by the calcium-sensing receptor
VL - 31
ER -
TY - JOUR
AB - BioSig is an open source software library for biomedical signal processing. The aim of the BioSig project is to foster research in biomedical signal processing by providing free and open source software tools for many different application areas. Some of the areas where BioSig can be employed are neuroinformatics, brain-computer interfaces, neurophysiology, psychology, cardiovascular systems, and sleep research. Moreover, the analysis of biosignals such as the electroencephalogram (EEG), electrocorticogram (ECoG), electrocardiogram (ECG), electrooculogram (EOG), electromyogram (EMG), or respiration signals is a very relevant element of the BioSig project. Specifically, BioSig provides solutions for data acquisition, artifact processing, quality control, feature extraction, classification, modeling, and data visualization, to name a few. In this paper, we highlight several methods to help students and researchers to work more efficiently with biomedical signals.
AU - Schlögl, Alois
AU - Vidaurre, Carmen
AU - Sander, Tilmann
ID - 490
JF - Computational Intelligence and Neuroscience
TI - BioSig: The free and open source software library for biomedical signal processing
VL - 2011
ER -
TY - JOUR
AB - In their search for antigens, lymphocytes continuously shuttle among blood vessels, lymph vessels, and lymphatic tissues. Chemokines mediate entry of lymphocytes into lymphatic tissues, and sphingosine 1-phosphate (S1P) promotes localization of lymphocytes to the vasculature. Both signals are sensed through G protein-coupled receptors (GPCRs). Most GPCRs undergo ligand-dependent homologous receptor desensitization, a process that decreases their signaling output after previous exposure to high ligand concentration. Such desensitization can explain why lymphocytes do not take an intermediate position between two signals but rather oscillate between them. The desensitization of S1P receptor 1 (S1PR1) is mediated by GPCR kinase 2 (GRK2). Deletion of GRK2 in lymphocytes compromises desensitization by high vascular S1P concentrations, thereby reducing responsiveness to the chemokine signal and trapping the cells in the vascular compartment. The desensitization kinetics of S1PR1 allows lymphocytes to dynamically shuttle between vasculature and lymphatic tissue, although the positional information in both compartments is static.
AU - Eichner, Alexander
AU - Sixt, Michael K
ID - 491
IS - 198
JF - Science Signaling
TI - Setting the clock for recirculating lymphocytes
VL - 4
ER -
TY - JOUR
AB - Cancer stem cells or cancer initiating cells are believed to contribute to cancer recurrence after therapy. MicroRNAs (miRNAs) are short RNA molecules with fundamental roles in gene regulation. The role of miRNAs in cancer stem cells is only poorly understood. Here, we report miRNA expression profiles of glioblastoma stem cell-containing CD133 + cell populations. We find that miR-9, miR-9 * (referred to as miR-9/9 *), miR-17 and miR-106b are highly abundant in CD133 + cells. Furthermore, inhibition of miR-9/9 * or miR-17 leads to reduced neurosphere formation and stimulates cell differentiation. Calmodulin-binding transcription activator 1 (CAMTA1) is a putative transcription factor, which induces the expression of the anti-proliferative cardiac hormone natriuretic peptide A (NPPA). We identify CAMTA1 as an miR-9/9 * and miR-17 target. CAMTA1 expression leads to reduced neurosphere formation and tumour growth in nude mice, suggesting that CAMTA1 can function as tumour suppressor. Consistently, CAMTA1 and NPPA expression correlate with patient survival. Our findings could provide a basis for novel strategies of glioblastoma therapy.
AU - Schraivogel, Daniel
AU - Weinmann, Lasse
AU - Beier, Dagmar
AU - Tabatabai, Ghazaleh
AU - Eichner, Alexander
AU - Zhu, Jia
AU - Anton, Martina
AU - Sixt, Michael K
AU - Weller, Michael
AU - Beier, Christoph
AU - Meister, Gunter
ID - 518
IS - 20
JF - EMBO Journal
TI - CAMTA1 is a novel tumour suppressor regulated by miR-9/9 * in glioblastoma stem cells
VL - 30
ER -
TY - JOUR
AB - Software transactional memories (STM) are described in the literature with assumptions of sequentially consistent program execution and atomicity of high level operations like read, write, and abort. However, in a realistic setting, processors use relaxed memory models to optimize hardware performance. Moreover, the atomicity of operations depends on the underlying hardware. This paper presents the first approach to verify STMs under relaxed memory models with atomicity of 32 bit loads and stores, and read-modify-write operations. We describe RML, a simple language for expressing concurrent programs. We develop a semantics of RML parametrized by a relaxed memory model. We then present our tool, FOIL, which takes as input the RML description of an STM algorithm restricted to two threads and two variables, and the description of a memory model, and automatically determines the locations of fences, which if inserted, ensure the correctness of the restricted STM algorithm under the given memory model. We use FOIL to verify DSTM, TL2, and McRT STM under the memory models of sequential consistency, total store order, partial store order, and relaxed memory order for two threads and two variables. Finally, we extend the verification results for DSTM and TL2 to an arbitrary number of threads and variables by manually proving that the structural properties of STMs are satisfied at the hardware level of atomicity under the considered relaxed memory models.
AU - Guerraoui, Rachid
AU - Henzinger, Thomas A
AU - Singh, Vasu
ID - 531
IS - 3
JF - Formal Methods in System Design
TI - Verification of STM on relaxed memory models
VL - 39
ER -
TY - GEN
AB - Computing the winning set for Büchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is ̃O(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the ̃O(n·m) boundary by presenting a new technique that reduces the running time to O(n2). This bound also leads to O(n2) time algorithms for computing the set of almost-sure winning vertices for Büchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of O(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n3)), and (3) in Markov decision processes (improving for m > n4/3 an earlier bound of O(min(m1.5, m·n2/3)). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n2), which is an improvement over earlier bounds for m > n4/3. Finally, we show how to maintain the winning set for Büchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.
AU - Chatterjee, Krishnendu
AU - Henzinger, Monika
ID - 5379
SN - 2664-1690
TI - An O(n2) time algorithm for alternating Büchi games
ER -
TY - GEN
AB - We consider 2-player games played on a finite state space for an infinite number of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine the successor state. We study concurrent games with ω-regular winning conditions specified as parity objectives. We consider the qualitative analysis problems: the computation of the almost-sure and limit-sure winning set of states, where player 1 can ensure to win with probability 1 and with probability arbitrarily close to 1, respectively. In general the almost-sure and limit-sure winning strategies require both infinite-memory as well as infinite-precision (to describe probabilities). We study the bounded-rationality problem for qualitative analysis of concurrent parity games, where the strategy set for player 1 is restricted to bounded-resource strategies. In terms of precision, strategies can be deterministic, uniform, finite-precision or infinite-precision; and in terms of memory, strategies can be memoryless, finite-memory or infinite-memory. We present a precise and complete characterization of the qualitative winning sets for all combinations of classes of strategies. In particular, we show that uniform memoryless strategies are as powerful as finite-precision infinite-memory strategies, and infinite-precision memoryless strategies are as powerful as infinite-precision finite-memory strategies. We show that the winning sets can be computed in O(n2d+3) time, where n is the size of the game structure and 2d is the number of priorities (or colors), and our algorithms are symbolic. The membership problem of whether a state belongs to a winning set can be decided in NP ∩ coNP. While this complexity is the same as for the simpler class of turn-based parity games, where in each state only one of the two players has a choice of moves, our algorithms,that are obtained by characterization of the winning sets as μ-calculus formulas, are considerably more involved than those for turn-based games.
AU - Chatterjee, Krishnendu
ID - 5380
SN - 2664-1690
TI - Bounded rationality in concurrent parity games
ER -
TY - GEN
AB - In two-player finite-state stochastic games of partial obser- vation on graphs, in every state of the graph, the players simultaneously choose an action, and their joint actions determine a probability distri- bution over the successor states. The game is played for infinitely many rounds and thus the players construct an infinite path in the graph. We consider reachability objectives where the first player tries to ensure a target state to be visited almost-surely (i.e., with probability 1) or pos- itively (i.e., with positive probability), no matter the strategy of the second player.
We classify such games according to the information and to 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, (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.
Our main results for pure strategies are as follows: (1) For one-sided games with player 2 perfect observation we show that (in contrast to full randomized strategies) belief-based (subset-construction based) strate- gies are not sufficient, and present an exponential upper bound on mem- ory both for almost-sure 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 and present symbolic algo- rithms that avoid the explicit exponential construction. (2) For one-sided games with player 1 perfect observation we show that non-elementary memory is both necessary and sufficient for both almost-sure and posi- tive 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 re- sult exhibit serious flaws in previous results in 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 - 5381
SN - 2664-1690
TI - Partial-observation stochastic games: How to win when belief fails
ER -
TY - GEN
AB - We consider two-player stochastic games played on a finite state space for an infinite num- ber of rounds. The games are concurrent: in each round, the two players (player 1 and player 2) choose their moves independently and simultaneously; the current state and the two moves determine a probability distribution over the successor states. We also consider the important special case of turn-based stochastic games where players make moves in turns, rather than concurrently. We study concurrent games with ω-regular winning conditions specified as parity objectives. The value for player 1 for a parity objective is the maximal probability with which the player can guarantee the satisfaction of the objective against all strategies of the opponent. We study the problem of continuity and robustness of the value function in concurrent and turn-based stochastic parity games with respect to imprecision in the transition probabilities. We present quantitative bounds on the difference of the value function (in terms of the imprecision of the transition probabilities) and show the value continuity for structurally equivalent concurrent games (two games are structurally equivalent if the support of the transition func- tion is same and the probabilities differ). We also show robustness of optimal strategies for structurally equivalent turn-based stochastic parity games. Finally we show that the value continuity property breaks without the structurally equivalent assumption (even for Markov chains) and show that our quantitative bound is asymptotically optimal. Hence our results are tight (the assumption is both necessary and sufficient) and optimal (our quantitative bound is asymptotically optimal).
AU - Chatterjee, Krishnendu
ID - 5382
SN - 2664-1690
TI - Robustness of structurally equivalent concurrent parity games
ER -
TY - GEN
AB - We present a new decidable logic called TREX for expressing constraints about imperative tree data structures. In particular, TREX supports a transitive closure operator that can express reachability constraints, which often appear in data structure invariants. We show that our logic is closed under weakest precondition computation, which enables its use for automated software verification. We further show that satisfiability of formulas in TREX is decidable in NP. The low complexity makes it an attractive alternative to more expensive logics such as monadic second-order logic (MSOL) over trees, which have been traditionally used for reasoning about tree data structures.
AU - Wies, Thomas
AU - Muñiz, Marco
AU - Kuncak, Viktor
ID - 5383
SN - 2664-1690
TI - On an efficient decision procedure for imperative tree data structures
ER -