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 - 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 - 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 - 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
AU - Maas, Jan
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 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 - 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 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 - 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 - 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 - 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 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 - 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 - 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 - 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 - 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
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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - JOUR
AB - The phytohormone auxin is vital to plant growth and development. A unique property of auxin among all other plant hormones is its cell-to-cell polar transport that requires activity of polarly localized PIN-FORMED (PIN) auxin efflux transporters. Despite the substantial molecular insight into the cellular PIN polarization, the mechanistic understanding for developmentally and environmentally regulated PIN polarization is scarce. The long-standing belief that auxin modulates its own transport by means of a positive feedback mechanism has inspired both experimentalists and theoreticians for more than two decades. Recently, theoretical models for auxin-dependent patterning in plants include the feedback between auxin transport and the PIN protein localization. These computer models aid to assess the complexity of plant development by testing and predicting plausible scenarios for various developmental processes that occur in planta. Although the majority of these models rely on purely heuristic principles, the most recent mechanistic models tentatively integrate biologically testable components into known cellular processes that underlie the PIN polarity regulation. The existing and emerging computational approaches to describe PIN polarization are presented and discussed in the light of recent experimental data on the PIN polar targeting.
AU - Wabnik, Krzysztof T
AU - Govaerts, Willy
AU - Friml, Jirí
AU - Kleine Vehn, Jürgen
ID - 3092
IS - 8
JF - Molecular BioSystems
TI - Feedback models for polarized auxin transport: An emerging trend
VL - 7
ER -
TY - JOUR
AB - The phytohormone auxin is an important determinant of plant development. Directional auxin flow within tissues depends on polar localization of PIN auxin transporters. To explore regulation of PIN-mediated auxin transport, we screened for suppressors of PIN1 overexpression (supo) and identified an inositol polyphosphate 1-phosphatase mutant (supo1), with elevated inositol trisphosphate (InsP 3) and cytosolic Ca 2+ levels. Pharmacological and genetic increases in InsP 3 or Ca 2+ levels also suppressed the PIN1 gain-of-function phenotypes and caused defects in basal PIN localization, auxin transport and auxin-mediated development. In contrast, the reductions in InsP 3 levels and Ca 2+ signaling antagonized the effects of the supo1 mutation and disrupted preferentially apical PIN localization. InsP 3 and Ca 2+ are evolutionarily conserved second messengers involved in various cellular functions, particularly stress responses. Our findings implicate them as modifiers of cell polarity and polar auxin transport, and highlight a potential integration point through which Ca 2+ signaling-related stimuli could influence auxin-mediated development.
AU - Zhang, Jing
AU - Vanneste, Steffen
AU - Brewer, Philip B
AU - Michniewicz, Marta
AU - Peter Grones
AU - Kleine-Vehn, Jürgen
AU - Löfke, Christian
AU - Teichmann, Thomas
AU - Bielach, Agnieszka
AU - Cannoot, Bernard
AU - Hoyerová, Klára
AU - Xu Chen
AU - Xue, Hong-Wei
AU - Eva Benková
AU - Zažímalová, Eva
AU - Jirí Friml
ID - 3089
IS - 6
JF - Developmental Cell
TI - Inositol trisphosphate-induced ca^2+ signaling modulates auxin transport and pin polarity
VL - 20
ER -
TY - JOUR
AB - The polarized transport of the phytohormone auxin [1], which is crucial for the regulation of different stages of plant development [2, 3], depends on the asymmetric plasma membrane distribution of the PIN-FORMED (PIN) auxin efflux carriers [4, 5]. The PIN polar localization results from clathrin-mediated endocytosis (CME) from the plasma membrane and subsequent polar recycling [6]. The Arabidopsis genome encodes two groups of dynamin-related proteins (DRPs) that show homology to mammalian dynamin - a protein required for fission of endocytic vesicles during CME [7, 8]. Here we show by coimmunoprecipitation (coIP), bimolecular fluorescence complementation (BiFC), and Förster resonance energy transfer (FRET) that members of the DRP1 group closely associate with PIN proteins at the cell plate. Localization and phenotypic analysis of novel drp1 mutants revealed a requirement for DRP1 function in correct PIN distribution and in auxin-mediated development. We propose that rapid and specific internalization of PIN proteins mediated by the DRP1 proteins and the associated CME machinery from the cell plate membranes during cytokinesis is an important mechanism for proper polar PIN positioning in interphase cells.
AU - Mravec, Jozef
AU - Petrášek, Jan
AU - Li, Na
AU - Boeren, Sjef
AU - Karlova, Rumyana
AU - Kitakura, Saeko
AU - Pařezová, Markéta
AU - Naramoto, Satoshi
AU - Nodzyński, Thomasz
AU - Dhonukshe, Pankaj
AU - Bednarek, Sebastian Y
AU - Zažímalová, Eva
AU - De Vries, Sacco
AU - Jirí Friml
ID - 3090
IS - 12
JF - Current Biology
TI - Cell plate restricted association of DRP1A and PIN proteins is required for cell polarity establishment in arabidopsis
VL - 21
ER -
TY - JOUR
AB - Background: Whereas the majority of animals develop toward a predetermined body plan, plants show iterative growth and continually produce new organs and structures from actively dividing meristems. This raises an intriguing question: How are these newly developed organs patterned? In Arabidopsis embryos, radial symmetry is broken by the bisymmetric specification of the cotyledons in the apical domain. Subsequently, this bisymmetry is propagated to the root promeristem. Results: Here we present a mutually inhibitory feedback loop between auxin and cytokinin that sets distinct boundaries of hormonal output. Cytokinins promote the bisymmetric distribution of the PIN-FORMED (PIN) auxin efflux proteins, which channel auxin toward a central domain. High auxin promotes transcription of the cytokinin signaling inhibitor AHP6, which closes the interaction loop. This bisymmetric auxin response domain specifies the differentiation of protoxylem in a bisymmetric pattern. In embryonic roots, cytokinin is required to translate a bisymmetric auxin response in the cotyledons to a bisymmetric vascular pattern in the root promeristem. Conclusions: Our results present an interactive feedback loop between hormonal signaling and transport by which small biases in hormonal input are propagated into distinct signaling domains to specify the vascular pattern in the root meristem. It is an intriguing possibility that such a mechanism could transform radial patterns and allow continuous vascular connections between other newly emerging organs.
AU - Bishopp, Anthony
AU - Help, Hanna
AU - El-Showk, Sedeer
AU - Weijers, Dolf
AU - Scheres, Ben
AU - Jirí Friml
AU - Eva Benková
AU - Mähönen, Ari Pekka
AU - Helariutta, Ykä
ID - 3088
IS - 11
JF - Current Biology
TI - A mutually inhibitory interaction between auxin and cytokinin specifies vascular pattern in roots
VL - 21
ER -
TY - JOUR
AB -
Plants take up iron from the soil using the IRON-REGULATED TRANSPORTER 1 (IRT1) high-affinity iron transporter at the root surface. Sophisticated regulatory mechanisms allow plants to tightly control the levels of IRT1, ensuring optimal absorption of essential but toxic iron. Here, we demonstrate that overexpression of Arabidopsis thaliana IRT1 leads to constitutive IRT1 protein accumulation, metal overload, and oxidative stress. IRT1 is unexpectedly found in trans-Golgi network/early endosomes of root hair cells, and its levels and localization are unaffected by iron nutrition. Using pharmacological approaches, we show that IRT1 cycles to the plasma membrane to perform iron and metal uptake at the cell surface and is sent to the vacuole for proper turnover. We also prove that IRT1 is monoubiquitinated on several cytosol-exposed residues in vivo and that mutation of two putative monoubiquitination target residues in IRT1 triggers stabilization at the plasma membrane and leads to extreme lethality. Together, these data suggest a model in which monoubiquitin-dependent internalization/sorting and turnover keep the plasma membrane pool of IRT1 low to ensure proper iron uptake and to prevent metal toxicity. More generally, our work demonstrates the existence of monoubiquitin-dependent trafficking to lytic vacuoles in plants and points to proteasome-independent turnover of plasma membrane proteins.
AU - Barberon, Marie
AU - Zelazny, Enric
AU - Robert, Stéphanie
AU - Conéjéro, Geneviève
AU - Curie, Cathy
AU - Jirí Friml
AU - Vert, Grégory
ID - 3093
IS - 32
JF - PNAS
TI - Monoubiquitin dependent endocytosis of the Iron Regulated Transporter 1 IRT1 transporter controls iron uptake in plants
VL - 108
ER -
TY - JOUR
AB - Summary Gravitropism aligns plant growth with gravity. It involves gravity perception and the asymmetric distribution of the phytohormone auxin. Here we provide insights into the mechanism for hypocotyl gravitropic growth. We show that the Arabidopsis thaliana PIN3 auxin transporter is required for the asymmetric auxin distribution for the gravitropic response. Gravistimulation polarizes PIN3 to the bottom side of hypocotyl endodermal cells, which correlates with an increased auxin response at the lower hypocotyl side. Both PIN3 polarization and hypocotyl bending require the activity of the trafficking regulator GNOM and the protein kinase PINOID. Our data suggest that gravity-induced PIN3 polarization diverts the auxin flow to mediate the asymmetric distribution of auxin for gravitropic shoot bending.
AU - Rakusová, Hana
AU - Gallego-Bartolomé, Javier
AU - Vanstraelen, Marleen
AU - Robert, Hélène S
AU - Alabadí, David
AU - Blázquez, Miguel A
AU - Eva Benková
AU - Jirí Friml
ID - 3094
IS - 5
JF - Plant Journal
TI - Polarization of PIN3 dependent auxin transport for hypocotyl gravitropic response in Arabidopsis thaliana
VL - 67
ER -
TY - JOUR
AU - Sauer, Michael
AU - Friml, Jirí
ID - 3091
JF - Molecular Systems Biology
TI - Fleeting hormone cues get stabilized for plant organogenesis
VL - 7
ER -
TY - JOUR
AB - Multicellular organisms depend on cell production, cell fate specification, and correct patterning to shape their adult body. In plants, auxin plays a prominent role in the timely coordination of these different cellular processes. A well-studied example is lateral root initiation, in which auxin triggers founder cell specification and cell cycle activation of xylem pole–positioned pericycle cells. Here, we report that the E2Fa transcription factor of Arabidopsis thaliana is an essential component that regulates the asymmetric cell division marking lateral root initiation. Moreover, we demonstrate that E2Fa expression is regulated by the LATERAL ORGAN BOUNDARY DOMAIN18/LATERAL ORGAN BOUNDARY DOMAIN33 (LBD18/LBD33) dimer that is, in turn, regulated by the auxin signaling pathway. LBD18/LBD33 mediates lateral root organogenesis through E2Fa transcriptional activation, whereas E2Fa expression under control of the LBD18 promoter eliminates the need for LBD18. Besides lateral root initiation, vascular patterning is disrupted in E2Fa knockout plants, similarly as it is affected in auxin signaling and lbd mutants, indicating that the transcriptional induction of E2Fa through LBDs represents a general mechanism for auxin-dependent cell cycle activation. Our data illustrate how a conserved mechanism driving cell cycle entry has been adapted evolutionarily to connect auxin signaling with control of processes determining plant architecture.
AU - Berckmans, Barbara
AU - Vassileva, Valya
AU - Schmid, Stephan P
AU - Maes, Sara
AU - Parizot, Boris
AU - Naramoto, Satoshi
AU - Magyar, Zoltan
AU - Lessa Alvim Kamei, Claire
AU - Koncz, Csaba
AU - Bögre, Laszlo
AU - Persiau, Geert
AU - De Jaeger, Geert
AU - Jirí Friml
AU - Simon, Rüdiger
AU - Beeckman, Tom
AU - de Veyldera, Lieven
ID - 3102
IS - 10
JF - Plant Cell
TI - Auxin Dependent cell cycle reactivation through transcriptional regulation of arabidopsis E2Fa by lateral organ boundary proteins
VL - 23
ER -
TY - JOUR
AB - Endocytosis in plants has an essential role not only for basic cellular functions but also for growth and development, hormonal signaling and communication with the environment including nutrient delivery, toxin avoidance, and pathogen defense. The major endocytic mechanism in plants depends on the coat protein clathrin. It starts by clathrin-coated vesicle formation at the plasma membrane, where specific cargoes are recognized and packaged for internalization. Recently, genetic, biochemical and advanced microscopy studies provided initial insights into mechanisms and roles of clathrin-mediated endocytosis in plants. Here we summarize the present state of knowledge and compare mechanisms of clathrin-mediated endocytosis in plants with animal and yeast paradigms as well as review plant-specific regulations and roles of this process.
AU - Chen, Xu
AU - Irani, Niloufer
AU - Friml, Jirí
ID - 3103
IS - 6
JF - Current Opinion in Plant Biology
TI - Clathrin-mediated endocytosis: The gateway into plant cells
VL - 14
ER -
TY - JOUR
AB - Cancer cell of origin is difficult to identify by analyzing cells within terminal stage tumors, whose identity could be concealed by the acquired plasticity. Thus, an ideal approach to identify the cell of origin is to analyze proliferative abnormalities in distinct lineages prior to malignancy. Here, we use mosaic analysis with double markers (MADM) in mice to model gliomagenesis by initiating concurrent p53/Nf1 mutations sporadically in neural stem cells (NSCs). Surprisingly, MADM-based lineage tracing revealed significant aberrant growth prior to malignancy only in oligodendrocyte precursor cells (OPCs), but not in any other NSC-derived lineages or NSCs themselves. Upon tumor formation, phenotypic and transcriptome analyses of tumor cells revealed salient OPC features. Finally, introducing the same p53/Nf1 mutations directly into OPCs consistently led to gliomagenesis. Our findings suggest OPCs as the cell of origin in this model, even when initial mutations occur in NSCs, and highlight the importance of analyzing premalignant stages to identify the cancer cell of origin.
AU - Liu, Chong
AU - Sage, Jonathan C
AU - Miller, Michael R
AU - Verhaak, Roel G
AU - Simon Hippenmeyer
AU - Vogel, Hannes
AU - Foreman, Oded
AU - Bronson, Roderick T
AU - Nishiyama, Akiko
AU - Luo, Liqun
AU - Zong, Hui
ID - 3147
IS - 2
JF - Cell
TI - Mosaic analysis with double markers reveals tumor cell of origin in glioma
VL - 146
ER -
TY - CONF
AB - We introduce a new class of functions that can be minimized in polynomial time in the value oracle model. These are functions f satisfying f(x) + f(y) ≥ f(x ∏ y) + f(x ∐ y) where the domain of each variable x i corresponds to nodes of a rooted binary tree, and operations ∏,∐ are defined with respect to this tree. Special cases include previously studied L-convex and bisubmodular functions, which can be obtained with particular choices of trees. We present a polynomial-time algorithm for minimizing functions in the new class. It combines Murota's steepest descent algorithm for L-convex functions with bisubmodular minimization algorithms.
AU - Vladimir Kolmogorov
ID - 3204
TI - Submodularity on a tree: Unifying Submodularity on a tree: Unifying L-convex and bisubmodular functions convex and bisubmodular functions
VL - 6907
ER -
TY - CONF
AB - In this paper we address the problem of finding the most probable state of discrete Markov random field (MRF) with associative pairwise terms. Although of practical importance, this problem is known to be NP-hard in general. We propose a new type of MRF decomposition, submod-ular decomposition (SMD). Unlike existing decomposition approaches SMD decomposes the initial problem into sub-problems corresponding to a specific class label while preserving the graph structure of each subproblem. Such decomposition enables us to take into account several types of global constraints in an efficient manner. We study theoretical properties of the proposed approach and demonstrate its applicability on a number of problems.
AU - Osokin, Anton
AU - Vetrov, Dmitry
AU - Vladimir Kolmogorov
ID - 3206
TI - Submodular decomposition framework for inference in associative Markov networks with global constraints
ER -
TY - CONF
AB - This paper proposes a novel Linear Programming (LP) based algorithm, called Dynamic Tree-Block Coordinate Ascent (DT-BCA), for performing maximum a posteriori (MAP) inference in probabilistic graphical models. Unlike traditional message passing algorithms, which operate uniformly on the whole factor graph, our method dynamically chooses regions of the factor graph on which to focus message-passing efforts. We propose two criteria for selecting regions, including an efficiently computable upper-bound on the increase in the objective possible by passing messages in any particular region. This bound is derived from the theory of primal-dual methods from combinatorial optimization, and the forest that maximizes the bounds can be chosen efficiently using a maximum-spanning-tree-like algorithm. Experimental results show that our dynamic schedules significantly speed up state-of-the-art LP-based message-passing algorithms on a wide variety of real-world problems.
AU - Tarlow, Daniel
AU - Batra, Druv
AU - Kohli, Pushmeet
AU - Vladimir Kolmogorov
ID - 3205
TI - Dynamic tree block coordinate ascent
ER -
TY - CONF
AB - Cosegmentation is typically defined as the task of jointly segmenting something similar in a given set of images. Existing methods are too generic and so far have not demonstrated competitive results for any specific task. In this paper we overcome this limitation by adding two new aspects to cosegmentation: (1) the "something" has to be an object, and (2) the "similarity" measure is learned. In this way, we are able to achieve excellent results on the recently introduced iCoseg dataset, which contains small sets of images of either the same object instance or similar objects of the same class. The challenge of this dataset lies in the extreme changes in viewpoint, lighting, and object deformations within each set. We are able to considerably outperform several competitors. To achieve this performance, we borrow recent ideas from object recognition: the use of powerful features extracted from a pool of candidate object-like segmentations. We believe that our work will be beneficial to several application areas, such as image retrieval.
AU - Vicente, Sara
AU - Rother, Carsten
AU - Vladimir Kolmogorov
ID - 3207
TI - Object cosegmentation
ER -
TY - CONF
AB - The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two limitations: - Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are ε-close to uniform, one must set v ≤ m - 2log(1/ε), meaning that the entropy loss L = def m - v ≥ 2 log(1/ε). For many applications, such entropy loss is too large. - Large Seed Length: the seed length n of (almost) universal hash function required by the LHL must be at least n ≥ min (u - v, v + 2log(1/ε)) - O(1), where u is the length of the source, and must grow with the number of extracted bits. Quite surprisingly, we show that both limitations of the LHL - large entropy loss and large seed - can be overcome (or, at least, mitigated) in various important scenarios. First, we show that entropy loss could be reduced to L = log(1/ε) for the setting of deriving secret keys for a wide range of cryptographic applications. Specifically, the security of these schemes with an LHL-derived key gracefully degrades from ε to at most ε + √ε2-L. (Notice that, unlike standard LHL, this bound is meaningful even when one extracts more bits than the min-entropy we have!) Based on these results we build a general computational extractor that enjoys low entropy loss and can be used to instantiate a generic key derivation function for any cryptographic application. Second, we study the soundness of the natural expand-then-extract approach, where one uses a pseudorandom generator (PRG) to expand a short "input seed" S into a longer "output seed" S′, and then use the resulting S′ as the seed required by the LHL (or, more generally, by any randomness extractor). We show that, in general, the expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true. Despite that, we show that it is sound either: (1) when extracting a "small" (logarithmic in the security of the PRG) number of bits; or (2) in minicrypt. Implication (2) suggests that the expand-then-extract approach is likely secure when used with "practical" PRGs, despite lacking a reductionist proof of security! © 2011 International Association for Cryptologic Research.
AU - Barak, Boaz
AU - Dodis, Yevgeniy
AU - Krawczyk, Hugo
AU - Pereira, Olivier
AU - Krzysztof Pietrzak
AU - Standaert, François-Xavier
AU - Yu, Yu
ID - 3240
TI - Leftover hash lemma revisited
VL - 6841
ER -
TY - CONF
AB - Verification of programs with procedures, multi-threaded programs, and higher-order functional programs can be effectively au- tomated using abstraction and refinement schemes that rely on spurious counterexamples for abstraction discovery. The analysis of counterexam- ples can be automated by a series of interpolation queries, or, alterna- tively, as a constraint solving query expressed by a set of recursion free Horn clauses. (A set of interpolation queries can be formulated as a single constraint over Horn clauses with linear dependency structure between the unknown relations.) In this paper we present an algorithm for solving recursion free Horn clauses over a combined theory of linear real/rational arithmetic and uninterpreted functions. Our algorithm performs resolu- tion to deal with the clausal structure and relies on partial solutions to deal with (non-local) instances of functionality axioms.
AU - Gupta, Ashutosh
AU - Popeea, Corneliu
AU - Rybalchenko, Andrey
ED - Yang, Hongseok
ID - 3264
TI - Solving recursion-free Horn clauses over LI+UIF
VL - 7078
ER -
TY - CONF
AB - We present a joint image segmentation and labeling model (JSL) which, given a bag of figure-ground segment hypotheses extracted at multiple image locations and scales, constructs a joint probability distribution over both the compatible image interpretations (tilings or image segmentations) composed from those segments, and over their labeling into categories. The process of drawing samples from the joint distribution can be interpreted as first sampling tilings, modeled as maximal cliques, from a graph connecting spatially non-overlapping segments in the bag [1], followed by sampling labels for those segments, conditioned on the choice of a particular tiling. We learn the segmentation and labeling parameters jointly, based on Maximum Likelihood with a novel Incremental Saddle Point estimation procedure. The partition function over tilings and labelings is increasingly more accurately approximated by including incorrect configurations that a not-yet-competent model rates probable during learning. We show that the proposed methodologymatches the current state of the art in the Stanford dataset [2], as well as in VOC2010, where 41.7% accuracy on the test set is achieved.
AU - Ion, Adrian
AU - Carreira, Joao
AU - Sminchisescu, Cristian
ID - 3266
T2 - NIPS Proceedings
TI - Probabilistic joint image segmentation and labeling
VL - 24
ER -
TY - JOUR
AB - The unintentional scattering of light between neighboring surfaces in complex projection environments increases the brightness and decreases the contrast, disrupting the appearance of the desired imagery. To achieve satisfactory projection results, the inverse problem of global illumination must be solved to cancel this secondary scattering. In this paper, we propose a global illumination cancellation method that minimizes the perceptual difference between the desired imagery and the actual total illumination in the resulting physical environment. Using Gauss-Newton and active set methods, we design a fast solver for the bound constrained nonlinear least squares problem raised by the perceptual error metrics. Our solver is further accelerated with a CUDA implementation and multi-resolution method to achieve 1–2 fps for problems with approximately 3000 variables. We demonstrate the global illumination cancellation algorithm with our multi-projector system. Results show that our method preserves the color fidelity of the desired imagery significantly better than previous methods.
AU - Sheng, Yu
AU - Cutler, Barbara
AU - Chen, Chao
AU - Nasman, Joshua
ID - 3269
IS - 4
JF - Computer Graphics Forum
TI - Perceptual global illumination cancellation in complex projection environments
VL - 30
ER -
TY - JOUR
AB - We address the problem of localizing homology classes, namely, finding the cycle representing a given class with the most concise geometric measure. We study the problem with different measures: volume, diameter and radius. For volume, that is, the 1-norm of a cycle, two main results are presented. First, we prove that the problem is NP-hard to approximate within any constant factor. Second, we prove that for homology of dimension two or higher, the problem is NP-hard to approximate even when the Betti number is O(1). The latter result leads to the inapproximability of the problem of computing the nonbounding cycle with the smallest volume and computing cycles representing a homology basis with the minimal total volume. As for the other two measures defined by pairwise geodesic distance, diameter and radius, we show that the localization problem is NP-hard for diameter but is polynomial for radius. Our work is restricted to homology over the ℤ2 field.
AU - Chen, Chao
AU - Freedman, Daniel
ID - 3267
IS - 3
JF - Discrete & Computational Geometry
TI - Hardness results for homology localization
VL - 45
ER -
TY - CHAP
AB - Algebraic topology is generally considered one of the purest subfield of mathematics. However, over the last decade two interesting new lines of research have emerged, one focusing on algorithms for algebraic topology, and the other on applications of algebraic topology in engineering and science. Amongst the new areas in which the techniques have been applied are computer vision and image processing. In this paper, we survey the results of these endeavours. Because algebraic topology is an area of mathematics with which most computer vision practitioners have no experience, we review the machinery behind the theories of homology and persistent homology; our review emphasizes intuitive explanations. In terms of applications to computer vision, we focus on four illustrative problems: shape signatures, natural image statistics, image denoising, and segmentation. Our hope is that this review will stimulate interest on the part of computer vision researchers to both use and extend the tools of this new field.
AU - Freedman, Daniel
AU - Chen, Chao
ID - 3268
T2 - Computer Vision
TI - Algebraic topology for computer vision
ER -
TY - JOUR
AB - The zonula adherens (ZA) of epithelial cells is a site of cell-cell adhesion where cellular forces are exerted and resisted. Increasing evidence indicates that E-cadherin adhesion molecules at the ZA serve to sense force applied on the junctions and coordinate cytoskeletal responses to those forces. Efforts to understand the role that cadherins play in mechanotransduction have been limited by the lack of assays to measure the impact of forces on the ZA. In this study we used 4D imaging of GFP-tagged E-cadherin to analyse the movement of the ZA. Junctions in confluent epithelial monolayers displayed prominent movements oriented orthogonal (perpendicular) to the ZA itself. Two components were identified in these movements: a relatively slow unidirectional (translational) component that could be readily fitted by least-squares regression analysis, upon which were superimposed more rapid oscillatory movements. Myosin IIB was a dominant factor responsible for driving the unilateral translational movements. In contrast, frequency spectrum analysis revealed that depletion of Myosin IIA increased the power of the oscillatory movements. This implies that Myosin IIA may serve to dampen oscillatory movements of the ZA. This extends our recent analysis of Myosin II at the ZA to demonstrate that Myosin IIA and Myosin IIB make distinct contributions to junctional movement at the ZA.
AU - Smutny, Michael
AU - Wu, Selwin
AU - Gomez, Guillermo
AU - Mangold, Sabine
AU - Yap, Alpha
AU - Hamilton, Nicholas
ID - 3288
IS - 7
JF - PLoS One
TI - Multicomponent analysis of junctional movements regulated by Myosin II isoforms at the epithelial zonula adherens
VL - 6
ER -
TY - JOUR
AB - Cationic antimicrobial peptides (CAMPs) selectively target bacterial membranes by electrostatic interactions with negatively charged lipids. It turned out that for inhibition of microbial growth a high CAMP membrane concentration is required, which can be realized by the incorporation of hydrophobic groups within the peptide. Increasing hydrophobicity, however, reduces the CAMP selectivity for bacterial over eukaryotic host membranes, thereby causing the risk of detrimental side-effects. In this study we addressed how cationic amphipathic peptides—in particular a CAMP with Lysine–Leucine–Lysine repeats (termed KLK)—affect the localization and dynamics of molecules in eukaryotic membranes. We found KLK to selectively inhibit the endocytosis of a subgroup of membrane proteins and lipids by electrostatically interacting with negatively charged sialic acid moieties. Ultrastructural characterization revealed the formation of membrane invaginations representing fission or fusion intermediates, in which the sialylated proteins and lipids were immobilized. Experiments on structurally different cationic amphipathic peptides (KLK, 6-MO-LF11-322 and NK14-2) indicated a cooperation of electrostatic and hydrophobic forces that selectively arrest sialylated membrane constituents.
AU - Weghuber, Julian
AU - Aichinger, Michael C.
AU - Brameshuber, Mario
AU - Stefan Wieser
AU - Verena Ruprecht
AU - Plochberger, Birgit
AU - Madl, Josef
AU - Horner, Andreas
AU - Reipert, Siegfried
AU - Lohner, Karl
AU - Henics, Tamas
AU - Schuetz, Gerhard J
ID - 3286
IS - 10
JF - Biochimica et Biophysica Acta (BBA) - Biomembranes
TI - Cationic amphipathic peptides accumulate sialylated proteins and lipids in the plasma membrane of eukaryotic host cells
VL - 1808
ER -
TY - JOUR
AB - Diffusing membrane constituents are constantly exposed to a variety of forces that influence their stochastic path. Single molecule experiments allow for resolving trajectories at extremely high spatial and temporal accuracy, thereby offering insights into en route interactions of the tracer. In this review we discuss approaches to derive information about the underlying processes, based on single molecule tracking experiments. In particular, we focus on a new versatile way to analyze single molecule diffusion in the absence of a full analytical treatment. The method is based on comprehensive comparison of an experimental data set against the hypothetical outcome of multiple experiments performed on the computer. Since Monte Carlo simulations can be easily and rapidly performed even on state-of-the-art PCs, our method provides a simple way for testing various - even complicated - diffusion models. We describe the new method in detail, and show the applicability on two specific examples: firstly, kinetic rate constants can be derived for the transient interaction of mobile membrane proteins; secondly, residence time and corral size can be extracted for confined diffusion.
AU - Ruprecht, Verena
AU - Axmann, Markus
AU - Wieser, Stefan
AU - Schuetz, Gerhard
ID - 3287
IS - 8
JF - Current Protein & Peptide Science
TI - What can we learn from single molecule trajectories?
VL - 12
ER -
TY - JOUR
AB - Resolving the dynamical interplay of proteins and lipids in the live-cell plasma membrane represents a central goal in current cell biology. Superresolution concepts have introduced a means of capturing spatial heterogeneity at a nanoscopic length scale. Similar concepts for detecting dynamical transitions (superresolution chronoscopy) are still lacking. Here, we show that recently introduced spot-variation fluorescence correlation spectroscopy allows for sensing transient confinement times of membrane constituents at dramatically improved resolution. Using standard diffraction-limited optics, spot-variation fluorescence correlation spectroscopy captures signatures of single retardation events far below the transit time of the tracer through the focal spot. We provide an analytical description of special cases of transient binding of a tracer to pointlike traps, or association of a tracer with nanodomains. The influence of trap mobility and the underlying binding kinetics are quantified. Experimental approaches are suggested that allow for gaining quantitative mechanistic insights into the interaction processes of membrane constituents.
AU - Ruprecht, Verena
AU - Wieser, Stefan
AU - Marguet, Didier
AU - Schuetz, Gerhard
ID - 3285
IS - 11
JF - Biophysical Journal
TI - Spot variation fluorescence correlation spectroscopy allows for superresolution chronoscopy of confinement times in membranes
VL - 100
ER -
TY - CONF
AB - Cloud computing aims to give users virtually unlimited pay-per-use computing resources without the burden of managing the underlying infrastructure. We present a new job execution environment Flextic that exploits scal- able static scheduling techniques to provide the user with a flexible pricing model, such as a tradeoff between dif- ferent degrees of execution speed and execution price, and at the same time, reduce scheduling overhead for the cloud provider. We have evaluated a prototype of Flextic on Amazon EC2 and compared it against Hadoop. For various data parallel jobs from machine learning, im- age processing, and gene sequencing that we considered, Flextic has low scheduling overhead and reduces job du- ration by up to 15% compared to Hadoop, a dynamic cloud scheduler.
AU - Henzinger, Thomas A
AU - Singh, Anmol
AU - Singh, Vasu
AU - Wies, Thomas
AU - Zufferey, Damien
ID - 3302
TI - Static scheduling in clouds
ER -
TY - CONF
AB - The chemical master equation is a differential equation describing the time evolution of the probability distribution over the possible “states” of a biochemical system. The solution of this equation is of interest within the systems biology field ever since the importance of the molec- ular noise has been acknowledged. Unfortunately, most of the systems do not have analytical solutions, and numerical solutions suffer from the course of dimensionality and therefore need to be approximated. Here, we introduce the concept of tail approximation, which retrieves an approximation of the probabilities in the tail of a distribution from the total probability of the tail and its conditional expectation. This approximation method can then be used to numerically compute the solution of the chemical master equation on a subset of the state space, thus fighting the explosion of the state space, for which this problem is renowned.
AU - Henzinger, Thomas A
AU - Mateescu, Maria
ID - 3301
TI - Tail approximation for the chemical master equation
ER -
TY - CONF
AB - We introduce propagation models, a formalism designed to support general and efficient data structures for the transient analysis of biochemical reaction networks. We give two use cases for propagation abstract data types: the uniformization method and numerical integration. We also sketch an implementation of a propagation abstract data type, which uses abstraction to approximate states.
AU - Henzinger, Thomas A
AU - Mateescu, Maria
ID - 3299
TI - Propagation models for computing biochemical reaction networks
ER -
TY - JOUR
AB - Powerful statistical models that can be learned efficiently from large amounts of data are currently revolutionizing computer vision. These models possess a rich internal structure reflecting task-specific relations and constraints. This monograph introduces the reader to the most popular classes of structured models in computer vision. Our focus is discrete undirected graphical models which we cover in detail together with a description of algorithms for both probabilistic inference and maximum a posteriori inference. We discuss separately recently successful techniques for prediction in general structured models. In the second part of this monograph we describe methods for parameter learning where we distinguish the classic maximum likelihood based methods from the more recent prediction-based parameter learning methods. We highlight developments to enhance current models and discuss kernelized models and latent variable models. To make the monograph more practical and to provide links to further study we provide examples of successful application of many methods in the computer vision literature.
AU - Nowozin, Sebastian
AU - Lampert, Christoph
ID - 3320
IS - 3-4
JF - Foundations and Trends in Computer Graphics and Vision
TI - Structured learning and prediction in computer vision
VL - 6
ER -
TY - CONF
AB - In addition to being correct, a system should be robust, that is, it should behave reasonably even after receiving unexpected inputs. In this paper, we summarize two formal notions of robustness that we have introduced previously for reactive systems. One of the notions is based on assigning costs for failures on a user-provided notion of incorrect transitions in a specification. Here, we define a system to be robust if a finite number of incorrect inputs does not lead to an infinite number of incorrect outputs. We also give a more refined notion of robustness that aims to minimize the ratio of output failures to input failures. The second notion is aimed at liveness. In contrast to the previous notion, it has no concept of recovery from an error. Instead, it compares the ratio of the number of liveness constraints that the system violates to the number of liveness constraints that the environment violates.
AU - Bloem, Roderick
AU - Chatterjee, Krishnendu
AU - Greimel, Karin
AU - Henzinger, Thomas A
AU - Jobstmann, Barbara
ID - 3316
T2 - 6th IEEE International Symposium on Industrial and Embedded Systems
TI - Specification-centered robustness
ER -
TY - CONF
AB - We address the problem of metric learning for multi-view data, namely the construction of embedding projections from data in different representations into a shared feature space, such that the Euclidean distance in this space provides a meaningful within-view as well as between-view similarity. Our motivation stems from the problem of cross-media retrieval tasks, where the availability of a joint Euclidean distance function is a pre-requisite to allow fast, in particular hashing-based, nearest neighbor queries. We formulate an objective function that expresses the intuitive concept that matching samples are mapped closely together in the output space, whereas non-matching samples are pushed apart, no matter in which view they are available. The resulting optimization problem is not convex, but it can be decomposed explicitly into a convex and a concave part, thereby allowing efficient optimization using the convex-concave procedure. Experiments on an image retrieval task show that nearest-neighbor based cross-view retrieval is indeed possible, and the proposed technique improves the retrieval accuracy over baseline techniques.
AU - Quadrianto, Novi
AU - Lampert, Christoph
ID - 3319
TI - Learning multi-view neighborhood preserving projections
ER -
TY - JOUR
AB - Parvalbumin is thought to act in a manner similar to EGTA, but how a slow Ca2+ buffer affects nanodomain-coupling regimes at GABAergic synapses is unclear. Direct measurements of parvalbumin concentration and paired recordings in rodent hippocampus and cerebellum revealed that parvalbumin affects synaptic dynamics only when expressed at high levels. Modeling suggests that, in high concentrations, parvalbumin may exert BAPTA-like effects, modulating nanodomain coupling via competition with local saturation of endogenous fixed buffers.
AU - Eggermann, Emmanuel
AU - Jonas, Peter M
ID - 3318
JF - Nature Neuroscience
TI - How the “slow” Ca(2+) buffer parvalbumin affects transmitter release in nanodomain coupling regimes at GABAergic synapses
VL - 15
ER -
TY - CHAP
AB - We study the topology of the Megaparsec Cosmic Web in terms of the scale-dependent Betti numbers, which formalize the topological information content of the cosmic mass distribution. While the Betti numbers do not fully quantify topology, they extend the information beyond conventional cosmological studies of topology in terms of genus and Euler characteristic. The richer information content of Betti numbers goes along the availability of fast algorithms to compute them. For continuous density fields, we determine the scale-dependence of Betti numbers by invoking the cosmologically familiar filtration of sublevel or superlevel sets defined by density thresholds. For the discrete galaxy distribution, however, the analysis is based on the alpha shapes of the particles. These simplicial complexes constitute an ordered sequence of nested subsets of the Delaunay tessellation, a filtration defined by the scale parameter, α. As they are homotopy equivalent to the sublevel sets of the distance field, they are an excellent tool for assessing the topological structure of a discrete point distribution. In order to develop an intuitive understanding for the behavior of Betti numbers as a function of α, and their relation to the morphological patterns in the Cosmic Web, we first study them within the context of simple heuristic Voronoi clustering models. These can be tuned to consist of specific morphological elements of the Cosmic Web, i.e. clusters, filaments, or sheets. To elucidate the relative prominence of the various Betti numbers in different stages of morphological evolution, we introduce the concept of alpha tracks. Subsequently, we address the topology of structures emerging in the standard LCDM scenario and in cosmological scenarios with alternative dark energy content. The evolution of the Betti numbers is shown to reflect the hierarchical evolution of the Cosmic Web. We also demonstrate that the scale-dependence of the Betti numbers yields a promising measure of cosmological parameters, with a potential to help in determining the nature of dark energy and to probe primordial non-Gaussianities. We also discuss the expected Betti numbers as a function of the density threshold for superlevel sets of a Gaussian random field. Finally, we introduce the concept of persistent homology. It measures scale levels of the mass distribution and allows us to separate small from large scale features. Within the context of the hierarchical cosmic structure formation, persistence provides a natural formalism for a multiscale topology study of the Cosmic Web.
AU - Van De Weygaert, Rien
AU - Vegter, Gert
AU - Edelsbrunner, Herbert
AU - Jones, Bernard
AU - Pranav, Pratyush
AU - Park, Changbom
AU - Hellwing, Wojciech
AU - Eldering, Bob
AU - Kruithof, Nico
AU - Bos, Patrick
AU - Hidding, Johan
AU - Feldbrugge, Job
AU - Ten Have, Eline
AU - Van Engelen, Matti
AU - Caroli, Manuel
AU - Teillaud, Monique
ED - Gavrilova, Marina
ED - Tan, Kenneth
ED - Mostafavi, Mir
ID - 3335
T2 - Transactions on Computational Science XIV
TI - Alpha, Betti and the Megaparsec Universe: On the topology of the Cosmic Web
VL - 6970
ER -
TY - CONF
AB - We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance µ in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution shape P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. An alternative algorithm, based purely on rational arithmetic, answers the same deconstruction problem, up to an uncertainty parameter, and its running time depends on the parameter δ (in addition to the other input parameters: n, δ and the radius of the disk). If the input shape is found to be approximable, the rational-arithmetic algorithm also computes an approximate solution shape for the problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution shape P with at most one more vertex than a vertex-minimal one. Our study is motivated by applications from two different domains. However, since the offset operation has numerous uses, we anticipate that the reverse question that we study here will be still more broadly applicable. We present results obtained with our implementation of the rational-arithmetic algorithm.
AU - Berberich, Eric
AU - Halperin, Dan
AU - Kerber, Michael
AU - Pogalnikova, Roza
ID - 3329
T2 - Proceedings of the twenty-seventh annual symposium on Computational geometry
TI - Deconstructing approximate offsets
ER -
TY - JOUR
AB - Given an algebraic hypersurface O in ℝd, how many simplices are necessary for a simplicial complex isotopic to O? We address this problem and the variant where all vertices of the complex must lie on O. We give asymptotically tight worst-case bounds for algebraic plane curves. Our results gradually improve known bounds in higher dimensions; however, the question for tight bounds remains unsolved for d ≥ 3.
AU - Kerber, Michael
AU - Sagraloff, Michael
ID - 3332
IS - 3
JF - Graphs and Combinatorics
TI - A note on the complexity of real algebraic hypersurfaces
VL - 27
ER -
TY - CONF
AB - We consider the problem of approximating all real roots of a square-free polynomial f. Given isolating intervals, our algorithm refines each of them to a width at most 2-L, that is, each of the roots is approximated to L bits after the binary point. Our method provides a certified answer for arbitrary real polynomials, only requiring finite approximations of the polynomial coefficient and choosing a suitable working precision adaptively. In this way, we get a correct algorithm that is simple to implement and practically efficient. Our algorithm uses the quadratic interval refinement method; we adapt that method to be able to cope with inaccuracies when evaluating f, without sacrificing its quadratic convergence behavior. We prove a bound on the bit complexity of our algorithm in terms of degree, coefficient size and discriminant. Our bound improves previous work on integer polynomials by a factor of deg f and essentially matches best known theoretical bounds on root approximation which are obtained by very sophisticated algorithms.
AU - Kerber, Michael
AU - Sagraloff, Michael
ID - 3330
TI - Root refinement for real polynomials
ER -
TY - CONF
AB - We report on a generic uni- and bivariate algebraic kernel that is publicly available with CGAL 3.7. It comprises complete, correct, though efficient state-of-the-art implementations on polynomials, roots of polynomial systems, and the support to analyze algebraic curves defined by bivariate polynomials. The kernel design is generic, that is, various number types and substeps can be exchanged. It is accompanied with a ready-to-use interface to enable arrangements induced by algebraic curves, that have already been used as basis for various geometric applications, as arrangements on Dupin cyclides or the triangulation of algebraic surfaces. We present two novel applications: arrangements of rotated algebraic curves and Boolean set operations on polygons bounded by segments of algebraic curves. We also provide experiments showing that our general implementation is competitive and even often clearly outperforms existing implementations that are explicitly tailored for specific types of non-linear curves that are available in CGAL.
AU - Berberich, Eric
AU - Hemmer, Michael
AU - Kerber, Michael
ID - 3328
TI - A generic algebraic kernel for non linear geometric applications
ER -
TY - JOUR
AU - Edelsbrunner, Herbert
AU - Pach, János
AU - Ziegler, Günter
ID - 3334
IS - 1
JF - Discrete & Computational Geometry
TI - Letter from the new editors-in-chief
VL - 45
ER -
TY - JOUR
AB - Compositional theories are crucial when designing large and complex systems from smaller components. In this work we propose such a theory for synchronous concurrent systems. Our approach follows so-called interface theories, which use game-theoretic interpretations of composition and refinement. These are appropriate for systems with distinct inputs and outputs, and explicit conditions on inputs that must be enforced during composition. Our interfaces model systems that execute in an infinite sequence of synchronous rounds. At each round, a contract must be satisfied. The contract is simply a relation specifying the set of valid input/output pairs. Interfaces can be composed by parallel, serial or feedback composition. A refinement relation between interfaces is defined, and shown to have two main properties: (1) it is preserved by composition, and (2) it is equivalent to substitutability, namely, the ability to replace an interface by another one in any context. Shared refinement and abstraction operators, corresponding to greatest lower and least upper bounds with respect to refinement, are also defined. Input-complete interfaces, that impose no restrictions on inputs, and deterministic interfaces, that produce a unique output for any legal input, are discussed as special cases, and an interesting duality between the two classes is exposed. A number of illustrative examples are provided, as well as algorithms to compute compositions, check refinement, and so on, for finite-state interfaces.
AU - Tripakis, Stavros
AU - Lickly, Ben
AU - Henzinger, Thomas A
AU - Lee, Edward
ID - 3353
IS - 4
JF - ACM Transactions on Programming Languages and Systems (TOPLAS)
TI - A theory of synchronous relational interfaces
VL - 33
ER -
TY - CONF
AB - Byzantine Fault Tolerant (BFT) protocols aim to improve the reliability of distributed systems. They enable systems to tolerate arbitrary failures in a bounded number of nodes. BFT protocols are usually proven correct for certain safety and liveness properties. However, recent studies have shown that the performance of state-of-the-art BFT protocols decreases drastically in the presence of even a single malicious node. This motivates a formal quantitative analysis of BFT protocols to investigate their performance characteristics under different scenarios. We present HyPerf, a new hybrid methodology based on model checking and simulation techniques for evaluating the performance of BFT protocols. We build a transition system corresponding to a BFT protocol and systematically explore the set of behaviors allowed by the protocol. We associate certain timing information with different operations in the protocol, like cryptographic operations and message transmission. After an elaborate state exploration, we use the time information to evaluate the performance characteristics of the protocol using simulation techniques. We integrate our framework in Mace, a tool for building and verifying distributed systems. We evaluate the performance of PBFT using our framework. We describe two different use-cases of our methodology. For the benign operation of the protocol, we use the time information as random variables to compute the probability distribution of the execution times. In the presence of faults, we estimate the worst-case performance of the protocol for various attacks that can be employed by malicious nodes. Our results show the importance of hybrid techniques in systematically analyzing the performance of large-scale systems.
AU - Halalai, Raluca
AU - Henzinger, Thomas A
AU - Singh, Vasu
ID - 3355
TI - Quantitative evaluation of BFT protocols
ER -
TY - CONF
AB - A controller for a discrete game with ω-regular objectives requires attention if, intuitively, it requires measuring the state and switching from the current control action. Minimum attention controllers are preferable in modern shared implementations of cyber-physical systems because they produce the least burden on system resources such as processor time or communication bandwidth. We give algorithms to compute minimum attention controllers for ω-regular objectives in imperfect information discrete two-player games. We show a polynomial-time reduction from minimum attention controller synthesis to synthesis of controllers for mean-payoff parity objectives in games of incomplete information. This gives an optimal EXPTIME-complete synthesis algorithm. We show that the minimum attention controller problem is decidable for infinite state systems with finite bisimulation quotients. In particular, the problem is decidable for timed and rectangular automata.
AU - Chatterjee, Krishnendu
AU - Majumdar, Ritankar
ED - Fahrenberg, Uli
ED - Tripakis, Stavros
ID - 3350
TI - Minimum attention controller synthesis for omega regular objectives
VL - 6919
ER -
TY - CONF
AB - In two-player games on graph, the players construct an infinite path through the game graph and get a reward computed by a payoff function over infinite paths. Over weighted graphs, the typical and most studied payoff functions compute the limit-average or the discounted sum of the rewards along the path. Besides their simple definition, these two payoff functions enjoy the property that memoryless optimal strategies always exist. In an attempt to construct other simple payoff functions, we define a class of payoff functions which compute an (infinite) weighted average of the rewards. This new class contains both the limit-average and the discounted sum functions, and we show that they are the only members of this class which induce memoryless optimal strategies, showing that there is essentially no other simple payoff functions.
AU - Chatterjee, Krishnendu
AU - Doyen, Laurent
AU - Singh, Rohit
ED - Owe, Olaf
ED - Steffen, Martin
ED - Telle, Jan Arne
ID - 3351
TI - On memoryless quantitative objectives
VL - 6914
ER -
TY - JOUR
AB - We consider two-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 consider ω-regular winning conditions specified as parity objectives. Both players are allowed to use randomization when choosing their moves. We study the computation of the limit-winning set of states, consisting of the states where the sup-inf value of the game for player 1 is 1: in other words, a state is limit-winning if player 1 can ensure a probability of winning arbitrarily close to 1. We show that the limit-winning set can be computed in O(n2d+2) time, where n is the size of the game structure and 2d is the number of priorities (or colors). The membership problem of whether a state belongs to the limit-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 are considerably more involved than those for turn-based games. This is because concurrent games do not satisfy two of the most fundamental properties of turn-based parity games. First, in concurrent games limit-winning strategies require randomization; and second, they require infinite memory.
AU - Chatterjee, Krishnendu
AU - De Alfaro, Luca
AU - Henzinger, Thomas A
ID - 3354
IS - 4
JF - ACM Transactions on Computational Logic (TOCL)
TI - Qualitative concurrent parity games
VL - 12
ER -
TY - CONF
AB - Games on graphs provide a natural model for reactive non-terminating systems. In such games, the interaction of two players on an arena results in an infinite path that describes a run of the system. Different settings are used to model various open systems in computer science, as for instance turn-based or concurrent moves, and deterministic or stochastic transitions. In this paper, we are interested in turn-based games, and specifically in deterministic parity games and stochastic reachability games (also known as simple stochastic games). We present a simple, direct and efficient reduction from deterministic parity games to simple stochastic games: it yields an arena whose size is linear up to a logarithmic factor in size of the original arena.
AU - Chatterjee, Krishnendu
AU - Fijalkow, Nathanaël
ID - 3349
TI - A reduction from parity games to simple stochastic games
VL - 54
ER -
TY - JOUR
AB - Recently reported synthetic routes for the production of hollow nanoparticles have stimulated significant interest for the possibilities this novel geometry offers. While advantageous properties have been found and innovative applications have been proposed, the development of the full potential of these new nanostructures is still strongly tied to the extent of control that can be accomplished over their characteristics (e.g., composition, size, shell thickness, and nanocrystalline structure). In the present work, we investigate the means and limits of control over these parameters that can be obtained by the Kirkendall effect synthetic route on cadmium chalcogenide nanocrystalline shells. We demonstrate that the selection of the reactants and oxidation conditions allows some extent of control of the nanocrystalline structure and thickness of the shell. However, the tuning range is limited by the intrinsic restrictions of the synthetic procedure and by the dependence of the particle geometry on the same reaction conditions. Thus, we further explore the range of control over the shell parameters that can be accomplished through post-synthesis processes, such as chemical etching and thermal annealing.
AU - Ibáñez, Maria
AU - Fan, Jiandong
AU - Li, Wenhua
AU - Cadavid, Doris
AU - Nafria, Raquel
AU - Carrete, Alex
AU - Cabot, Andreu
ID - 335
IS - 12
JF - Chemistry of Materials
TI - Means and limits of control of the shell parameters in hollow nanoparticles obtained by the Kirkendall effect
VL - 23
ER -
TY - JOUR
AB - Exploring the connection of biology with reactive systems to better understand living systems.
AU - Fisher, Jasmin
AU - Harel, David
AU - Henzinger, Thomas A
ID - 3352
IS - 10
JF - Communications of the ACM
TI - Biology as reactivity
VL - 54
ER -
TY - CONF
AB - State-transition systems communicating by shared variables have been the underlying model of choice for applications of model checking. Such formalisms, however, have difficulty with modeling process creation or death and communication reconfigurability. Here, we introduce “dynamic reactive modules” (DRM), a state-transition modeling formalism that supports dynamic reconfiguration and creation/death of processes. The resulting formalism supports two types of variables, data variables and reference variables. Reference variables enable changing the connectivity between processes and referring to instances of processes. We show how this new formalism supports parallel composition and refinement through trace containment. DRM provide a natural language for modeling (and ultimately reasoning about) biological systems and multiple threads communicating through shared variables.
AU - Fisher, Jasmin
AU - Henzinger, Thomas A
AU - Nickovic, Dejan
AU - Piterman, Nir
AU - Singh, Anmol
AU - Vardi, Moshe
ID - 3362
TI - Dynamic reactive modules
VL - 6901
ER -
TY - CONF
AB - We present the tool Quasy, a quantitative synthesis tool. Quasy takes qualitative and quantitative specifications and automatically constructs a system that satisfies the qualitative specification and optimizes the quantitative specification, if such a system exists. The user can choose between a system that satisfies and optimizes the specifications (a) under all possible environment behaviors or (b) under the most-likely environment behaviors given as a probability distribution on the possible input sequences. Quasy solves these two quantitative synthesis problems by reduction to instances of 2-player games and Markov Decision Processes (MDPs) with quantitative winning objectives. Quasy can also be seen as a game solver for quantitative games. Most notable, it can solve lexicographic mean-payoff games with 2 players, MDPs with mean-payoff objectives, and ergodic MDPs with mean-payoff parity objectives.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Jobstmann, Barbara
AU - Singh, Rohit
ID - 3365
TI - QUASY: quantitative synthesis tool
VL - 6605
ER -
TY - CONF
AB - In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ>0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0,1), the running time is O(C(1-δ)ΓR(n)log n), where C(1-δ)Γ is the number of homology classes with persistence at least (1-δ)Γ, n is the total number of simplices, and R(n) is the complexity of computing the rank of an n x n matrix with O(n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C(1-δ)Γn2.376) algorithm, a O(C(1-δ)Γn2.28) Las-Vegas algorithm, or a O(C(1-δ)Γn2+ε) Monte-Carlo algorithm for an arbitrary ε>0.
AU - Chen, Chao
AU - Kerber, Michael
ID - 3367
TI - An output sensitive algorithm for persistent homology
ER -
TY - GEN
AB - We consider probabilistic automata on infinite words with acceptance defined by safety, reachability, Büchi, coBüchi, and limit-average conditions. We consider quantitative and qualitative decision problems. We present extensions and adaptations of proofs for probabilistic finite automata and present a complete characterization of the decidability and undecidability frontier of the quantitative and qualitative decision problems for probabilistic automata on infinite words.
AU - Chatterjee, Krishnendu
AU - Henzinger, Thomas A
AU - Tracol, Mathieu
ID - 3363
TI - The decidability frontier for probabilistic automata on infinite words
ER -