@article{1912,
abstract = {Kupffer's vesicle (KV) is the zebrafish organ of laterality, patterning the embryo along its left-right (LR) axis. Regional differences in cell shape within the lumen-lining KV epithelium are essential for its LR patterning function. However, the processes by which KV cells acquire their characteristic shapes are largely unknown. Here, we show that the notochord induces regional differences in cell shape within KV by triggering extracellular matrix (ECM) accumulation adjacent to anterior-dorsal (AD) regions of KV. This localized ECM deposition restricts apical expansion of lumen-lining epithelial cells in AD regions of KV during lumen growth. Our study provides mechanistic insight into the processes by which KV translates global embryonic patterning into regional cell shape differences required for its LR symmetry-breaking function.},
author = {Compagnon, Julien and Barone, Vanessa and Rajshekar, Srivarsha and Kottmeier, Rita and Pranjic-Ferscha, Kornelija and Behrndt, Martin and Heisenberg, Carl-Philipp J},
journal = {Developmental Cell},
number = {6},
pages = {774 -- 783},
publisher = {Cell Press},
title = {{The notochord breaks bilateral symmetry by controlling cell shapes in the Zebrafish laterality organ}},
doi = {10.1016/j.devcel.2014.11.003},
volume = {31},
year = {2014},
}
@article{7598,
author = {Tan, Shutang and Xue, Hong-Wei},
issn = {2211-1247},
journal = {Cell Reports},
number = {5},
pages = {1692--1702},
publisher = {Elsevier},
title = {{Casein kinase 1 regulates ethylene synthesis by phosphorylating and promoting the turnover of ACS5}},
doi = {10.1016/j.celrep.2014.10.047},
volume = {9},
year = {2014},
}
@article{8021,
abstract = {Most excitatory inputs in the mammalian brain are made on dendritic spines, rather than on dendritic shafts. Spines compartmentalize calcium, and this biochemical isolation can underlie input-specific synaptic plasticity, providing a raison d'etre for spines. However, recent results indicate that the spine can experience a membrane potential different from that in the parent dendrite, as though the spine neck electrically isolated the spine. Here we use two-photon calcium imaging of mouse neocortical pyramidal neurons to analyze the correlation between the morphologies of spines activated under minimal synaptic stimulation and the excitatory postsynaptic potentials they generate. We find that excitatory postsynaptic potential amplitudes are inversely correlated with spine neck lengths. Furthermore, a spike timing-dependent plasticity protocol, in which two-photon glutamate uncaging over a spine is paired with postsynaptic spikes, produces rapid shrinkage of the spine neck and concomitant increases in the amplitude of the evoked spine potentials. Using numerical simulations, we explore the parameter regimes for the spine neck resistance and synaptic conductance changes necessary to explain our observations. Our data, directly correlating synaptic and morphological plasticity, imply that long-necked spines have small or negligible somatic voltage contributions, but that, upon synaptic stimulation paired with postsynaptic activity, they can shorten their necks and increase synaptic efficacy, thus changing the input/output gain of pyramidal neurons. },
author = {Araya, R. and Vogels, Tim P and Yuste, R.},
issn = {1091-6490},
journal = {Proceedings of the National Academy of Sciences},
number = {28},
pages = {E2895--E2904},
publisher = {Proceedings of the National Academy of Sciences},
title = {{Activity-dependent dendritic spine neck changes are correlated with synaptic strength}},
doi = {10.1073/pnas.1321869111},
volume = {111},
year = {2014},
}
@article{8022,
abstract = {Populations of neurons in motor cortex engage in complex transient dynamics of large amplitude during the execution of limb movements. Traditional network models with stochastically assigned synapses cannot reproduce this behavior. Here we introduce a class of cortical architectures with strong and random excitatory recurrence that is stabilized by intricate, fine-tuned inhibition, optimized from a control theory perspective. Such networks transiently amplify specific activity states and can be used to reliably execute multidimensional movement patterns. Similar to the experimental observations, these transients must be preceded by a steady-state initialization phase from which the network relaxes back into the background state by way of complex internal dynamics. In our networks, excitation and inhibition are as tightly balanced as recently reported in experiments across several brain areas, suggesting inhibitory control of complex excitatory recurrence as a generic organizational principle in cortex.},
author = {Hennequin, Guillaume and Vogels, Tim P and Gerstner, Wulfram},
issn = {0896-6273},
journal = {Neuron},
number = {6},
pages = {1394--1406},
publisher = {Elsevier},
title = {{Optimal control of transient dynamics in balanced networks supports generation of complex movements}},
doi = {10.1016/j.neuron.2014.04.045},
volume = {82},
year = {2014},
}
@article{8023,
abstract = {Uniform random sparse network architectures are ubiquitous in computational neuroscience, but the implicit hypothesis that they are a good representation of real neuronal networks has been met with skepticism. Here we used two experimental data sets, a study of triplet connectivity statistics and a data set measuring neuronal responses to channelrhodopsin stimuli, to evaluate the fidelity of thousands of model networks. Network architectures comprised three neuron types (excitatory, fast spiking, and nonfast spiking inhibitory) and were created from a set of rules that govern the statistics of the resulting connection types. In a high-dimensional parameter scan, we varied the degree distributions (i.e., how many cells each neuron connects with) and the synaptic weight correlations of synapses from or onto the same neuron. These variations converted initially uniform random and homogeneously connected networks, in which every neuron sent and received equal numbers of synapses with equal synaptic strength distributions, to highly heterogeneous networks in which the number of synapses per neuron, as well as average synaptic strength of synapses from or to a neuron were variable. By evaluating the impact of each variable on the network structure and dynamics, and their similarity to the experimental data, we could falsify the uniform random sparse connectivity hypothesis for 7 of 36 connectivity parameters, but we also confirmed the hypothesis in 8 cases. Twenty-one parameters had no substantial impact on the results of the test protocols we used.},
author = {Tomm, Christian and Avermann, Michael and Petersen, Carl and Gerstner, Wulfram and Vogels, Tim P},
issn = {1522-1598},
journal = {Journal of Neurophysiology},
number = {8},
pages = {1801--1814},
publisher = {American Physiological Society},
title = {{Connection-type-specific biases make uniform random network models consistent with cortical recordings}},
doi = {10.1152/jn.00629.2013},
volume = {112},
year = {2014},
}
@inproceedings{1374,
abstract = {We study two-player zero-sum games over infinite-state graphs equipped with ωB and finitary conditions. Our first contribution is about the strategy complexity, i.e the memory required for winning strategies: we prove that over general infinite-state graphs, memoryless strategies are sufficient for finitary Büchi, and finite-memory suffices for finitary parity games. We then study pushdown games with boundedness conditions, with two contributions. First we prove a collapse result for pushdown games with ωB-conditions, implying the decidability of solving these games. Second we consider pushdown games with finitary parity along with stack boundedness conditions, and show that solving these games is EXPTIME-complete.},
author = {Chatterjee, Krishnendu and Fijalkow, Nathanaël},
booktitle = {22nd EACSL Annual Conference on Computer Science Logic},
location = {Torino, Italy},
pages = {181 -- 196},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Infinite-state games with finitary conditions}},
doi = {10.4230/LIPIcs.CSL.2013.181},
volume = {23},
year = {2013},
}
@inproceedings{1385,
abstract = {It is often difficult to correctly implement a Boolean controller for a complex system, especially when concurrency is involved. Yet, it may be easy to formally specify a controller. For instance, for a pipelined processor it suffices to state that the visible behavior of the pipelined system should be identical to a non-pipelined reference system (Burch-Dill paradigm). We present a novel procedure to efficiently synthesize multiple Boolean control signals from a specification given as a quantified first-order formula (with a specific quantifier structure). Our approach uses uninterpreted functions to abstract details of the design. We construct an unsatisfiable SMT formula from the given specification. Then, from just one proof of unsatisfiability, we use a variant of Craig interpolation to compute multiple coordinated interpolants that implement the Boolean control signals. Our method avoids iterative learning and back-substitution of the control functions. We applied our approach to synthesize a controller for a simple two-stage pipelined processor, and present first experimental results.},
author = {Hofferek, Georg and Gupta, Ashutosh and Könighofer, Bettina and Jiang, Jie and Bloem, Roderick},
booktitle = {2013 Formal Methods in Computer-Aided Design},
location = {Portland, OR, United States},
pages = {77 -- 84},
publisher = {IEEE},
title = {{Synthesizing multiple boolean functions using interpolation on a single proof}},
doi = {10.1109/FMCAD.2013.6679394},
year = {2013},
}
@inproceedings{1387,
abstract = {Choices made by nondeterministic word automata depend on both the past (the prefix of the word read so far) and the future (the suffix yet to be read). In several applications, most notably synthesis, the future is diverse or unknown, leading to algorithms that are based on deterministic automata. Hoping to retain some of the advantages of nondeterministic automata, researchers have studied restricted classes of nondeterministic automata. Three such classes are nondeterministic automata that are good for trees (GFT; i.e., ones that can be expanded to tree automata accepting the derived tree languages, thus whose choices should satisfy diverse futures), good for games (GFG; i.e., ones whose choices depend only on the past), and determinizable by pruning (DBP; i.e., ones that embody equivalent deterministic automata). The theoretical properties and relative merits of the different classes are still open, having vagueness on whether they really differ from deterministic automata. In particular, while DBP ⊆ GFG ⊆ GFT, it is not known whether every GFT automaton is GFG and whether every GFG automaton is DBP. Also open is the possible succinctness of GFG and GFT automata compared to deterministic automata. We study these problems for ω-regular automata with all common acceptance conditions. We show that GFT=GFG⊃DBP, and describe a determinization construction for GFG automata.},
author = {Boker, Udi and Kuperberg, Denis and Kupferman, Orna and Skrzypczak, Michał},
location = {Riga, Latvia},
number = {PART 2},
pages = {89 -- 100},
publisher = {Springer},
title = {{Nondeterminism in the presence of a diverse or unknown future}},
doi = {10.1007/978-3-642-39212-2_11},
volume = {7966},
year = {2013},
}
@article{1442,
abstract = {We give a cohomological interpretation of both the Kac polynomial and the refined Donaldson-Thomas-invariants of quivers. This interpretation yields a proof of a conjecture of Kac from 1982 and gives a new perspective on recent work of Kontsevich-Soibelman. Thisis achieved by computing, via an arithmetic Fourier transform, the dimensions of the isotypical components of the cohomology of associated Nakajima quiver varieties under the action of a Weyl group. The generating function of the corresponding Poincare polynomials is an extension of Hua's formula for Kac polynomials of quivers involving Hall-Littlewood symmetric functions. The resulting formulae contain a wide range of information on the geometry of the quiver varieties.},
author = {Tamas Hausel and Letellier, Emmanuel and Rodríguez Villegas, Fernando},
journal = {Annals of Mathematics},
number = {3},
pages = {1147 -- 1168},
publisher = {Princeton University Press},
title = {{Positivity for Kac polynomials and DT-invariants of quivers}},
doi = {10.4007/annals.2013.177.3.8},
volume = {177},
year = {2013},
}
@inbook{1443,
abstract = {Here we survey several results and conjectures on the cohomology of the total space of the Hitchin system: the moduli space of semi-stable rank n and degree d Higgs bundles on a complex algebraic curve C. The picture emerging is a dynamic mixture of ideas originating in theoretical physics such as gauge theory and mirror symmetry, Weil conjectures in arithmetic algebraic geometry, representation theory of finite groups of Lie type and Langlands duality in number theory.},
author = {Tamas Hausel},
booktitle = {Handbook of Moduli: Volume II},
pages = {29 -- 70},
publisher = {International Press},
title = {{Global topology of the Hitchin system}},
volume = {25},
year = {2013},
}
@article{1470,
abstract = {We show that a natural isomorphism between the rational cohomology groups of the two zero-dimensional Hilbert schemes of n-points of two surfaces, the affine plane minus the axes and the cotangent bundle of an elliptic curve, exchanges the weight filtration on the first set of cohomology groups with the perverse Leray filtration associated with a natural fibration on the second set of cohomology groups. We discuss some associated hard Lefschetz phenomena.},
author = {De Cataldo, Mark A and Tamas Hausel and Migliorini, Luca},
journal = {Journal of Singularities},
pages = {23 -- 38},
publisher = {Worldwide Center of Mathematics},
title = {{Exchange between perverse and weight filtration for the Hilbert schemes of points of two surfaces}},
doi = {10.5427/jsing.2013.7c},
volume = {7},
year = {2013},
}
@article{1759,
abstract = {We report an electric-field-induced giant modulation of the hole g factor in SiGe nanocrystals. The observed effect is ascribed to a so-far overlooked contribution to the g factor that stems from the mixing between heavy- and light-hole wave functions. We show that the relative displacement between the confined heavy- and light-hole states, occurring upon application of the electric field, alters their mixing strength leading to a strong nonmonotonic modulation of the g factor.},
author = {Ares, Natalia and Golovach, Vitaly N and Georgios Katsaros and Stoffel, Mathieu and Fournel, Frank and Glazman, Leonid I and Schmidt, Oliver G and De Franceschi, Silvano},
journal = {Physical Review Letters},
number = {4},
publisher = {American Physical Society},
title = {{Nature of tunable hole g factors in quantum dots}},
doi = {10.1103/PhysRevLett.110.046602},
volume = {110},
year = {2013},
}
@article{1760,
abstract = {We report on hole g-factor measurements in three terminal SiGe self-assembled quantum dot devices with a top gate electrode positioned very close to the nanostructure. Measurements of both the perpendicular as well as the parallel g-factor reveal significant changes for a small modulation of the top gate voltage. From the observed modulations, we estimate that, for realistic experimental conditions, hole spins can be electrically manipulated with Rabi frequencies in the order of 100 MHz. This work emphasises the potential of hole-based nano-devices for efficient spin manipulation by means of the g-tensor modulation technique.},
author = {Ares, Natalia and Georgios Katsaros and Golovach, Vitaly N and Zhang, Jianjun and Prager, Aaron A and Glazman, Leonid I and Schmidt, Oliver G and De Franceschi, Silvano},
journal = {Applied Physics Letters},
number = {26},
publisher = {American Institute of Physics},
title = {{SiGe quantum dots for fast hole spin Rabi oscillations}},
doi = {10.1063/1.4858959},
volume = {103},
year = {2013},
}
@article{1786,
abstract = {We report the experimental observation and a theoretical explanation of collective suppression of linewidths for multiple superconducting qubits coupled to a good cavity. This demonstrates how strong qubit-cavity coupling can significantly modify the dephasing and dissipation processes that might be expected for individual qubits, and can potentially improve coherence times in many-body circuit QED.},
author = {Nissen, Felix and Johannes Fink and Mlynek, Jonas A and Wallraff, Andreas and Keeling, Jonathan M},
journal = {Physical Review Letters},
number = {20},
publisher = {American Physical Society},
title = {{Collective suppression of linewidths in circuit QED}},
doi = {10.1103/PhysRevLett.110.203602},
volume = {110},
year = {2013},
}
@article{2009,
abstract = {Traditional statistical methods for confidentiality protection of statistical databases do not scale well to deal with GWAS databases especially in terms of guarantees regarding protection from linkage to external information. 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, although the guarantees may come at a serious price in terms of data utility. 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.},
author = {Uhler, Caroline and Slavkovic, Aleksandra and Fienberg, Stephen},
journal = {Journal of Privacy and Confidentiality },
number = {1},
pages = {137 -- 166},
publisher = {Carnegie Mellon University},
title = {{Privacy-preserving data sharing for genome-wide association studies}},
doi = {10.29012/jpc.v5i1.629},
volume = {5},
year = {2013},
}
@article{2010,
abstract = {Many algorithms for inferring causality rely heavily on the faithfulness assumption. The main justification for imposing this assumption is that the set of unfaithful distributions has Lebesgue measure zero, since it can be seen as a collection of hypersurfaces in a hypercube. However, due to sampling error the faithfulness condition alone is not sufficient for statistical estimation, and strong-faithfulness has been proposed and assumed to achieve uniform or high-dimensional consistency. In contrast to the plain faithfulness assumption, the set of distributions that is not strong-faithful has nonzero Lebesgue measure and in fact, can be surprisingly large as we show in this paper. We study the strong-faithfulness condition from a geometric and combinatorial point of view and give upper and lower bounds on the Lebesgue measure of strong-faithful distributions for various classes of directed acyclic graphs. Our results imply fundamental limitations for the PC-algorithm and potentially also for other algorithms based on partial correlation testing in the Gaussian case.},
author = {Uhler, Caroline and Raskutti, Garvesh and Bühlmann, Peter and Yu, Bin},
journal = {The Annals of Statistics},
number = {2},
pages = {436 -- 463},
publisher = {Institute of Mathematical Statistics},
title = {{Geometry of the faithfulness assumption in causal inference}},
doi = {10.1214/12-AOS1080},
volume = {41},
year = {2013},
}
@article{2117,
abstract = {We prove new upper and lower bounds for Banach space-valued stochastic integrals with respect to a compensated Poisson random measure. Our estimates apply to Banach spaces with non-trivial martingale (co)type and extend various results in the literature. We also develop a Malliavin framework to interpret Poisson stochastic integrals as vector-valued Skorohod integrals, and prove a Clark-Ocone representation formula.},
author = {Dirksen, Sjoerd and Jan Maas and van Neerven, Jan M},
journal = {Electronic Journal of Probability},
publisher = {Institute of Mathematical Statistics},
title = {{Poisson stochastic integration in Banach spaces}},
doi = {10.1214/EJP.v18-2945 },
volume = {18},
year = {2013},
}
@article{2129,
abstract = {This paper continues the investigation of `Wasserstein-like' transportation distances for probability measures on discrete sets. We prove that the discrete transportation metrics on the d-dimensional discrete torus with mesh size 1/N converge, when N→∞, to the standard 2-Wasserstein distance W_2 on the continuous torus in the sense of Gromov-Hausdorff. This is the first convergence result for the recently developed discrete transportation metrics. The result shows the compatibility between these metrics and the well-established 2-Wasserstein metric.
},
author = {Gigli, Nicola and Jan Maas},
journal = {SIAM Journal on Mathematical Analysis},
number = {2},
pages = {879 -- 899},
publisher = {Society for Industrial and Applied Mathematics },
title = {{Gromov-Hausdorff convergence of discrete transportation metrics}},
doi = {10.1137/120886315 },
volume = {45},
year = {2013},
}
@article{2139,
abstract = {Recently it has been shown that pairs of atoms can form metastable bonds due to non-conservative forces induced by dissipation [Lemeshko&Weimer, Nature Comm. 4, 2230 (2013)]. Here we study the dynamics of interaction-induced coherent population trapping - the process responsible for the formation of dissipatively bound molecules. We derive the effective dissipative potentials induced between ultracold atoms by laser light, and study the time evolution of the scattering states. We demonstrate that binding occurs on short timescales of ~10 microseconds, even if the initial kinetic energy of the atoms significantly exceeds the depth of the dissipative potential. Dissipatively-bound molecules with preordained bond lengths and vibrational wavefunctions can be created and detected in current experiments with ultracold atoms.},
author = {Mikhail Lemeshko},
journal = {Frontiers Physics},
number = {17},
publisher = {Frontiers Media},
title = {{Manipulating scattering of ultracold atoms with light-induced dissipation}},
doi = {10.3389/fphy.2013.00017},
volume = {1},
year = {2013},
}
@article{2152,
author = {Bhongale, Satyan G and Mathey, Ludwig and Zhao, Erhai and Yelin, Susanne F and Mikhail Lemeshko},
journal = {Physical Review Letters},
number = {23},
publisher = {American Physical Society},
title = {{Erratum: Quantum phases of quadrupolar fermi gases in optical lattices}},
doi = {10.1103/PhysRevLett.111.239901},
volume = {111},
year = {2013},
}
@inproceedings{2181,
abstract = {There is a trade-off between performance and correctness in implementing concurrent data structures. Better performance may be achieved at the expense of relaxing correctness, by redefining the semantics of data structures. We address such a redefinition of data structure semantics and present a systematic and formal framework for obtaining new data structures by quantitatively relaxing existing ones. We view a data structure as a sequential specification S containing all "legal" sequences over an alphabet of method calls. Relaxing the data structure corresponds to defining a distance from any sequence over the alphabet to the sequential specification: the k-relaxed sequential specification contains all sequences over the alphabet within distance k from the original specification. In contrast to other existing work, our relaxations are semantic (distance in terms of data structure states). As an instantiation of our framework, we present two simple yet generic relaxation schemes, called out-of-order and stuttering relaxation, along with several ways of computing distances. We show that the out-of-order relaxation, when further instantiated to stacks, queues, and priority queues, amounts to tolerating bounded out-of-order behavior, which cannot be captured by a purely syntactic relaxation (distance in terms of sequence manipulation, e.g. edit distance). We give concurrent implementations of relaxed data structures and demonstrate that bounded relaxations provide the means for trading correctness for performance in a controlled way. The relaxations are monotonic which further highlights the trade-off: increasing k increases the number of permitted sequences, which as we demonstrate can lead to better performance. Finally, since a relaxed stack or queue also implements a pool, we actually have new concurrent pool implementations that outperform the state-of-the-art ones.},
author = {Henzinger, Thomas A and Kirsch, Christoph and Payer, Hannes and Sezgin, Ali and Sokolova, Ana},
booktitle = {Proceedings of the 40th annual ACM SIGPLAN-SIGACT symposium on Principles of programming language},
isbn = {978-1-4503-1832-7},
location = {Rome, Italy},
pages = {317 -- 328},
publisher = {ACM},
title = {{Quantitative relaxation of concurrent data structures}},
doi = {10.1145/2429069.2429109},
year = {2013},
}
@article{2204,
abstract = {We introduce a new platform for quantum simulation of many-body systems based on nonspherical atoms or molecules with zero dipole moments but possessing a significant value of electric quadrupole moments. We consider a quadrupolar Fermi gas trapped in a 2D square optical lattice, and show that the peculiar symmetry and broad tunability of the quadrupole-quadrupole interaction results in a rich phase diagram encompassing unconventional BCS and charge density wave phases, and opens up a perspective to create a topological superfluid. Quadrupolar species, such as metastable alkaline-earth atoms and homonuclear molecules, are stable against chemical reactions and collapse and are readily available in experiment at high densities.},
author = {Bhongale, Satyan G and Mathey, Ludwig and Zhao, Erhai and Yelin, Susanne F and Mikhail Lemeshko},
journal = {Physical Review Letters},
number = {15},
publisher = {American Physical Society},
title = {{Quantum phases of quadrupolar fermi gases in optical lattices}},
doi = {10.1103/PhysRevLett.110.155301},
volume = {110},
year = {2013},
}
@misc{2205,
abstract = {The goal of the present article is to review the major developments that have led to the current understanding of molecule-field interactions and experimental methods for manipulating molecules with electromagnetic fields. Molecule-field interactions are at the core of several, seemingly distinct areas of molecular physics. This is reflected in the organisation of this article, which includes sections on field control of molecular beams, external field traps for cold molecules, control of molecular orientation and molecular alignment, manipulation of molecules by non-conservative forces, ultracold molecules and ultracold chemistry, controlled many-body phenomena, entanglement of molecules and dipole arrays, and stability of molecular systems in high-frequency super-intense laser fields. The article contains 852 references.},
author = {Mikhail Lemeshko and Krems, Roman V and Doyle, John M and Kais, Sabre},
booktitle = {Molecular Physics},
number = {12-13},
pages = {1648 -- 1682},
publisher = {Taylor & Francis},
title = {{Manipulation of molecules with electromagnetic fields}},
doi = {10.1080/00268976.2013.813595},
volume = {111},
year = {2013},
}
@article{2206,
abstract = {Magnetic impurities embedded in inert solids can exhibit long coherence times and interact with one another via their intrinsic anisotropic dipolar interaction. We argue that, as a consequence of these properties, disordered ensembles of magnetic impurities provide an effective platform for realizing a controllable, tunable version of the dipolar quantum spin glass seen in LiHoxY1-xF4. Specifically, we propose and analyze a system composed of dysprosium atoms embedded in solid helium. We describe the phase diagram of the system and discuss the realizability and detectability of the quantum spin glass and antiglass phases.},
author = {Mikhail Lemeshko and Yao, Norman Y and Gorshkov, Alexey V and Weimer, Hendrik and Bennett, Steven D and Momose, Takamasa and Gopalakrishnan, Sarang},
journal = {Physical Review B - Condensed Matter and Materials Physics},
number = {1},
publisher = {American Physical Society},
title = {{Controllable quantum spin glasses with magnetic impurities embedded in quantum solids}},
doi = {10.1103/PhysRevB.88.014426},
volume = {88},
year = {2013},
}
@article{2207,
abstract = {The formation of molecules and supramolecular structures results from bonding by conservative forces acting among electrons and nuclei and giving rise to equilibrium configurations defined by minima of the interaction potential. Here we show that bonding can also occur by the non-conservative forces responsible for interaction-induced coherent population trapping. The bound state arises in a dissipative process and manifests itself as a stationary state at a preordained interatomic distance. Remarkably, such a dissipative bonding is present even when the interactions among the atoms are purely repulsive. The dissipative bound states can be created and studied spectroscopically in present-day experiments with ultracold atoms or molecules and can potentially serve for cooling strongly interacting quantum gases.},
author = {Mikhail Lemeshko and Weimer, Hendrik},
journal = {Nature Communications},
publisher = {Nature Publishing Group},
title = {{Dissipative binding of atoms by non-conservative forces}},
doi = {10.1038/ncomms3230},
volume = {4},
year = {2013},
}
@inproceedings{2210,
abstract = {A straight skeleton is a well-known geometric structure, and several algorithms exist to construct the straight skeleton for a given polygon. In this paper, we ask the reverse question: Given the straight skeleton (in form of a tree with a drawing in the plane, but with the exact position of the leaves unspecified), can we reconstruct the polygon? We show that in most cases there exists at most one polygon; in the remaining case there is an infinite number of polygons determined by one angle that can range in an interval. We can find this (set of) polygon(s) in linear time in the Real RAM computer model.},
author = {Biedl, Therese and Held, Martin and Huber, Stefan},
booktitle = {29th European Workshop on Computational Geometry},
location = {Braunschweig, Germany},
pages = {95 -- 98},
publisher = {TU Braunschweig},
title = {{Reconstructing polygons from embedded straight skeletons}},
year = {2013},
}
@inproceedings{2237,
abstract = {We describe new extensions of the Vampire theorem prover for computing tree interpolants. These extensions generalize Craig interpolation in Vampire, and can also be used to derive sequence interpolants. We evaluated our implementation on a large number of examples over the theory of linear integer arithmetic and integer-indexed arrays, with and without quantifiers. When compared to other methods, our experiments show that some examples could only be solved by our implementation.},
author = {Blanc, Régis and Gupta, Ashutosh and Kovács, Laura and Kragl, Bernhard},
location = {Stellenbosch, South Africa},
pages = {173 -- 181},
publisher = {Springer},
title = {{Tree interpolation in Vampire}},
doi = {10.1007/978-3-642-45221-5_13},
volume = {8312},
year = {2013},
}
@inproceedings{2243,
abstract = {We show that modal logic over universally first-order definable classes of transitive frames is decidable. More precisely, let K be an arbitrary class of transitive Kripke frames definable by a universal first-order sentence. We show that the global and finite global satisfiability problems of modal logic over K are decidable in NP, regardless of choice of K. We also show that the local satisfiability and the finite local satisfiability problems of modal logic over K are decidable in NEXPTIME.},
author = {Michaliszyn, Jakub and Otop, Jan},
location = {Torino, Italy},
pages = {563 -- 577},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Elementary modal logics over transitive structures}},
doi = {10.4230/LIPIcs.CSL.2013.563},
volume = {23},
year = {2013},
}
@article{2247,
abstract = {Cooperative behavior, where one individual incurs a cost to help another, is a wide spread phenomenon. Here we study direct reciprocity in the context of the alternating Prisoner's Dilemma. We consider all strategies that can be implemented by one and two-state automata. We calculate the payoff matrix of all pairwise encounters in the presence of noise. We explore deterministic selection dynamics with and without mutation. Using different error rates and payoff values, we observe convergence to a small number of distinct equilibria. Two of them are uncooperative strict Nash equilibria representing always-defect (ALLD) and Grim. The third equilibrium is mixed and represents a cooperative alliance of several strategies, dominated by a strategy which we call Forgiver. Forgiver cooperates whenever the opponent has cooperated; it defects once when the opponent has defected, but subsequently Forgiver attempts to re-establish cooperation even if the opponent has defected again. Forgiver is not an evolutionarily stable strategy, but the alliance, which it rules, is asymptotically stable. For a wide range of parameter values the most commonly observed outcome is convergence to the mixed equilibrium, dominated by Forgiver. Our results show that although forgiving might incur a short-term loss it can lead to a long-term gain. Forgiveness facilitates stable cooperation in the presence of exploitation and noise.},
author = {Zagorsky, Benjamin and Reiter, Johannes and Chatterjee, Krishnendu and Nowak, Martin},
journal = {PLoS One},
number = {12},
publisher = {Public Library of Science},
title = {{Forgiver triumphs in alternating prisoner's dilemma }},
doi = {10.1371/journal.pone.0080814},
volume = {8},
year = {2013},
}
@inproceedings{2244,
abstract = {We consider two systems (α1,...,αm) and (β1,...,βn) of curves drawn on a compact two-dimensional surface ℳ with boundary. Each αi and each βj is either an arc meeting the boundary of ℳ at its two endpoints, or a closed curve. The αi are pairwise disjoint except for possibly sharing endpoints, and similarly for the βj. We want to "untangle" the βj from the αi by a self-homeomorphism of ℳ; more precisely, we seek an homeomorphism φ: ℳ → ℳ fixing the boundary of ℳ pointwise such that the total number of crossings of the αi with the φ(βj) is as small as possible. This problem is motivated by an application in the algorithmic theory of embeddings and 3-manifolds. We prove that if ℳ is planar, i.e., a sphere with h ≥ 0 boundary components ("holes"), then O(mn) crossings can be achieved (independently of h), which is asymptotically tight, as an easy lower bound shows. In general, for an arbitrary (orientable or nonorientable) surface ℳ with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an O((m + n)4) upper bound, again independent of h and g. },
author = {Matoušek, Jiří and Sedgwick, Eric and Tancer, Martin and Wagner, Uli},
location = {Bordeaux, France},
pages = {472 -- 483},
publisher = {Springer},
title = {{Untangling two systems of noncrossing curves}},
doi = {10.1007/978-3-319-03841-4_41},
volume = {8242},
year = {2013},
}
@inproceedings{2258,
abstract = {In a digital signature scheme with message recovery, rather than transmitting the message m and its signature σ, a single enhanced signature τ is transmitted. The verifier is able to recover m from τ and at the same time verify its authenticity. The two most important parameters of such a scheme are its security and overhead |τ| − |m|. A simple argument shows that for any scheme with “n bits security” |τ| − |m| ≥ n, i.e., the overhead is lower bounded by the security parameter n. Currently, the best known constructions in the random oracle model are far from this lower bound requiring an overhead of n + logq h , where q h is the number of queries to the random oracle. In this paper we give a construction which basically matches the n bit lower bound. We propose a simple digital signature scheme with n + o(logq h ) bits overhead, where q h denotes the number of random oracle queries.
Our construction works in two steps. First, we propose a signature scheme with message recovery having optimal overhead in a new ideal model, the random invertible function model. Second, we show that a four-round Feistel network with random oracles as round functions is tightly “public-indifferentiable” from a random invertible function. At the core of our indifferentiability proof is an almost tight upper bound for the expected number of edges of the densest “small” subgraph of a random Cayley graph, which may be of independent interest.
},
author = {Kiltz, Eike and Pietrzak, Krzysztof Z and Szegedy, Mario},
location = {Santa Barbara, CA, United States},
pages = {571 -- 588},
publisher = {Springer},
title = {{Digital signatures with minimal overhead from indifferentiable random invertible functions}},
doi = {10.1007/978-3-642-40041-4_31},
volume = {8042},
year = {2013},
}
@inproceedings{2259,
abstract = {The learning with rounding (LWR) problem, introduced by Banerjee, Peikert and Rosen at EUROCRYPT ’12, is a variant of learning with errors (LWE), where one replaces random errors with deterministic rounding. The LWR problem was shown to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error ratio are super-polynomial. In this work we resolve the main open problem and give a new reduction that works for a larger range of parameters, allowing for a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater security, which now follows from the worst-case hardness of GapSVP with polynomial (rather than super-polynomial) approximation factors.
As a tool in the reduction, we show that there is a “lossy mode” for the LWR problem, in which LWR samples only reveal partial information about the secret. This property gives us several interesting new applications, including a proof that LWR remains secure with weakly random secrets of sufficient min-entropy, and very simple constructions of deterministic encryption, lossy trapdoor functions and reusable extractors.
Our approach is inspired by a technique of Goldwasser et al. from ICS ’10, which implicitly showed the existence of a “lossy mode” for LWE. By refining this technique, we also improve on the parameters of that work to only requiring a polynomial (instead of super-polynomial) modulus and modulus-to-error ratio.
},
author = {Alwen, Joel F and Krenn, Stephan and Pietrzak, Krzysztof Z and Wichs, Daniel},
location = {Santa Barbara, CA, United States},
number = {1},
pages = {57 -- 74},
publisher = {Springer},
title = {{Learning with rounding, revisited: New reduction properties and applications}},
doi = {10.1007/978-3-642-40041-4_4},
volume = {8042},
year = {2013},
}
@inproceedings{2260,
abstract = {Direct Anonymous Attestation (DAA) is one of the most complex cryptographic protocols deployed in practice. It allows an embedded secure processor known as a Trusted Platform Module (TPM) to attest to the configuration of its host computer without violating the owner’s privacy. DAA has been standardized by the Trusted Computing Group and ISO/IEC.
The security of the DAA standard and all existing schemes is analyzed in the random-oracle model. We provide the first constructions of DAA in the standard model, that is, without relying on random oracles. Our constructions use new building blocks, including the first efficient signatures of knowledge in the standard model, which have many applications beyond DAA.
},
author = {Bernhard, David and Fuchsbauer, Georg and Ghadafi, Essam},
location = {Banff, AB, Canada},
pages = {518 -- 533},
publisher = {Springer},
title = {{Efficient signatures of knowledge and DAA in the standard model}},
doi = {10.1007/978-3-642-38980-1_33},
volume = {7954},
year = {2013},
}
@article{2264,
abstract = {Faithful progression through the cell cycle is crucial to the maintenance and developmental potential of stem cells. Here, we demonstrate that neural stem cells (NSCs) and intermediate neural progenitor cells (NPCs) employ a zinc-finger transcription factor specificity protein 2 (Sp2) as a cell cycle regulator in two temporally and spatially distinct progenitor domains. Differential conditional deletion of Sp2 in early embryonic cerebral cortical progenitors, and perinatal olfactory bulb progenitors disrupted transitions through G1, G2 and M phases, whereas DNA synthesis appeared intact. Cell-autonomous function of Sp2 was identified by deletion of Sp2 using mosaic analysis with double markers, which clearly established that conditional Sp2-null NSCs and NPCs are M phase arrested in vivo. Importantly, conditional deletion of Sp2 led to a decline in the generation of NPCs and neurons in the developing and postnatal brains. Our findings implicate Sp2-dependent mechanisms as novel regulators of cell cycle progression, the absence of which disrupts neurogenesis in the embryonic and postnatal brain.},
author = {Liang, Huixuan and Xiao, Guanxi and Yin, Haifeng and Hippenmeyer, Simon and Horowitz, Jonathan and Ghashghaei, Troy},
journal = {Development},
number = {3},
pages = {552 -- 561},
publisher = {Company of Biologists},
title = {{Neural development is dependent on the function of specificity protein 2 in cell cycle progression}},
doi = {10.1242/dev.085621},
volume = {140},
year = {2013},
}
@inproceedings{2270,
abstract = {Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inher-
ent tradeoff between how general a language is, allowing it to capture more elaborate games, and how hard it is computationally to optimize and solve such games. One prominent such language is the simple yet expressive
Weighted Graph Games (WGGs) representation (Deng and Papadimitriou 1994), which maintains knowledge about synergies between agents in the form of an edge weighted graph. We consider the problem of finding the optimal coalition structure in WGGs. The agents in such games are vertices in a graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. We then provide algorithms with constant factor approximations for planar, minorfree and bounded degree graphs.},
author = {Bachrach, Yoram and Kohli, Pushmeet and Kolmogorov, Vladimir and Zadimoghaddam, Morteza},
location = {Bellevue, WA, United States},
pages = {81--87},
publisher = {AAAI Press},
title = {{Optimal Coalition Structures in Cooperative Graph Games}},
year = {2013},
}
@techreport{2274,
abstract = {Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto'92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.
In this work, we put forward an alternative concept for PoWs -- so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model, using graphs with high "pebbling complexity" and Merkle hash-trees. },
author = {Dziembowski, Stefan and Faust, Sebastian and Kolmogorov, Vladimir and Pietrzak, Krzysztof Z},
publisher = {IST Austria},
title = {{Proofs of Space}},
year = {2013},
}
@inproceedings{2276,
abstract = {The problem of minimizing the Potts energy function frequently occurs in computer vision applications. One way to tackle this NP-hard problem was proposed by Kovtun [19, 20]. It identifies a part of an optimal solution by running k maxflow computations, where k is the number of labels. The number of “labeled” pixels can be significant in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce the runtime to O (log k) maxflow computations (or one parametric maxflow computation). Furthermore, the output of our algorithm allows to speed-up the subsequent alpha expansion for the unlabeled part, or can be used as it is for time-critical applications. To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7] for Tree Metrics . We also show a connection to k-submodular functions from combinatorial optimization, and discuss k-submodular relaxations for general energy functions.},
author = {Gridchyn, Igor and Kolmogorov, Vladimir},
location = {Sydney, Australia},
pages = {2320 -- 2327},
publisher = {IEEE},
title = {{Potts model, parametric maxflow and k-submodular functions}},
doi = {10.1109/ICCV.2013.288},
year = {2013},
}
@article{2277,
abstract = {Redundancies and correlations in the responses of sensory neurons may seem to waste neural resources, but they can also carry cues about structured stimuli and may help the brain to correct for response errors. To investigate the effect of stimulus structure on redundancy in retina, we measured simultaneous responses from populations of retinal ganglion cells presented with natural and artificial stimuli that varied greatly in correlation structure; these stimuli and recordings are publicly available online. Responding to spatio-temporally structured stimuli such as natural movies, pairs of ganglion cells were modestly more correlated than in response to white noise checkerboards, but they were much less correlated than predicted by a non-adapting functional model of retinal response. Meanwhile, responding to stimuli with purely spatial correlations, pairs of ganglion cells showed increased correlations consistent with a static, non-adapting receptive field and nonlinearity. We found that in response to spatio-temporally correlated stimuli, ganglion cells had faster temporal kernels and tended to have stronger surrounds. These properties of individual cells, along with gain changes that opposed changes in effective contrast at the ganglion cell input, largely explained the pattern of pairwise correlations across stimuli where receptive field measurements were possible.},
author = {Simmons, Kristina and Prentice, Jason and Tkacik, Gasper and Homann, Jan and Yee, Heather and Palmer, Stephanie and Nelson, Philip and Balasubramanian, Vijay},
journal = {PLoS Computational Biology},
number = {12},
publisher = {Public Library of Science},
title = {{Transformation of stimulus correlations by the retina}},
doi = {10.1371/journal.pcbi.1003344},
volume = {9},
year = {2013},
}
@article{2256,
abstract = {Linked (Open) Data - bibliographic data on the Semantic Web. Report of the Working Group on Linked Data to the plenary assembly of the Austrian Library Network (translation of the title). Linked Data stands for a certain approach to publishing data on the Web. The underlying idea is to harmonise heterogeneous data sources of different origin in order to improve their accessibility and interoperability, effectively making them queryable as a big distributed database. This report summarises relevant developments in Europe as well as the Linked Data Working Group‘s strategic and technical considerations regarding the publishing of the Austrian Library Network’s (OBV’s) bibliographic datasets. It concludes with the mutual agreement that the implementation of Linked Data principles within the OBV can only be taken into consideration accompanied by a discussion about the provision of the datasets under a free license.},
author = {Danowski, Patrick and Goldfarb, Doron and Schaffner, Verena and Seidler, Wolfram},
journal = {VÖB Mitteilungen},
number = {3/4},
pages = {559 -- 587},
publisher = {Verein Österreichischer Bibliothekarinnen und Bibliothekare},
title = {{Linked (Open) Data - Bibliographische Daten im Semantic Web}},
volume = {66},
year = {2013},
}
@inproceedings{2272,
abstract = {We consider Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x1...xn is the sum of terms over intervals [i,j] where each term is non-zero only if the substring xi...xj equals a prespecified pattern α. Such CRFs can be naturally applied to many sequence tagging problems.
We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively O(nL), O(nLℓmax) and O(nLmin{|D|,log(ℓmax+1)}) where L is the combined length of input patterns, ℓmax is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of (Ye et al., 2009) whose complexities are respectively O(nL|D|), O(n|Γ|L2ℓ2max) and O(nL|D|), where |Γ| is the number of input patterns.
In addition, we give an efficient algorithm for sampling. Finally, we consider the case of non-positive weights. (Komodakis & Paragios, 2009) gave an O(nL) algorithm for computing the MAP. We present a modification that has the same worst-case complexity but can beat it in the best case. },
author = {Takhanov, Rustem and Kolmogorov, Vladimir},
booktitle = {ICML'13 Proceedings of the 30th International Conference on International},
location = {Atlanta, GA, USA},
number = {3},
pages = {145 -- 153},
publisher = {International Machine Learning Society},
title = {{Inference algorithms for pattern-based CRFs on sequence data}},
volume = {28},
year = {2013},
}
@techreport{2273,
abstract = {We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. We present such a generalization for the case of higher-order graphical models, and test it on several real-world problems with promising results.},
author = {Vladimir Kolmogorov},
publisher = {IST Austria},
title = {{Reweighted message passing revisited}},
year = {2013},
}
@article{2282,
abstract = {Epithelial spreading is a common and fundamental aspect of various developmental and disease-related processes such as epithelial closure and wound healing. A key challenge for epithelial tissues undergoing spreading is to increase their surface area without disrupting epithelial integrity. Here we show that orienting cell divisions by tension constitutes an efficient mechanism by which the enveloping cell layer (EVL) releases anisotropic tension while undergoing spreading during zebrafish epiboly. The control of EVL cell-division orientation by tension involves cell elongation and requires myosin II activity to align the mitotic spindle with the main tension axis. We also found that in the absence of tension-oriented cell divisions and in the presence of increased tissue tension, EVL cells undergo ectopic fusions, suggesting that the reduction of tension anisotropy by oriented cell divisions is required to prevent EVL cells from fusing. We conclude that cell-division orientation by tension constitutes a key mechanism for limiting tension anisotropy and thus promoting tissue spreading during EVL epiboly.},
author = {Campinho, Pedro and Behrndt, Martin and Ranft, Jonas and Risler, Thomas and Minc, Nicolas and Heisenberg, Carl-Philipp J},
journal = {Nature Cell Biology},
pages = {1405 -- 1414},
publisher = {Nature Publishing Group},
title = {{Tension-oriented cell divisions limit anisotropic tissue tension in epithelial spreading during zebrafish epiboly}},
doi = {10.1038/ncb2869},
volume = {15},
year = {2013},
}
@article{2284,
abstract = {Background: The brood of ants and other social insects is highly susceptible to pathogens, particularly those that penetrate the soft larval and pupal cuticle. We here test whether the presence of a pupal cocoon, which occurs in some ant species but not in others, affects the sanitary brood care and fungal infection patterns after exposure to the entomopathogenic fungus Metarhizium brunneum. We use a) a comparative approach analysing four species with either naked or cocooned pupae and b) a within-species analysis of a single ant species, in which both pupal types co-exist in the same colony. Results: We found that the presence of a cocoon did not compromise fungal pathogen detection by the ants and that species with cocooned pupae increased brood grooming after pathogen exposure. All tested ant species further removed brood from their nests, which was predominantly expressed towards larvae and naked pupae treated with the live fungal pathogen. In contrast, cocooned pupae exposed to live fungus were not removed at higher rates than cocooned pupae exposed to dead fungus or a sham control. Consistent with this, exposure to the live fungus caused high numbers of infections and fungal outgrowth in larvae and naked pupae, but not in cocooned pupae. Moreover, the ants consistently removed the brood prior to fungal outgrowth, ensuring a clean brood chamber. Conclusion: Our study suggests that the pupal cocoon has a protective effect against fungal infection, causing an adaptive change in sanitary behaviours by the ants. It further demonstrates that brood removal-originally described for honeybees as "hygienic behaviour"-is a widespread sanitary behaviour in ants, which likely has important implications on disease dynamics in social insect colonies.},
author = {Tragust, Simon and Ugelvig, Line V and Chapuisat, Michel and Heinze, Jürgen and Cremer, Sylvia},
journal = {BMC Evolutionary Biology},
number = {1},
publisher = {BioMed Central},
title = {{Pupal cocoons affect sanitary brood care and limit fungal infections in ant colonies}},
doi = {10.1186/1471-2148-13-225},
volume = {13},
year = {2013},
}
@article{2286,
abstract = {The spatiotemporal control of cell divisions is a key factor in epithelial morphogenesis and patterning. Mao et al (2013) now describe how differential rates of proliferation within the Drosophila wing disc epithelium give rise to anisotropic tissue tension in peripheral/proximal regions of the disc. Such global tissue tension anisotropy in turn determines the orientation of cell divisions by controlling epithelial cell elongation.},
author = {Campinho, Pedro and Heisenberg, Carl-Philipp J},
journal = {EMBO Journal},
number = {21},
pages = {2783 -- 2784},
publisher = {Wiley-Blackwell},
title = {{The force and effect of cell proliferation}},
doi = {10.1038/emboj.2013.225},
volume = {32},
year = {2013},
}
@article{2287,
abstract = {Negative frequency-dependent selection should result in equal sex ratios in large populations of dioecious flowering plants, but deviations from equality are commonly reported. A variety of ecological and genetic factors can explain biased sex ratios, although the mechanisms involved are not well understood. Most dioecious species are long-lived and/or clonal complicating efforts to identify stages during the life cycle when biases develop. We investigated the demographic correlates of sex-ratio variation in two chromosome races of Rumex hastatulus, an annual, wind-pollinated colonizer of open habitats from the southern USA. We examined sex ratios in 46 populations and evaluated the hypothesis that the proximity of males in the local mating environment, through its influence on gametophytic selection, is the primary cause of female-biased sex ratios. Female-biased sex ratios characterized most populations of R. hastatulus (mean sex ratio = 0.62), with significant female bias in 89% of populations. Large, high-density populations had the highest proportion of females, whereas smaller, low-density populations had sex ratios closer to equality. Progeny sex ratios were more female biased when males were in closer proximity to females, a result consistent with the gametophytic selection hypothesis. Our results suggest that interactions between demographic and genetic factors are probably the main cause of female-biased sex ratios in R. hastatulus. The annual life cycle of this species may limit the scope for selection against males and may account for the weaker degree of bias in comparison with perennial Rumex species.},
author = {Pickup, Melinda and Barrett, Spencer},
journal = {Ecology and Evolution},
number = {3},
pages = {629 -- 639},
publisher = {Wiley-Blackwell},
title = {{The influence of demography and local mating environment on sex ratios in a wind-pollinated dioecious plant}},
doi = {10.1002/ece3.465},
volume = {3},
year = {2013},
}
@article{2289,
abstract = {Formal verification aims to improve the quality of software by detecting errors before they do harm. At the basis of formal verification is the logical notion of correctness, which purports to capture whether or not a program behaves as desired. We suggest that the boolean partition of software into correct and incorrect programs falls short of the practical need to assess the behavior of software in a more nuanced fashion against multiple criteria. We therefore propose to introduce quantitative fitness measures for programs, specifically for measuring the function, performance, and robustness of reactive programs such as concurrent processes. This article describes the goals of the ERC Advanced Investigator Project QUAREM. The project aims to build and evaluate a theory of quantitative fitness measures for reactive models. Such a theory must strive to obtain quantitative generalizations of the paradigms that have been success stories in qualitative reactive modeling, such as compositionality, property-preserving abstraction and abstraction refinement, model checking, and synthesis. The theory will be evaluated not only in the context of software and hardware engineering, but also in the context of systems biology. In particular, we will use the quantitative reactive models and fitness measures developed in this project for testing hypotheses about the mechanisms behind data from biological experiments.},
author = {Henzinger, Thomas A},
journal = {Computer Science Research and Development},
number = {4},
pages = {331 -- 344},
publisher = {Springer},
title = {{Quantitative reactive modeling and verification}},
doi = {10.1007/s00450-013-0251-7},
volume = {28},
year = {2013},
}
@article{2290,
abstract = {The plant hormone indole-acetic acid (auxin) is essential for many aspects of plant development. Auxin-mediated growth regulation typically involves the establishment of an auxin concentration gradient mediated by polarly localized auxin transporters. The localization of auxin carriers and their amount at the plasma membrane are controlled by membrane trafficking processes such as secretion, endocytosis, and recycling. In contrast to endocytosis or recycling, how the secretory pathway mediates the localization of auxin carriers is not well understood. In this study we have used the differential cell elongation process during apical hook development to elucidate the mechanisms underlying the post-Golgi trafficking of auxin carriers in Arabidopsis. We show that differential cell elongation during apical hook development is defective in Arabidopsis mutant echidna (ech). ECH protein is required for the trans-Golgi network (TGN)-mediated trafficking of the auxin influx carrier AUX1 to the plasma membrane. In contrast, ech mutation only marginally perturbs the trafficking of the highly related auxin influx carrier LIKE-AUX1-3 or the auxin efflux carrier PIN-FORMED-3, both also involved in hook development. Electron tomography reveals that the trafficking defects in ech mutant are associated with the perturbation of secretory vesicle genesis from the TGN. Our results identify differential mechanisms for the post-Golgi trafficking of de novo-synthesized auxin carriers to plasma membrane from the TGN and reveal how trafficking of auxin influx carriers mediates the control of differential cell elongation in apical hook development.},
author = {Boutté, Yohann and Jonsson, Kristoffer and Mcfarlane, Heather and Johnson, Errin and Gendre, Delphine and Swarup, Ranjan and Friml, Jirí and Samuels, Lacey and Robert, Stéphanie and Bhalerao, Rishikesh},
journal = {PNAS},
number = {40},
pages = {16259 -- 16264},
publisher = {National Academy of Sciences},
title = {{ECHIDNA mediated post Golgi trafficking of auxin carriers for differential cell elongation}},
doi = {10.1073/pnas.1309057110},
volume = {110},
year = {2013},
}
@inproceedings{2291,
abstract = {Cryptographic access control promises to offer easily distributed trust and broader applicability, while reducing reliance on low-level online monitors. Traditional implementations of cryptographic access control rely on simple cryptographic primitives whereas recent endeavors employ primitives with richer functionality and security guarantees. Worryingly, few of the existing cryptographic access-control schemes come with precise guarantees, the gap between the policy specification and the implementation being analyzed only informally, if at all. In this paper we begin addressing this shortcoming. Unlike prior work that targeted ad-hoc policy specification, we look at the well-established Role-Based Access Control (RBAC) model, as used in a typical file system. In short, we provide a precise syntax for a computational version of RBAC, offer rigorous definitions for cryptographic policy enforcement of a large class of RBAC security policies, and demonstrate that an implementation based on attribute-based encryption meets our security notions. We view our main contribution as being at the conceptual level. Although we work with RBAC for concreteness, our general methodology could guide future research for uses of cryptography in other access-control models.
},
author = {Ferrara, Anna and Fuchsbauer, Georg and Warinschi, Bogdan},
location = {New Orleans, LA, United States},
pages = {115 -- 129},
publisher = {IEEE},
title = {{Cryptographically enforced RBAC}},
doi = {10.1109/CSF.2013.15},
year = {2013},
}
@inproceedings{2293,
abstract = {Many computer vision problems have an asymmetric distribution of information between training and test time. In this work, we study the case where we are given additional information about the training data, which however will not be available at test time. This situation is called learning using privileged information (LUPI). We introduce two maximum-margin techniques that are able to make use of this additional source of information, and we show that the framework is applicable to several scenarios that have been studied in computer vision before. Experiments with attributes, bounding boxes, image tags and rationales as additional information in object classification show promising results.},
author = {Sharmanska, Viktoriia and Quadrianto, Novi and Lampert, Christoph},
location = {Sydney, Australia},
pages = {825 -- 832},
publisher = {IEEE},
title = {{Learning to rank using privileged information}},
doi = {10.1109/ICCV.2013.107},
year = {2013},
}
@inproceedings{2294,
abstract = {In this work we propose a system for automatic classification of Drosophila embryos into developmental stages.
While the system is designed to solve an actual problem in biological research, we believe that the principle underly-
ing it is interesting not only for biologists, but also for researchers in computer vision. The main idea is to combine two orthogonal sources of information: one is a classifier trained on strongly invariant features, which makes it applicable to images of very different conditions, but also leads to rather noisy predictions. The other is a label propagation step based on a more powerful similarity measure that however is only consistent within specific subsets of the data at a time.
In our biological setup, the information sources are the shape and the staining patterns of embryo images. We show
experimentally that while neither of the methods can be used by itself to achieve satisfactory results, their combina-
tion achieves prediction quality comparable to human performance.},
author = {Kazmar, Tomas and Kvon, Evgeny and Stark, Alexander and Lampert, Christoph},
location = {Sydney, Australia},
publisher = {IEEE},
title = {{Drosophila Embryo Stage Annotation using Label Propagation}},
doi = {10.1109/ICCV.2013.139},
year = {2013},
}
@article{2300,
abstract = {We consider Ising models in two and three dimensions with nearest neighbor ferromagnetic interactions and long-range, power law decaying, antiferromagnetic interactions. If the strength of the ferromagnetic coupling J is larger than a critical value Jc, then the ground state is homogeneous and ferromagnetic. As the critical value is approached from smaller values of J, it is believed that the ground state consists of a periodic array of stripes (d=2) or slabs (d=3), all of the same size and alternating magnetization. Here we prove rigorously that the ground state energy per site converges to that of the optimal periodic striped or slabbed state, in the limit that J tends to the ferromagnetic transition point. While this theorem does not prove rigorously that the ground state is precisely striped or slabbed, it does prove that in any suitably large box the ground state is striped or slabbed with high probability.},
author = {Giuliani, Alessandro and Lieb, Élliott and Seiringer, Robert},
journal = {Physical Review B},
number = {6},
publisher = {American Physical Society},
title = {{Realization of stripes and slabs in two and three dimensions}},
doi = {10.1103/PhysRevB.88.064401},
volume = {88},
year = {2013},
}
@article{2297,
abstract = {We present an overview of mathematical results on the low temperature properties of dilute quantum gases, which have been obtained in the past few years. The presentation includes a discussion of Bose-Einstein condensation, the excitation spectrum for trapped gases and its relation to superfluidity, as well as the appearance of quantized vortices in rotating systems. All these properties are intensely being studied in current experiments on cold atomic gases. We will give a description of the mathematics involved in understanding these phenomena, starting from the underlying many-body Schrödinger equation.},
author = {Seiringer, Robert},
journal = {Japanese Journal of Mathematics},
number = {2},
pages = {185 -- 232},
publisher = {Springer},
title = {{Hot topics in cold gases: A mathematical physics perspective}},
doi = {10.1007/s11537-013-1264-5},
volume = {8},
year = {2013},
}
@inproceedings{2298,
abstract = {We present a shape analysis for programs that manipulate overlaid data structures which share sets of objects. The abstract domain contains Separation Logic formulas that (1) combine a per-object separating conjunction with a per-field separating conjunction and (2) constrain a set of variables interpreted as sets of objects. The definition of the abstract domain operators is based on a notion of homomorphism between formulas, viewed as graphs, used recently to define optimal decision procedures for fragments of the Separation Logic. Based on a Frame Rule that supports the two versions of the separating conjunction, the analysis is able to reason in a modular manner about non-overlaid data structures and then, compose information only at a few program points, e.g., procedure returns. We have implemented this analysis in a prototype tool and applied it on several interesting case studies that manipulate overlaid and nested linked lists.
},
author = {Dragoi, Cezara and Enea, Constantin and Sighireanu, Mihaela},
location = {Seattle, WA, United States},
pages = {150 -- 171},
publisher = {Springer},
title = {{Local shape analysis for overlaid data structures}},
doi = {10.1007/978-3-642-38856-9_10},
volume = {7935},
year = {2013},
}
@article{2299,
abstract = {The standard hardware design flow involves: (a) design of an integrated circuit using a hardware description language, (b) extensive functional and formal verification, and (c) logical synthesis. However, the above-mentioned processes consume significant effort and time. An alternative approach is to use a formal specification language as a high-level hardware description language and synthesize hardware from formal specifications. Our work is a case study of the synthesis of the widely and industrially used AMBA AHB protocol from formal specifications. Bloem et al. presented the first formal specifications for the AMBA AHB Arbiter and synthesized the AHB Arbiter circuit. However, in the first formal specification some important assumptions were missing. Our contributions are as follows: (a) We present detailed formal specifications for the AHB Arbiter incorporating the missing details, and obtain significant improvements in the synthesis results (both with respect to the number of gates in the synthesized circuit and with respect to the time taken to synthesize the circuit), and (b) we present formal specifications to generate compact circuits for the remaining two main components of AMBA AHB, namely, AHB Master and AHB Slave. Thus with systematic description we are able to automatically and completely synthesize an important and widely used industrial protocol.},
author = {Godhal, Yashdeep and Chatterjee, Krishnendu and Henzinger, Thomas A},
journal = {International Journal on Software Tools for Technology Transfer},
number = {5-6},
pages = {585 -- 601},
publisher = {Springer},
title = {{Synthesis of AMBA AHB from formal specification: A case study}},
doi = {10.1007/s10009-011-0207-9},
volume = {15},
year = {2013},
}
@article{2280,
abstract = {The problem of packing ellipsoids of different sizes and shapes into an ellipsoidal container so as to minimize a measure of overlap between ellipsoids is considered. A bilevel optimization formulation is given, together with an algorithm for the general case and a simpler algorithm for the special case in which all ellipsoids are in fact spheres. Convergence results are proved and computational experience is described and illustrated. The motivating application-chromosome organization in the human cell nucleus-is discussed briefly, and some illustrative results are presented.},
author = {Uhler, Caroline and Wright, Stephen},
journal = {SIAM Review},
number = {4},
pages = {671 -- 706},
publisher = {Society for Industrial and Applied Mathematics },
title = {{Packing ellipsoids with overlap}},
doi = {10.1137/120872309},
volume = {55},
year = {2013},
}
@article{2404,
abstract = {The Lieb-Thirring inequalities give a bound on the negative eigenvalues of a Schrödinger operator in terms of an Lp-norm of the potential. These are dual to bounds on the H1-norms of a system of orthonormal functions. Here we extend these bounds to analogous inequalities for perturbations of the Fermi sea of noninteracting particles (i.e., for perturbations of the continuous spectrum of the Laplacian by local potentials).},
author = {Frank, Rupert L and Lewin, Mathieu and Lieb, Élliott H and Robert Seiringer},
journal = {Duke Mathematical Journal},
number = {3},
pages = {435 -- 495},
publisher = {Duke University Press},
title = {{A positive density analogue of the Lieb-Thirring inequality}},
doi = {10.1215/00127094-2019477},
volume = {162},
year = {2013},
}
@article{2405,
abstract = {We consider the bipolaron in the Pekar-Tomasevich approximation and address the question whether the ground state is spherically symmetric or not. Numerical analysis has, so far, not completely settled the question. Our contribution is to prove rigorously that the ground state remains spherical for small values of the electron-electron Coulomb repulsion.},
author = {Frank, Rupert L and Lieb, Élliott H and Robert Seiringer},
journal = {Communications in Mathematical Physics},
number = {2},
pages = {557 -- 573},
publisher = {Springer},
title = {{Symmetry of bipolaron bound states for small Coulomb repulsion}},
doi = {10.1007/s00220-012-1604-y},
volume = {319},
year = {2013},
}
@article{2408,
abstract = {We investigate the low-energy excitation spectrum of a Bose gas confined in a trap, with weak long-range repulsive interactions. In particular, we prove that the spectrum can be described in terms of the eigenvalues of an effective one-particle operator, as predicted by the Bogoliubov approximation.},
author = {Grech, Philip and Robert Seiringer},
journal = {Communications in Mathematical Physics},
number = {2},
pages = {559 -- 591},
publisher = {Springer},
title = {{The excitation spectrum for weakly interacting Bosons in a trap}},
doi = {10.1007/s00220-013-1736-8},
volume = {322},
year = {2013},
}
@article{2410,
abstract = {Here, we describe a novel virulent bacteriophage that infects Bacillus weihenstephanensis, isolated from soil in Austria. It is the first phage to be discovered that infects this species. Here, we present the complete genome sequence of this podovirus. },
author = {Fernandes Redondo, Rodrigo A and Kupczok, Anne and Stift, Gertraud and Bollback, Jonathan P},
journal = {Genome Announcements},
number = {3},
publisher = {American Society for Microbiology},
title = {{Complete genome sequence of the novel phage MG-B1 infecting bacillus weihenstephanensis}},
doi = {10.1128/genomeA.00216-13},
volume = {1},
year = {2013},
}
@article{2412,
abstract = {Background: The CRISPR/Cas system is known to act as an adaptive and heritable immune system in Eubacteria and Archaea. Immunity is encoded in an array of spacer sequences. Each spacer can provide specific immunity to invasive elements that carry the same or a similar sequence. Even in closely related strains, spacer content is very dynamic and evolves quickly. Standard models of nucleotide evolutioncannot be applied to quantify its rate of change since processes other than single nucleotide changes determine its evolution.Methods We present probabilistic models that are specific for spacer content evolution. They account for the different processes of insertion and deletion. Insertions can be constrained to occur on one end only or are allowed to occur throughout the array. One deletion event can affect one spacer or a whole fragment of adjacent spacers. Parameters of the underlying models are estimated for a pair of arrays by maximum likelihood using explicit ancestor enumeration.Results Simulations show that parameters are well estimated on average under the models presented here. There is a bias in the rate estimation when including fragment deletions. The models also estimate times between pairs of strains. But with increasing time, spacer overlap goes to zero, and thus there is an upper bound on the distance that can be estimated. Spacer content similarities are displayed in a distance based phylogeny using the estimated times.We use the presented models to analyze different Yersinia pestis data sets and find that the results among them are largely congruent. The models also capture the variation in diversity of spacers among the data sets. A comparison of spacer-based phylogenies and Cas gene phylogenies shows that they resolve very different time scales for this data set.Conclusions The simulations and data analyses show that the presented models are useful for quantifying spacer content evolution and for displaying spacer content similarities of closely related strains in a phylogeny. This allows for comparisons of different CRISPR arrays or for comparisons between CRISPR arrays and nucleotide substitution rates.},
author = {Kupczok, Anne and Bollback, Jonathan P},
journal = {BMC Evolutionary Biology},
number = {1},
pages = {54 -- 54},
publisher = {BioMed Central},
title = {{Probabilistic models for CRISPR spacer content evolution }},
doi = {10.1186/1471-2148-13-54},
volume = {13},
year = {2013},
}
@inproceedings{2305,
abstract = {We study the complexity of central controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize both the expected mean-payoff performance of the system and its stability. e argue that the basic theoretical notion of expressing the stability in terms of the variance of the mean-payoff (called global variance in our paper) is not always sufficient, since it ignores possible instabilities on respective runs. For this reason we propose alernative definitions of stability, which we call local and hybrid variance, and which express how rewards on each run deviate from the run's own mean-payoff and from the expected mean-payoff, respectively. We show that a strategy ensuring both the expected mean-payoff and the variance below given bounds requires randomization and memory, under all the above semantics of variance. We then look at the problem of determining whether there is a such a strategy. For the global variance, we show that the problem is in PSPACE, and that the answer can be approximated in pseudo-polynomial time. For the hybrid variance, the analogous decision problem is in NP, and a polynomial-time approximating algorithm also exists. For local variance, we show that the decision problem is in NP. Since the overall performance can be traded for stability (and vice versa), we also present algorithms for approximating the associated Pareto curve in all the three cases. Finally, we study a special case of the decision problems, where we require a given expected mean-payoff together with zero variance. Here we show that the problems can be all solved in polynomial time.},
author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Forejt, Vojtěch and Kučera, Antonín},
booktitle = {28th Annual ACM/IEEE Symposium},
location = {New Orleans, LA, United States},
pages = {331 -- 340},
publisher = {IEEE},
title = {{Trading performance for stability in Markov decision processes}},
doi = {10.1109/LICS.2013.39},
year = {2013},
}
@book{2306,
abstract = {Das Buch ist sowohl eine Einführung in die Themen Linked Data, Open Data und Open Linked Data als es auch den konkreten Bezug auf Bibliotheken behandelt. Hierzu werden konkrete Anwendungsprojekte beschrieben. Der Band wendet sich dabei sowohl an Personen aus der Bibliothekspraxis als auch an Personen aus dem Bibliotheksmanagement, die noch nicht mit dem Thema vertraut sind.},
author = {Danowski, Patrick and Pohl, Adrian},
publisher = {De Gruyter},
title = {{(Open) Linked Data in Bibliotheken}},
doi = {10.1515/9783110278736},
volume = {50},
year = {2013},
}
@inproceedings{2315,
abstract = { We study the effects of random scatterers on the ground state of the one-dimensional Lieb-Liniger model of interacting bosons on the unit interval in the Gross-Pitaevskii regime. We prove that Bose Einstein condensation survives even a strong random potential with a high density of scatterers. The character of the wave function of the condensate, however, depends in an essential way on the interplay between randomness and the strength of the two-body interaction. For low density of scatterers or strong interactions the wave function extends over the whole interval. High density of scatterers and weak interaction, on the other hand, leads to localization of the wave function in a fragmented subset of the interval. },
author = {Seiringer, Robert and Yngvason, Jakob and Zagrebnov, Valentin},
pages = {610--619},
publisher = {World Scientific Publishing},
title = {{Disordered Bose-Einstein condensates with interaction}},
doi = {10.1142/9789814449243_0063},
year = {2013},
}
@inproceedings{2319,
abstract = {In a recent paper [7] we give the first rigorous derivation of the celebrated Ginzburg-Landau (GL)theory, starting from the microscopic Bardeen- Cooper-Schrieffer (BCS)model. Here we present our results in the simplified case of a one-dimensional system of particles interacting via a δ-potential.},
author = {Frank, Rupert L and Hainzl, Christian and Robert Seiringer and Solovej, Jan P},
pages = {57 -- 88},
publisher = {Springer},
title = {{ Derivation of Ginzburg-Landau theory for a one-dimensional system with contact interaction}},
doi = {10.1007/978-3-0348-0531-5_3},
year = {2013},
}
@inproceedings{2444,
abstract = {We consider two core algorithmic problems for probabilistic verification: the maximal end-component decomposition and the almost-sure reachability set computation for Markov decision processes (MDPs). For MDPs with treewidth k, we present two improved static algorithms for both the problems that run in time O(n·k 2.38·2k ) and O(m·logn· k), respectively, where n is the number of states and m is the number of edges, significantly improving the previous known O(n·k·√n· k) bound for low treewidth. We also present decremental algorithms for both problems for MDPs with constant treewidth that run in amortized logarithmic time, which is a huge improvement over the previously known algorithms that require amortized linear time.},
author = {Chatterjee, Krishnendu and Ła̧Cki, Jakub},
location = {St. Petersburg, Russia},
pages = {543 -- 558},
publisher = {Springer},
title = {{Faster algorithms for Markov decision processes with low treewidth}},
doi = {10.1007/978-3-642-39799-8_36},
volume = {8044},
year = {2013},
}
@inproceedings{2328,
abstract = {Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on identifying the so-called linearization points. Regrettably, such proofs, whether manual or automatic, are often complicated and scale poorly to advanced non-blocking concurrency patterns, such as helping and optimistic updates.
In response, we propose a more modular way of checking linearizability of concurrent queue algorithms that does not involve identifying linearization points. We reduce the task of proving linearizability with respect to the queue specification to establishing four basic properties, each of which can be proved independently by simpler arguments. As a demonstration of our approach, we verify the Herlihy and Wing queue, an algorithm that is challenging to verify by a simulation proof.},
author = {Henzinger, Thomas A and Sezgin, Ali and Vafeiadis, Viktor},
location = {Buenos Aires, Argentina},
pages = {242 -- 256},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Aspect-oriented linearizability proofs}},
doi = {10.1007/978-3-642-40184-8_18},
volume = {8052},
year = {2013},
}
@inproceedings{2445,
abstract = {We develop program synthesis techniques that can help programmers fix concurrency-related bugs. We make two new contributions to synthesis for concurrency, the first improving the efficiency of the synthesized code, and the second improving the efficiency of the synthesis procedure itself. The first contribution is to have the synthesis procedure explore a variety of (sequential) semantics-preserving program transformations. Classically, only one such transformation has been considered, namely, the insertion of synchronization primitives (such as locks). Based on common manual bug-fixing techniques used by Linux device-driver developers, we explore additional, more efficient transformations, such as the reordering of independent instructions. The second contribution is to speed up the counterexample-guided removal of concurrency bugs within the synthesis procedure by considering partial-order traces (instead of linear traces) as counterexamples. A partial-order error trace represents a set of linear (interleaved) traces of a concurrent program all of which lead to the same error. By eliminating a partial-order error trace, we eliminate in a single iteration of the synthesis procedure all linearizations of the partial-order trace. We evaluated our techniques on several simplified examples of real concurrency bugs that occurred in Linux device drivers.},
author = {Cerny, Pavol and Henzinger, Thomas A and Radhakrishna, Arjun and Ryzhyk, Leonid and Tarrach, Thorsten},
location = {St. Petersburg, Russia},
pages = {951 -- 967},
publisher = {Springer},
title = {{Efficient synthesis for concurrency by semantics-preserving transformations}},
doi = {10.1007/978-3-642-39799-8_68},
volume = {8044},
year = {2013},
}
@inproceedings{2446,
abstract = {The model-checking problem for probabilistic systems crucially relies on the translation of LTL to deterministic Rabin automata (DRW). Our recent Safraless translation [KE12, GKE12] for the LTL(F,G) fragment produces smaller automata as compared to the traditional approach. In this work, instead of DRW we consider deterministic automata with acceptance condition given as disjunction of generalized Rabin pairs (DGRW). The Safraless translation of LTL(F,G) formulas to DGRW results in smaller automata as compared to DRW. We present algorithms for probabilistic model-checking as well as game solving for DGRW conditions. Our new algorithms lead to improvement both in terms of theoretical bounds as well as practical evaluation. We compare PRISM with and without our new translation, and show that the new translation leads to significant improvements.},
author = {Chatterjee, Krishnendu and Gaiser, Andreas and Kretinsky, Jan},
location = {St. Petersburg, Russia},
pages = {559 -- 575},
publisher = {Springer},
title = {{Automata with generalized Rabin pairs for probabilistic model checking and LTL synthesis}},
doi = {10.1007/978-3-642-39799-8_37},
volume = {8044},
year = {2013},
}
@inproceedings{2447,
abstract = {Separation logic (SL) has gained widespread popularity because of its ability to succinctly express complex invariants of a program’s heap configurations. Several specialized provers have been developed for decidable SL fragments. However, these provers cannot be easily extended or combined with solvers for other theories that are important in program verification, e.g., linear arithmetic. In this paper, we present a reduction of decidable SL fragments to a decidable first-order theory that fits well into the satisfiability modulo theories (SMT) framework. We show how to use this reduction to automate satisfiability, entailment, frame inference, and abduction problems for separation logic using SMT solvers. Our approach provides a simple method of integrating separation logic into existing verification tools that provide SMT backends, and an elegant way of combining SL fragments with other decidable first-order theories. We implemented this approach in a verification tool and applied it to heap-manipulating programs whose verification involves reasoning in theory combinations.
},
author = {Piskac, Ruzica and Wies, Thomas and Zufferey, Damien},
location = {St. Petersburg, Russia},
pages = {773 -- 789},
publisher = {Springer},
title = {{Automating separation logic using SMT}},
doi = {10.1007/978-3-642-39799-8_54},
volume = {8044},
year = {2013},
}
@article{2448,
abstract = {Cell-to-cell directional flow of the phytohormone auxin is primarily established by polar localization of the PIN auxin transporters, a process tightly regulated at multiple levels by auxin itself. We recently reported that, in the context of strong auxin flows, activity of the vacuolar ZIFL1.1 transporter is required for fine-tuning of polar auxin transport rates in the Arabidopsis root. In particular, ZIFL1.1 function protects plasma-membrane stability of the PIN2 carrier in epidermal root tip cells under conditions normally triggering PIN2 degradation. Here, we show that ZIFL1.1 activity at the root tip also promotes PIN1 plasma-membrane abundance in central cylinder cells, thus supporting the notion that ZIFL1.1 acts as a general positive modulator of polar auxin transport in roots.},
author = {Remy, Estelle and Baster, Pawel and Friml, Jirí and Duque, Paula},
journal = {Plant Signaling & Behavior},
number = {10},
publisher = {Landes Bioscience},
title = {{ZIFL1.1 transporter modulates polar auxin transport by stabilizing membrane abundance of multiple PINs in Arabidopsis root tip}},
doi = {10.4161/psb.25688},
volume = {8},
year = {2013},
}
@article{245,
abstract = {For given non-zero integers a, b, q we investigate the density of solutions (x; y) ∈ ℤ2 to the binary cubic congruence ax2 + by3 ≡ 0 mod q, and use it to establish the Manin conjecture for a singular del Pezzo surface of degree 2 defined over ℚ.},
author = {Baier, Stephan and Timothy Browning},
journal = {Journal fur die Reine und Angewandte Mathematik},
number = {680},
pages = {69 -- 151},
publisher = {Walter de Gruyter},
title = {{Inhomogeneous cubic congruences and rational points on del Pezzo surfaces}},
doi = {10.1515/crelle.2012.039},
year = {2013},
}
@article{2466,
abstract = {We introduce a new method for efficiently simulating liquid with extreme amounts of spatial adaptivity. Our method combines several key components to drastically speed up the simulation of large-scale fluid phenomena: We leverage an alternative Eulerian tetrahedral mesh discretization to significantly reduce the complexity of the pressure solve while increasing the robustness with respect to element quality and removing the possibility of locking. Next, we enable subtle free-surface phenomena by deriving novel second-order boundary conditions consistent with our discretization. We couple this discretization with a spatially adaptive Fluid-Implicit Particle (FLIP) method, enabling efficient, robust, minimally-dissipative simulations that can undergo sharp changes in spatial resolution while minimizing artifacts. Along the way, we provide a new method for generating a smooth and detailed surface from a set of particles with variable sizes. Finally, we explore several new sizing functions for determining spatially adaptive simulation resolutions, and we show how to couple them to our simulator. We combine each of these elements to produce a simulation algorithm that is capable of creating animations at high maximum resolutions while avoiding common pitfalls like inaccurate boundary conditions and inefficient computation.},
author = {Ando, Ryoichi and Thuerey, Nils and Wojtan, Christopher J},
journal = {ACM Transactions on Graphics},
number = {4},
publisher = {ACM},
title = {{Highly adaptive liquid simulations on tetrahedral meshes}},
doi = {10.1145/2461912.2461982},
volume = {32},
year = {2013},
}
@article{2467,
abstract = {This paper presents a method for computing topology changes for triangle meshes in an interactive geometric modeling environment. Most triangle meshes in practice do not exhibit desirable geometric properties, so we develop a solution that is independent of standard assumptions and robust to geometric errors. Specifically, we provide the first method for topology change applicable to arbitrary non-solid, non-manifold, non-closed, self-intersecting surfaces. We prove that this new method for topology change produces the expected conventional results when applied to solid (closed, manifold, non-self-intersecting) surfaces---that is, we prove a backwards-compatibility property relative to prior work. Beyond solid surfaces, we present empirical evidence that our method remains tolerant to a variety of surface aberrations through the incorporation of a novel error correction scheme. Finally, we demonstrate how topology change applied to non-solid objects enables wholly new and useful behaviors.},
author = {Bernstein, Gilbert and Wojtan, Christopher J},
journal = {ACM Transactions on Graphics},
number = {4},
publisher = {ACM},
title = {{Putting holes in holey geometry: Topology change for arbitrary surfaces}},
doi = {10.1145/2461912.2462027},
volume = {32},
year = {2013},
}
@article{2468,
abstract = {Our work concerns the combination of an Eulerian liquid simulation with a high-resolution surface tracker (e.g. the level set method or a Lagrangian triangle mesh). The naive application of a high-resolution surface tracker to a low-resolution velocity field can produce many visually disturbing physical and topological artifacts that limit their use in practice. We address these problems by defining an error function which compares the current state of the surface tracker to the set of physically valid surface states. By reducing this error with a gradient descent technique, we introduce a novel physics-based surface fairing method. Similarly, by treating this error function as a potential energy, we derive a new surface correction force that mimics the vortex sheet equations. We demonstrate our results with both level set and mesh-based surface trackers.},
author = {Bojsen-Hansen, Morten and Wojtan, Christopher J},
journal = {ACM Transactions on Graphics},
number = {4},
publisher = {ACM},
title = {{Liquid surface tracking with error compensation}},
doi = {10.1145/2461912.2461991},
volume = {32},
year = {2013},
}
@article{2469,
abstract = {Cadherins are transmembrane proteins that mediate cell–cell adhesion in animals. By regulating contact formation and stability, cadherins play a crucial role in tissue morphogenesis and homeostasis. Here, we review the three major unctions of cadherins in cell–cell contact formation and stability. Two of those functions lead to a decrease in interfacial ension at the forming cell–cell contact, thereby promoting contact expansion — first, by providing adhesion tension that lowers interfacial tension at the cell–cell contact, and second, by signaling to the actomyosin cytoskeleton in order to reduce cortex tension and thus interfacial tension at the contact. The third function of cadherins in cell–cell contact formation is to stabilize the contact by resisting mechanical forces that pull on the contact.},
author = {Maître, Jean-Léon and Heisenberg, Carl-Philipp J},
journal = {Current Biology},
number = {14},
pages = {R626 -- R633},
publisher = {Cell Press},
title = {{Three functions of cadherins in cell adhesion}},
doi = {10.1016/j.cub.2013.06.019},
volume = {23},
year = {2013},
}
@article{2470,
abstract = {Background:Auxin binding protein 1 (ABP1) is a putative auxin receptor and its function is indispensable for plant growth and development. ABP1 has been shown to be involved in auxin-dependent regulation of cell division and expansion, in plasma-membrane-related processes such as changes in transmembrane potential, and in the regulation of clathrin-dependent endocytosis. However, the ABP1-regulated downstream pathway remains elusive.Methodology/Principal Findings:Using auxin transport assays and quantitative analysis of cellular morphology we show that ABP1 regulates auxin efflux from tobacco BY-2 cells. The overexpression of ABP1can counterbalance increased auxin efflux and auxin starvation phenotypes caused by the overexpression of PIN auxin efflux carrier. Relevant mechanism involves the ABP1-controlled vesicle trafficking processes, including positive regulation of endocytosis of PIN auxin efflux carriers, as indicated by fluorescence recovery after photobleaching (FRAP) and pharmacological manipulations.Conclusions/Significance:The findings indicate the involvement of ABP1 in control of rate of auxin transport across plasma membrane emphasizing the role of ABP1 in regulation of PIN activity at the plasma membrane, and highlighting the relevance of ABP1 for the formation of developmentally important, PIN-dependent auxin gradients.},
author = {Čovanová, Milada and Sauer, Michael and Rychtář, Jan and Friml, Jirí and Petrášek, Jan and Zažímalová, Eva},
journal = {PLoS One},
number = {7},
publisher = {Public Library of Science},
title = {{Overexpression of the auxin binding PROTEIN1 modulates PIN-dependent auxin transport in tobacco cells}},
doi = {10.1371/journal.pone.0070050},
volume = {8},
year = {2013},
}
@article{2471,
abstract = {The impact of disulfide bonds on protein stability goes beyond simple equilibrium thermodynamics effects associated with the conformational entropy of the unfolded state. Indeed, disulfide crosslinks may play a role in the prevention of dysfunctional association and strongly affect the rates of irreversible enzyme inactivation, highly relevant in biotechnological applications. While these kinetic-stability effects remain poorly understood, by analogy with proposed mechanisms for processes of protein aggregation and fibrillogenesis, we propose that they may be determined by the properties of sparsely-populated, partially-unfolded intermediates. Here we report the successful design, on the basis of high temperature molecular-dynamics simulations, of six thermodynamically and kinetically stabilized variants of phytase from Citrobacter braakii (a biotechnologically important enzyme) with one, two or three engineered disulfides. Activity measurements and 3D crystal structure determination demonstrate that the engineered crosslinks do not cause dramatic alterations in the native structure. The inactivation kinetics for all the variants displays a strongly non-Arrhenius temperature dependence, with the time-scale for the irreversible denaturation process reaching a minimum at a given temperature within the range of the denaturation transition. We show this striking feature to be a signature of a key role played by a partially unfolded, intermediate state/ensemble. Energetic and mutational analyses confirm that the intermediate is highly unfolded (akin to a proposed critical intermediate in the misfolding of the prion protein), a result that explains the observed kinetic stabilization. Our results provide a rationale for the kinetic-stability consequences of disulfide-crosslink engineering and an experimental methodology to arrive at energetic/structural descriptions of the sparsely populated and elusive intermediates that play key roles in irreversible protein denaturation.},
author = {Sanchez Romero, Inmaculada and Ariza, Antonio and Wilson, Keith and Skjøt, Michael and Vind, Jesper and De Maria, Leonardo and Skov, Lars and Sánchez Ruiz, Jose},
journal = {PLoS One},
number = {7},
publisher = {Public Library of Science},
title = {{Mechanism of protein kinetic stabilization by engineered disulfide crosslinks}},
doi = {10.1371/journal.pone.0070013},
volume = {8},
year = {2013},
}
@article{2472,
abstract = {Plant-specific PIN-formed (PIN) efflux transporters for the plant hormone auxin are required for tissue-specific directional auxin transport and cellular auxin homeostasis. The Arabidopsis PIN protein family has been shown to play important roles in developmental processes such as embryogenesis, organogenesis, vascular tissue differentiation, root meristem patterning and tropic growth. Here we analyzed roles of the less characterised Arabidopsis PIN6 auxin transporter. PIN6 is auxin-inducible and is expressed during multiple auxin-regulated developmental processes. Loss of pin6 function interfered with primary root growth and lateral root development. Misexpression of PIN6 affected auxin transport and interfered with auxin homeostasis in other growth processes such as shoot apical dominance, lateral root primordia development, adventitious root formation, root hair outgrowth and root waving. These changes in auxin-regulated growth correlated with a reduction in total auxin transport as well as with an altered activity of DR5-GUS auxin response reporter. Overall, the data indicate that PIN6 regulates auxin homeostasis during plant development.},
author = {Cazzonelli, Christopher and Vanstraelen, Marleen and Simon, Sibu and Yin, Kuide and Carron Arthur, Ashley and Nisar, Nazia and Tarle, Gauri and Cuttriss, Abby and Searle, Iain and Benková, Eva and Mathesius, Ulrike and Masle, Josette and Friml, Jirí and Pogson, Barry},
journal = {PLoS One},
number = {7},
publisher = {Public Library of Science},
title = {{Role of the Arabidopsis PIN6 auxin transporter in auxin homeostasis and auxin-mediated development}},
doi = {10.1371/journal.pone.0070069},
volume = {8},
year = {2013},
}
@article{2473,
abstract = {When a mutation with selective advantage s spreads through a panmictic population, it may cause two lineages at a linked locus to coalesce; the probability of coalescence is exp(−2rT), where T∼log(2Ns)/s is the time to fixation, N is the number of haploid individuals, and r is the recombination rate. Population structure delays fixation, and so weakens the effect of a selective sweep. However, favourable alleles spread through a spatially continuous population behind a narrow wavefront; ancestral lineages are confined at the tip of this front, and so coalesce rapidly. In extremely dense populations, coalescence is dominated by rare fluctuations ahead of the front. However, we show that for moderate densities, a simple quasi-deterministic approximation applies: the rate of coalescence within the front is λ∼2g(η)/(ρℓ), where ρ is the population density and is the characteristic scale of the wavefront; g(η) depends only on the strength of random drift, . The net effect of a sweep on coalescence also depends crucially on whether two lineages are ever both within the wavefront at the same time: even in the extreme case when coalescence within the front is instantaneous, the net rate of coalescence may be lower than in a single panmictic population. Sweeps can also have a substantial impact on the rate of gene flow. A single lineage will jump to a new location when it is hit by a sweep, with mean square displacement ; this can be substantial if the species’ range, L, is large, even if the species-wide rate of sweeps per map length, Λ/R, is small. This effect is half as strong in two dimensions. In contrast, the rate of coalescence between lineages, at random locations in space and on the genetic map, is proportional to (c/L)(Λ/R), where c is the wavespeed: thus, on average, one-dimensional structure is likely to reduce coalescence due to sweeps, relative to panmixis. In two dimensions, genes must move along the front before they can coalesce; this process is rapid, being dominated by rare fluctuations. This leads to a dramatically higher rate of coalescence within the wavefront than if lineages simply diffused along the front. Nevertheless, the net rate of coalescence due to a sweep through a two-dimensional population is likely to be lower than it would be with panmixis.},
author = {Barton, Nicholas H and Etheridge, Alison and Kelleher, Jerome and Véber, Amandine},
journal = {Theoretical Population Biology},
number = {8},
pages = {75 -- 89},
publisher = {Elsevier},
title = {{Genetic hitch-hiking in spatially extended populations}},
doi = {10.1016/j.tpb.2012.12.001},
volume = {87},
year = {2013},
}
@article{250,
abstract = {Châtelet surfaces provide a rich source of geometrically rational surfaces that do not always satisfy the Hasse principle. Restricting attention to a special class of Châtelet surfaces, we investigate the frequency that such counter-examples arise over the rational numbers.},
author = {de la Bretèche, Régis and Timothy Browning},
journal = {Proceedings of the London Mathematical Society},
number = {4},
pages = {1030 -- 1078},
publisher = {Oxford University Press},
title = {{Density of Châtelet surfaces failing the Hasse principle}},
doi = {10.1112/plms/pdt060},
volume = {108},
year = {2013},
}
@inproceedings{2517,
abstract = {Traditional formal methods are based on a Boolean satisfaction notion: a reactive system satisfies, or not, a given specification. We generalize formal methods to also address the quality of systems. As an adequate specification formalism we introduce the linear temporal logic LTL[F]. The satisfaction value of an LTL[F] formula is a number between 0 and 1, describing the quality of the satisfaction. The logic generalizes traditional LTL by augmenting it with a (parameterized) set F of arbitrary functions over the interval [0,1]. For example, F may contain the maximum or minimum between the satisfaction values of subformulas, their product, and their average. The classical decision problems in formal methods, such as satisfiability, model checking, and synthesis, are generalized to search and optimization problems in the quantitative setting. For example, model checking asks for the quality in which a specification is satisfied, and synthesis returns a system satisfying the specification with the highest quality. Reasoning about quality gives rise to other natural questions, like the distance between specifications. We formalize these basic questions and study them for LTL[F]. By extending the automata-theoretic approach for LTL to a setting that takes quality into an account, we are able to solve the above problems and show that reasoning about LTL[F] has roughly the same complexity as reasoning about traditional LTL.},
author = {Almagor, Shaull and Boker, Udi and Kupferman, Orna},
location = {Riga, Latvia},
number = {Part 2},
pages = {15 -- 27},
publisher = {Springer},
title = {{Formalizing and reasoning about quality}},
doi = {10.1007/978-3-642-39212-2_3},
volume = {7966},
year = {2013},
}
@inproceedings{2518,
abstract = {A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the problem is specified by a sum of cost functions from the language with the goal to minimise the sum. We study which classes of finite-valued languages can be solved exactly by the basic linear programming relaxation (BLP). Thapper and Živný showed [20] that if BLP solves the language then the language admits a binary commutative fractional polymorphism. We prove that the converse is also true. This leads to a necessary and a sufficient condition which can be checked in polynomial time for a given language. In contrast, the previous necessary and sufficient condition due to [20] involved infinitely many inequalities. More recently, Thapper and Živný [21] showed (using, in particular, a technique introduced in this paper) that core languages that do not satisfy our condition are NP-hard. Taken together, these results imply that a finite-valued language can either be solved using Linear Programming or is NP-hard.},
author = {Kolmogorov, Vladimir},
location = {Riga, Latvia},
number = {1},
pages = {625 -- 636},
publisher = {Springer},
title = {{The power of linear programming for finite-valued CSPs: A constructive characterization}},
doi = {10.1007/978-3-642-39206-1_53},
volume = {7965},
year = {2013},
}
@inproceedings{2520,
abstract = {We propose a probabilistic model to infer supervised latent variables in
the Hamming space from observed data. Our model allows simultaneous
inference of the number of binary latent variables, and their values. The
latent variables preserve neighbourhood structure of the data in a sense
that objects in the same semantic concept have similar latent values, and
objects in different concepts have dissimilar latent values. We formulate
the supervised infinite latent variable problem based on an intuitive
principle of pulling objects together if they are of the same type, and
pushing them apart if they are not. We then combine this principle with a
flexible Indian Buffet Process prior on the latent variables. We show that
the inferred supervised latent variables can be directly used to perform a
nearest neighbour search for the purpose of retrieval. We introduce a new
application of dynamically extending hash codes, and show how to
effectively couple the structure of the hash codes with continuously
growing structure of the neighbourhood preserving infinite latent feature
space.},
author = {Quadrianto, Novi and Sharmanska, Viktoriia and Knowles, David and Ghahramani, Zoubin},
booktitle = {Proceedings of the 29th conference uncertainty in Artificial Intelligence},
isbn = {9780974903996},
location = {Bellevue, WA, United States},
pages = {527 -- 536},
publisher = {AUAI Press},
title = {{The supervised IBP: Neighbourhood preserving infinite latent feature models}},
year = {2013},
}
@inproceedings{2718,
abstract = {Even though both population and quantitative genetics, and evolutionary computation, deal with the same questions, they have developed largely independently of each other. I review key results from each field, emphasising those that apply independently of the (usually unknown) relation between genotype and phenotype. The infinitesimal model provides a simple framework for predicting the response of complex traits to selection, which in biology has proved remarkably successful. This allows one to choose the schedule of population sizes and selection intensities that will maximise the response to selection, given that the total number of individuals realised, C = ∑t Nt, is constrained. This argument shows that for an additive trait (i.e., determined by the sum of effects of the genes), the optimum population size and the maximum possible response (i.e., the total change in trait mean) are both proportional to √C.},
author = {Barton, Nicholas H and Paixao, Tiago},
booktitle = {Proceedings of the 15th annual conference on Genetic and evolutionary computation},
location = {Amsterdam, Netherlands},
pages = {1573 -- 1580},
publisher = {ACM},
title = {{Can quantitative and population genetics help us understand evolutionary computation?}},
doi = {10.1145/2463372.2463568},
year = {2013},
}
@article{2720,
abstract = {Knowledge of the rate and fitness effects of mutations is essential for understanding the process of evolution. Mutations are inherently difficult to study because they are rare and are frequently eliminated by natural selection. In the ciliate Tetrahymena thermophila, mutations can accumulate in the germline genome without being exposed to selection. We have conducted a mutation accumulation (MA) experiment in this species. Assuming that all mutations are deleterious and have the same effect, we estimate that the deleterious mutation rate per haploid germline genome per generation is U = 0.0047 (95% credible interval: 0.0015, 0.0125), and that germline mutations decrease fitness by s = 11% when expressed in a homozygous state (95% CI: 4.4%, 27%). We also estimate that deleterious mutations are partially recessive on average (h = 0.26; 95% CI: –0.022, 0.62) and that the rate of lethal mutations is <10% of the deleterious mutation rate. Comparisons between the observed evolutionary responses in the germline and somatic genomes and the results from individual-based simulations of MA suggest that the two genomes have similar mutational parameters. These are the first estimates of the deleterious mutation rate and fitness effects from the eukaryotic supergroup Chromalveolata and are within the range of those of other eukaryotes.},
author = {Long, Hongan and Paixao, Tiago and Azevedo, Ricardo and Zufall, Rebecca},
journal = {Genetics},
number = {2},
pages = {527--540},
publisher = {Genetics Society of America},
title = {{Accumulation of spontaneous mutations in the ciliate Tetrahymena thermophila}},
doi = {10.1534/genetics.113.153536},
volume = {195},
year = {2013},
}
@article{2697,
abstract = {We consider Hermitian and symmetric random band matrices H = (h xy ) in d⩾1 d ⩾ 1 dimensions. The matrix entries h xy , indexed by x,y∈(Z/LZ)d x , y ∈ ( Z / L Z ) d , are independent, centred random variables with variances sxy=E|hxy|2 s x y = E | h x y | 2 . We assume that s xy is negligible if |x − y| exceeds the band width W. In one dimension we prove that the eigenvectors of H are delocalized if W≫L4/5 W ≫ L 4 / 5 . We also show that the magnitude of the matrix entries |Gxy|2 | G x y | 2 of the resolvent G=G(z)=(H−z)−1 G = G ( z ) = ( H - z ) - 1 is self-averaging and we compute E|Gxy|2 E | G x y | 2 . We show that, as L→∞ L → ∞ and W≫L4/5 W ≫ L 4 / 5 , the behaviour of E|Gxy|2 E | G x y | 2 is governed by a diffusion operator whose diffusion constant we compute. Similar results are obtained in higher dimensions.},
author = {László Erdös and Knowles, Antti and Yau, Horng-Tzer and Yin, Jun},
journal = {Communications in Mathematical Physics},
number = {1},
pages = {367 -- 416},
publisher = {Springer},
title = {{Delocalization and diffusion profile for random band matrices}},
doi = {10.1007/s00220-013-1773-3},
volume = {323},
year = {2013},
}
@article{2698,
abstract = {We consider non-interacting particles subject to a fixed external potential V and a self-generated magnetic field B. The total energy includes the field energy β∫B2 and we minimize over all particle states and magnetic fields. In the case of spin-1/2 particles this minimization leads to the coupled Maxwell-Pauli system. The parameter β tunes the coupling strength between the field and the particles and it effectively determines the strength of the field. We investigate the stability and the semiclassical asymptotics, h→0, of the total ground state energy E(β,h,V). The relevant parameter measuring the field strength in the semiclassical limit is κ=βh. We are not able to give the exact leading order semiclassical asymptotics uniformly in κ or even for fixed κ. We do however give upper and lower bounds on E with almost matching dependence on κ. In the simultaneous limit h→0 and κ→∞ we show that the standard non-magnetic Weyl asymptotics holds. The same result also holds for the spinless case, i.e. where the Pauli operator is replaced by the Schrödinger operator.},
author = {Erdös, László and Fournais, Søren and Solovej, Jan},
journal = {Journal of the European Mathematical Society},
number = {6},
pages = {2093 -- 2113},
publisher = {European Mathematical Society},
title = {{Stability and semiclassics in self-generated fields}},
doi = {10.4171/JEMS/416},
volume = {15},
year = {2013},
}
@article{2780,
abstract = {We consider a general class of random matrices whose entries are centred random variables, independent up to a symmetry constraint. We establish precise high-probability bounds on the averages of arbitrary monomials in the resolvent matrix entries. Our results generalize the previous results of Erdős et al. (Ann Probab, arXiv:1103.1919, 2013; Commun Math Phys, arXiv:1103.3869, 2013; J Combin 1(2):15-85, 2011) which constituted a key step in the proof of the local semicircle law with optimal error bound in mean-field random matrix models. Our bounds apply to random band matrices and improve previous estimates from order 2 to order 4 in the cases relevant to applications. In particular, they lead to a proof of the diffusion approximation for the magnitude of the resolvent of random band matrices. This, in turn, implies new delocalization bounds on the eigenvectors. The applications are presented in a separate paper (Erdős et al., arXiv:1205.5669, 2013).},
author = {László Erdös and Knowles, Antti and Yau, Horng-Tzer},
journal = {Annales Henri Poincare},
number = {8},
pages = {1837 -- 1926},
publisher = {Birkhäuser},
title = {{Averaging fluctuations in resolvents of random band matrices}},
doi = {10.1007/s00023-013-0235-y},
volume = {14},
year = {2013},
}
@article{2781,
abstract = {We consider the ensemble of adjacency matrices of Erdős-Rényi random graphs, that is, graphs on N vertices where every edge is chosen independently and with probability p = p(N). We rescale the matrix so that its bulk eigenvalues are of order one. We prove that, as long as pN→∞(with a speed at least logarithmic in N), the density of eigenvalues of the Erdős-Rényi ensemble is given by the Wigner semicircle law for spectral windows of length larger than N-1 (up to logarithmic corrections). As a consequence, all eigenvectors are proved to be completely delocalized in the sense that the ℓ∞-norms of the ℓ2-normalized eigenvectors are at most of order N-1/2 with a very high probability. The estimates in this paper will be used in the companion paper [Spectral statistics of Erdős-Rényi graphs II: Eigenvalue spacing and the extreme eigenvalues (2011) Preprint] to prove the universality of eigenvalue distributions both in the bulk and at the spectral edges under the further restriction that pN »N2/3.},
author = {László Erdös and Knowles, Antti and Yau, Horng-Tzer and Yin, Jun},
journal = {Annals of Probability},
number = {3 B},
pages = {2279 -- 2375},
publisher = {Institute of Mathematical Statistics},
title = {{Spectral statistics of Erdős-Rényi graphs I: Local semicircle law}},
doi = {10.1214/11-AOP734},
volume = {41},
year = {2013},
}
@article{2782,
abstract = {We consider random n×n matrices of the form (XX*+YY*)^{-1/2}YY*(XX*+YY*)^{-1/2}, where X and Y have independent entries with zero mean and variance one. These matrices are the natural generalization of the Gaussian case, which are known as MANOVA matrices and which have joint eigenvalue density given by the third classical ensemble, the Jacobi ensemble. We show that, away from the spectral edge, the eigenvalue density converges to the limiting density of the Jacobi ensemble even on the shortest possible scales of order 1/n (up to log n factors). This result is the analogue of the local Wigner semicircle law and the local Marchenko-Pastur law for general MANOVA matrices.},
author = {Erdös, László and Farrell, Brendan},
journal = {Journal of Statistical Physics},
number = {6},
pages = {1003 -- 1032},
publisher = {Springer},
title = {{Local eigenvalue density for general MANOVA matrices}},
doi = {10.1007/s10955-013-0807-8},
volume = {152},
year = {2013},
}
@inproceedings{2807,
abstract = {We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity. The extension problem asks, given topological spaces X; Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that X and Y are represented as finite simplicial complexes, A is a subcomplex of X, and f is given as a simplicial map. In this generality the problem is undecidable, as follows from Novikov's result from the 1950s on uncomputability of the fundamental group π1(Y ). We thus study the problem under the assumption that, for some k ≥ 2, Y is (k - 1)-connected; informally, this means that Y has \no holes up to dimension k-1" (a basic example of such a Y is the sphere Sk). We prove that, on the one hand, this problem is still undecidable for dimX = 2k. On the other hand, for every fixed k ≥ 2, we obtain an algorithm that solves the extension problem in polynomial time assuming Y (k - 1)-connected and dimX ≤ 2k - 1. For dimX ≤ 2k - 2, the algorithm also provides a classification of all extensions up to homotopy (continuous deformation). This relies on results of our SODA 2012 paper, and the main new ingredient is a machinery of objects with polynomial-time homology, which is a polynomial-time analog of objects with effective homology developed earlier by Sergeraert et al. We also consider the computation of the higher homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, Anick proved in 1989 that computing πk(Y ) is #P-hard if k is a part of input, where Y is a cell complex with certain rather compact encoding. We strengthen his result to #P-hardness for Y given as a simplicial complex. },
author = {Čadek, Martin and Krcál, Marek and Matoušek, Jiří and Vokřínek, Lukáš and Wagner, Uli},
booktitle = {45th Annual ACM Symposium on theory of computing},
location = {Palo Alto, CA, United States},
pages = {595 -- 604},
publisher = {ACM},
title = {{Extending continuous maps: Polynomiality and undecidability}},
doi = {10.1145/2488608.2488683},
year = {2013},
}
@article{2808,
abstract = {In order to establish a reference for analysis of the function of auxin and the auxin biosynthesis regulators SHORT INTERNODE/ STYLISH (SHI/STY) during Physcomitrella patens reproductive development, we have described male (antheridial) and female (archegonial) development in detail, including temporal and positional information of organ initiation. This has allowed us to define discrete stages of organ morphogenesis and to show that reproductive organ development in P. patens is highly organized and that organ phyllotaxis differs between vegetative and reproductive development. Using the PpSHI1 and PpSHI2 reporter and knockout lines, the auxin reporters GmGH3pro:GUS and PpPINApro:GFP-GUS, and the auxin-conjugating transgene PpSHI2pro:IAAL, we could show that the PpSHI genes, and by inference also auxin, play important roles for reproductive organ development in moss. The PpSHI genes are required for the apical opening of the reproductive organs, the final differentiation of the egg cell, and the progression of canal cells into a cell death program. The apical cells of the archegonium, the canal cells, and the egg cell are also sites of auxin responsiveness and are affected by reduced levels of active auxin, suggesting that auxin mediates PpSHI function in the reproductive organs.},
author = {Landberg, Katarina and Pederson, Eric and Viaene, Tom and Bozorg, Behruz and Friml, Jirí and Jönsson, Henrik and Thelander, Mattias and Sundberg, Eva},
journal = {Plant Physiology},
number = {3},
pages = {1406 -- 1419},
publisher = {American Society of Plant Biologists},
title = {{The moss physcomitrella patens reproductive organ development is highly organized, affected by the two SHI/STY genes and by the level of active auxin in the SHI/STY expression domain}},
doi = {10.1104/pp.113.214023},
volume = {162},
year = {2013},
}
@article{2810,
abstract = {The epistatic interactions that underlie evolutionary constraint have mainly been studied for constant external conditions. However, environmental changes may modulate epistasis and hence affect genetic constraints. Here we investigate genetic constraints in the adaptive evolution of a novel regulatory function in variable environments, using the lac repressor, LacI, as a model system. We have systematically reconstructed mutational trajectories from wild type LacI to three different variants that each exhibit an inverse response to the inducing ligand IPTG, and analyzed the higher-order interactions between genetic and environmental changes. We find epistasis to depend strongly on the environment. As a result, mutational steps essential to inversion but inaccessible by positive selection in one environment, become accessible in another. We present a graphical method to analyze the observed complex higher-order interactions between multiple mutations and environmental change, and show how the interactions can be explained by a combination of mutational effects on allostery and thermodynamic stability. This dependency of genetic constraint on the environment should fundamentally affect evolutionary dynamics and affects the interpretation of phylogenetic data.},
author = {De Vos, Marjon and Poelwijk, Frank and Battich, Nico and Ndika, Joseph and Tans, Sander},
journal = {PLoS Genetics},
number = {6},
publisher = {Public Library of Science},
title = {{Environmental dependence of genetic constraint}},
doi = {10.1371/journal.pgen.1003580},
volume = {9},
year = {2013},
}
@article{2811,
abstract = {In pipe, channel, and boundary layer flows turbulence first occurs intermittently in space and time: at moderate Reynolds numbers domains of disordered turbulent motion are separated by quiescent laminar regions. Based on direct numerical simulations of pipe flow we argue here that the spatial intermittency has its origin in a nearest neighbor interaction between turbulent regions. We further show that in this regime turbulent flows are intrinsically intermittent with a well-defined equilibrium turbulent fraction but without ever assuming a steady pattern. This transition scenario is analogous to that found in simple models such as coupled map lattices. The scaling observed implies that laminar intermissions of the turbulent flow will persist to arbitrarily large Reynolds numbers.},
author = {Avila, Marc and Hof, Björn},
journal = {Physical Review E},
number = {6},
publisher = {American Institute of Physics},
title = {{Nature of laminar-turbulence intermittency in shear flows}},
doi = {10.1103/PhysRevE.87.063012},
volume = {87},
year = {2013},
}
@inproceedings{2812,
abstract = {We consider the problem of deciding whether the persistent homology group of a simplicial pair (K, L) can be realized as the homology H* (X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in ℝ3. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S3 within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard.},
author = {Attali, Dominique and Bauer, Ulrich and Devillers, Olivier and Glisse, Marc and Lieutier, André},
booktitle = {Proceedings of the 29th annual symposium on Computational Geometry},
location = {Rio de Janeiro, Brazil},
pages = {117 -- 125},
publisher = {ACM},
title = {{Homological reconstruction and simplification in R3}},
doi = {10.1145/2462356.2462373},
year = {2013},
}
@article{2813,
abstract = {Turbulence is ubiquitous in nature, yet even for the case of ordinary Newtonian fluids like water, our understanding of this phenomenon is limited. Many liquids of practical importance are more complicated (e.g., blood, polymer melts, paints), however; they exhibit elastic as well as viscous characteristics, and the relation between stress and strain is nonlinear. We demonstrate here for a model system of such complex fluids that at high shear rates, turbulence is not simply modified as previously believed but is suppressed and replaced by a different type of disordered motion, elasto-inertial turbulence. Elasto-inertial turbulence is found to occur at much lower Reynolds numbers than Newtonian turbulence, and the dynamical properties differ significantly. The friction scaling observed coincides with the so-called "maximum drag reduction" asymptote, which is exhibited by a wide range of viscoelastic fluids.},
author = {Samanta, Devranjan and Dubief, Yves and Holzner, Markus and Schäfer, Christof and Morozov, Alexander and Wagner, Christian and Hof, Björn},
journal = {PNAS},
number = {26},
pages = {10557 -- 10562},
publisher = {National Academy of Sciences},
title = {{Elasto-inertial turbulence}},
doi = {10.1073/pnas.1219666110},
volume = {110},
year = {2013},
}
@article{2814,
abstract = {We study the problem of generating a test sequence that achieves maximal coverage for a reactive system under test. We formulate the problem as a repeated game between the tester and the system, where the system state space is partitioned according to some coverage criterion and the objective of the tester is to maximize the set of partitions (or coverage goals) visited during the game. We show the complexity of the maximal coverage problem for non-deterministic systems is PSPACE-complete, but is NP-complete for deterministic systems. For the special case of non-deterministic systems with a re-initializing "reset" action, which represent running a new test input on a re-initialized system, we show that the complexity is coNP-complete. Our proof technique for reset games uses randomized testing strategies that circumvent the exponentially large memory requirement of deterministic testing strategies. We also discuss the memory requirement for deterministic strategies and extensions of our results to other models, such as pushdown systems and timed systems.},
author = {Chatterjee, Krishnendu and Alfaro, Luca and Majumdar, Ritankar},
journal = {International Journal of Foundations of Computer Science},
number = {2},
pages = {165 -- 185},
publisher = {World Scientific Publishing},
title = {{The complexity of coverage}},
doi = {10.1142/S0129054113400066},
volume = {24},
year = {2013},
}
@article{2821,
abstract = {Many key aspects of plant development are regulated by the polarized transport of the phytohormone auxin. Cellular auxin efflux, the rate-limiting step in this process, has been shown to rely on the coordinated action of PIN-formed (PIN) and B-type ATP binding cassette (ABCB) carriers. Here, we report that polar auxin transport in the Arabidopsis thaliana root also requires the action of a Major Facilitator Superfamily (MFS) transporter, Zinc-Induced Facilitator-Like 1 (ZIFL1). Sequencing, promoter-reporter, and fluorescent protein fusion experiments indicate that the full-length ZIFL1.1 protein and a truncated splice isoform, ZIFL1.3, localize to the tonoplast of root cells and the plasma membrane of leaf stomatal guard cells, respectively. Using reverse genetics, we show that the ZIFL1.1 transporter regulates various root auxin-related processes, while the ZIFL1.3 isoform mediates drought tolerance by regulating stomatal closure. Auxin transport and immunolocalization assays demonstrate that ZIFL1.1 indirectly modulates cellular auxin efflux during shootward auxin transport at the root tip, likely by regulating plasma membrane PIN2 abundance. Finally, heterologous expression in yeast revealed that ZIFL1.1 and ZIFL1.3 share H+-coupled K+ transport activity. Thus, by determining the subcellular and tissue distribution of two isoforms, alternative splicing dictates a dual function for the ZIFL1 transporter. We propose that this MFS carrier regulates stomatal movements and polar auxin transport by modulating potassium and proton fluxes in Arabidopsis cells.},
author = {Remy, Estelle and Cabrito, Tânia and Baster, Pawel and Batista, Rita and Teixeira, Miguel and Friml, Jirí and Sá Correia, Isabel and Duque, Paula},
journal = {Plant Cell},
number = {3},
pages = {901 -- 926},
publisher = {American Society of Plant Biologists},
title = {{A major facilitator superfamily transporter plays a dual role in polar auxin transport and drought stress tolerance in Arabidopsis}},
doi = {10.1105/tpc.113.110353},
volume = {25},
year = {2013},
}
@article{2822,
abstract = {Identification of genes that control root system architecture in crop plants requires innovations that enable high-throughput and accurate measurements of root system architecture through time. We demonstrate the ability of a semiautomated 3D in vivo imaging and digital phenotyping pipeline to interrogate the quantitative genetic basis of root system growth in a rice biparental mapping population, Bala x Azucena. We phenotyped >1,400 3D root models and >57,000 2D images for a suite of 25 traits that quantified the distribution, shape, extent of exploration, and the intrinsic size of root networks at days 12, 14, and 16 of growth in a gellan gum medium. From these data we identified 89 quantitative trait loci, some of which correspond to those found previously in soil-grown plants, and provide evidence for genetic tradeoffs in root growth allocations, such as between the extent and thoroughness of exploration. We also developed a multivariate method for generating and mapping central root architecture phenotypes and used it to identify five major quantitative trait loci (r2 = 24-37%), two of which were not identified by our univariate analysis. Our imaging and analytical platform provides a means to identify genes with high potential for improving root traits and agronomic qualities of crops.},
author = {Topp, Christopher and Iyer Pascuzzi, Anjali and Anderson, Jill and Lee, Cheng and Zurek, Paul and Symonova, Olga and Zheng, Ying and Bucksch, Alexander and Mileyko, Yuriy and Galkovskyi, Taras and Moore, Brad and Harer, John and Edelsbrunner, Herbert and Mitchell Olds, Thomas and Weitz, Joshua and Benfey, Philip},
journal = {PNAS},
number = {18},
pages = {E1695 -- E1704},
publisher = {National Academy of Sciences},
title = {{3D phenotyping and quantitative trait locus mapping identify core regions of the rice genome controlling root architecture}},
doi = {10.1073/pnas.1304354110},
volume = {110},
year = {2013},
}
@article{2826,
abstract = {Myopia, or near-sightedness, is an ocular refractive error of unfocused image quality in front of the retinal plane. Individuals with high-grade myopia (dioptric power greater than -6.00) are predisposed to ocular morbidities such as glaucoma, retinal detachment, and myopic maculopathy. Nonsyndromic, high-grade myopia is highly heritable, and to date multiple gene loci have been reported. We performed exome sequencing in 4 individuals from an 11-member family of European descent from the United States. Affected individuals had a mean dioptric spherical equivalent of -22.00 sphere. A premature stop codon mutation c.157C>T (p.Gln53*) cosegregating with disease was discovered within SCO2 that maps to chromosome 22q13.33. Subsequent analyses identified three additional mutations in three highly myopic unrelated individuals (c.341G>A, c.418G>A, and c.776C>T). To determine differential gene expression in a developmental mouse model, we induced myopia by applying a -15.00D lens over one eye. Messenger RNA levels of SCO2 were significantly downregulated in myopic mouse retinae. Immunohistochemistry in mouse eyes confirmed SCO2 protein localization in retina, retinal pigment epithelium, and sclera. SCO2 encodes for a copper homeostasis protein influential in mitochondrial cytochrome c oxidase activity. Copper deficiencies have been linked with photoreceptor loss and myopia with increased scleral wall elasticity. Retinal thinning has been reported with an SC02 variant. Human mutation identification with support from an induced myopic animal provides biological insights of myopic development.},
author = {Tran Viet, Khanh and Powell, Caldwell and Barathi, Veluchamy and Klemm, Thomas and Maurer Stroh, Sebastian and Limviphuvadh, Vachiranee and Soler, Vincent and Ho, Candice and Yanovitch, Tammy and Schneider, Georg and Li, Yi and Nading, Erica and Metlapally, Ravikanth and Saw, Seang and Goh, Liang and Rozen, Steve and Young, Terri},
journal = {American Journal of Human Genetics},
number = {5},
pages = {820 -- 826},
publisher = {Cell Press},
title = {{Mutations in SCO2 are associated with autosomal-dominant high-grade myopia}},
doi = {10.1016/j.ajhg.2013.04.005},
volume = {92},
year = {2013},
}