@article{1679,
author = {Lemoult, Grégoire M and Maier, Philipp and Hof, Björn},
journal = {Physics of Fluids},
number = {9},
publisher = {American Institute of Physics},
title = {{Taylor's Forest}},
doi = {10.1063/1.4930850},
volume = {27},
year = {2015},
}
@article{1681,
abstract = {In many social situations, individuals endeavor to find the single best possible partner, but are constrained to evaluate the candidates in sequence. Examples include the search for mates, economic partnerships, or any other long-term ties where the choice to interact involves two parties. Surprisingly, however, previous theoretical work on mutual choice problems focuses on finding equilibrium solutions, while ignoring the evolutionary dynamics of decisions. Empirically, this may be of high importance, as some equilibrium solutions can never be reached unless the population undergoes radical changes and a sufficient number of individuals change their decisions simultaneously. To address this question, we apply a mutual choice sequential search problem in an evolutionary game-theoretical model that allows one to find solutions that are favored by evolution. As an example, we study the influence of sequential search on the evolutionary dynamics of cooperation. For this, we focus on the classic snowdrift game and the prisoner’s dilemma game.},
author = {Priklopil, Tadeas and Chatterjee, Krishnendu},
journal = {Games},
number = {4},
pages = {413 -- 437},
publisher = {Multidisciplinary Digital Publishing Institute},
title = {{Evolution of decisions in population games with sequentially searching individuals}},
doi = {10.3390/g6040413},
volume = {6},
year = {2015},
}
@article{1682,
abstract = {We study the problem of robust satisfiability of systems of nonlinear equations, namely, whether for a given continuous function f:K→ ℝn on a finite simplicial complex K and α > 0, it holds that each function g: K → ℝn such that ||g - f || ∞ < α, has a root in K. Via a reduction to the extension problem of maps into a sphere, we particularly show that this problem is decidable in polynomial time for every fixed n, assuming dimK ≤ 2n - 3. This is a substantial extension of previous computational applications of topological degree and related concepts in numerical and interval analysis. Via a reverse reduction, we prove that the problem is undecidable when dim K > 2n - 2, where the threshold comes from the stable range in homotopy theory. For the lucidity of our exposition, we focus on the setting when f is simplexwise linear. Such functions can approximate general continuous functions, and thus we get approximation schemes and undecidability of the robust satisfiability in other possible settings.},
author = {Franek, Peter and Krcál, Marek},
journal = {Journal of the ACM},
number = {4},
publisher = {ACM},
title = {{Robust satisfiability of systems of equations}},
doi = {10.1145/2751524},
volume = {62},
year = {2015},
}
@article{1684,
abstract = {Many species groups, including mammals and many insects, determine sex using heteromorphic sex chromosomes. Diptera flies, which include the model Drosophila melanogaster, generally have XY sex chromosomes and a conserved karyotype consisting of six chromosomal arms (five large rods and a small dot), but superficially similar karyotypes may conceal the true extent of sex chromosome variation. Here, we use whole-genome analysis in 37 fly species belonging to 22 different families of Diptera and uncover tremendous hidden diversity in sex chromosome karyotypes among flies. We identify over a dozen different sex chromosome configurations, and the small dot chromosome is repeatedly used as the sex chromosome, which presumably reflects the ancestral karyotype of higher Diptera. However, we identify species with undifferentiated sex chromosomes, others in which a different chromosome replaced the dot as a sex chromosome or in which up to three chromosomal elements became incorporated into the sex chromosomes, and others yet with female heterogamety (ZW sex chromosomes). Transcriptome analysis shows that dosage compensation has evolved multiple times in flies, consistently through up-regulation of the single X in males. However, X chromosomes generally show a deficiency of genes with male-biased expression, possibly reflecting sex-specific selective pressures. These species thus provide a rich resource to study sex chromosome biology in a comparative manner and show that similar selective forces have shaped the unique evolution of sex chromosomes in diverse fly taxa.},
author = {Vicoso, Beatriz and Bachtrog, Doris},
journal = {PLoS Biology},
number = {4},
publisher = {Public Library of Science},
title = {{Numerous transitions of sex chromosomes in Diptera}},
doi = {10.1371/journal.pbio.1002078},
volume = {13},
year = {2015},
}
@inproceedings{1685,
abstract = {Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any ε > 0, we show how to compute a (1 + ε) approximation of the shortest cut graph in time f(ε, g)n3.
Our techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest.},
author = {Cohen Addad, Vincent and De Mesmay, Arnaud N},
location = {Patras, Greece},
pages = {386 -- 398},
publisher = {Springer},
title = {{A fixed parameter tractable approximation scheme for the optimal cut graph of a surface}},
doi = {10.1007/978-3-662-48350-3_33},
volume = {9294},
year = {2015},
}
@article{121,
abstract = {We show that the simplest building blocks of origami-based materials - rigid, degree-four vertices - are generically multistable. The existence of two distinct branches of folding motion emerging from the flat state suggests at least bistability, but we show how nonlinearities in the folding motions allow generic vertex geometries to have as many as five stable states. In special geometries with collinear folds and symmetry, more branches emerge leading to as many as six stable states. Tuning the fold energy parameters, we show how monostability is also possible. Finally, we show how to program the stability features of a single vertex into a periodic fold tessellation. The resulting metasheets provide a previously unanticipated functionality - tunable and switchable shape and size via multistability.},
author = {Waitukaitis, Scott R and Menaut, Rémi and Chen, Bryan and Van Hecke, Martin},
journal = {APS Physics, Physical Review Letters},
number = {5},
publisher = {American Physical Society},
title = {{Origami multistability: From single vertices to metasheets}},
doi = {10.1103/PhysRevLett.114.055503},
volume = {114},
year = {2015},
}
@article{9057,
abstract = {Motility is a basic feature of living microorganisms, and how it works is often determined by environmental cues. Recent efforts have focused on developing artificial systems that can mimic microorganisms, in particular their self-propulsion. We report on the design and characterization of synthetic self-propelled particles that migrate upstream, known as positive rheotaxis. This phenomenon results from a purely physical mechanism involving the interplay between the polarity of the particles and their alignment by a viscous torque. We show quantitative agreement between experimental data and a simple model of an overdamped Brownian pendulum. The model notably predicts the existence of a stagnation point in a diverging flow. We take advantage of this property to demonstrate that our active particles can sense and predictably organize in an imposed flow. Our colloidal system represents an important step toward the realization of biomimetic microsystems with the ability to sense and respond to environmental changes.},
author = {Palacci, Jérémie A and Sacanna, Stefano and Abramian, Anaïs and Barral, Jérémie and Hanson, Kasey and Grosberg, Alexander Y. and Pine, David J. and Chaikin, Paul M.},
issn = {2375-2548},
journal = {Science Advances},
number = {4},
publisher = {American Association for the Advancement of Science },
title = {{Artificial rheotaxis}},
doi = {10.1126/sciadv.1400214},
volume = {1},
year = {2015},
}
@article{9141,
abstract = {The breaking of internal tides is believed to provide a large part of the power needed to mix the abyssal ocean and sustain the meridional overturning circulation. Both the fraction of internal tide energy that is dissipated locally and the resulting vertical mixing distribution are crucial for the ocean state, but remain poorly quantified. Here we present a first worldwide estimate of mixing due to internal tides generated at small‐scale abyssal hills. Our estimate is based on linear wave theory, a nonlinear parameterization for wave breaking and uses quasi‐global small‐scale abyssal hill bathymetry, stratification, and tidal data. We show that a large fraction of abyssal‐hill generated internal tide energy is locally dissipated over mid‐ocean ridges in the Southern Hemisphere. Significant dissipation occurs above ridge crests, and, upon rescaling by the local stratification, follows a monotonic exponential decay with height off the bottom, with a nonuniform decay scale. We however show that a substantial part of the dissipation occurs over the smoother flanks of mid‐ocean ridges, and exhibits a middepth maximum due to the interplay of wave amplitude with stratification. We link the three‐dimensional map of dissipation to abyssal hills characteristics, ocean stratification, and tidal forcing, and discuss its potential implementation in time‐evolving parameterizations for global climate models. Current tidal parameterizations only account for waves generated at large‐scale satellite‐resolved bathymetry. Our results suggest that the presence of small‐scale, mostly unresolved abyssal hills could significantly enhance the spatial inhomogeneity of tidal mixing, particularly above mid‐ocean ridges in the Southern Hemisphere.},
author = {Lefauve, Adrien and MULLER, Caroline J and Melet, Angélique},
issn = {2169-9275},
journal = {Journal of Geophysical Research: Oceans},
number = {7},
pages = {4760--4777},
publisher = {American Geophysical Union},
title = {{A three-dimensional map of tidal dissipation over abyssal hills}},
doi = {10.1002/2014jc010598},
volume = {120},
year = {2015},
}
@article{928,
abstract = {The actomyosin cytoskeleton is a primary force-generating mechanism in morphogenesis, thus a robust spatial control of cytoskeletal positioning is essential. In this report, we demonstrate that actomyosin contractility and planar cell polarity (PCP) interact in post-mitotic Ciona notochord cells to self-assemble and reposition actomyosin rings, which play an essential role for cell elongation. Intriguingly, rings always form at the cells′ anterior edge before migrating towards the center as contractility increases, reflecting a novel dynamical property of the cortex. Our drug and genetic manipulations uncover a tug-of-war between contractility, which localizes cortical flows toward the equator and PCP, which tries to reposition them. We develop a simple model of the physical forces underlying this tug-of-war, which quantitatively reproduces our results. We thus propose a quantitative framework for dissecting the relative contribution of contractility and PCP to the self-assembly and repositioning of cytoskeletal structures, which should be applicable to other morphogenetic events.},
author = {Sehring, Ivonne and Recho, Pierre and Denker, Elsa and Kourakis, Matthew and Mathiesen, Birthe and Hannezo, Edouard B and Dong, Bo and Jiang, Di},
journal = {eLife},
publisher = {eLife Sciences Publications},
title = {{Assembly and positioning of actomyosin rings by contractility and planar cell polarity}},
doi = {10.7554/eLife.09206},
volume = {4},
year = {2015},
}
@article{933,
abstract = {Although collective cell motion plays an important role, for example during wound healing, embryogenesis, or cancer progression, the fundamental rules governing this motion are still not well understood, in particular at high cell density. We study here the motion of human bronchial epithelial cells within a monolayer, over long times. We observe that, as the monolayer ages, the cells slow down monotonously, while the velocity correlation length first increases as the cells slow down but eventually decreases at the slowest motions. By comparing experiments, analytic model, and detailed particle-based simulations, we shed light on this biological amorphous solidification process, demonstrating that the observed dynamics can be explained as a consequence of the combined maturation and strengthening of cell-cell and cell-substrate adhesions. Surprisingly, the increase of cell surface density due to proliferation is only secondary in this process. This analysis is confirmed with two other cell types. The very general relations between the mean cell velocity and velocity correlation lengths, which apply for aggregates of self-propelled particles, as well as motile cells, can possibly be used to discriminate between various parameter changes in vivo, from noninvasive microscopy data.},
author = {García, Simón and Hannezo, Edouard B and Elgeti, Jens and Joanny, Jean and Silberzan, Pascal and Gov, Nir},
journal = {PNAS},
number = {50},
pages = {15314 -- 15319},
publisher = {National Academy of Sciences},
title = {{Physics of active jamming during collective cellular motion in a monolayer}},
doi = {10.1073/pnas.1510973112},
volume = {112},
year = {2015},
}
@article{981,
abstract = {The tunability of topological surface states and controllable opening of the Dirac gap are of fundamental and practical interest in the field of topological materials. In the newly discovered topological crystalline insulators (TCIs), theory predicts that the Dirac node is protected by a crystalline symmetry and that the surface state electrons can acquire a mass if this symmetry is broken. Recent studies have detected signatures of a spontaneously generated Dirac gap in TCIs; however, the mechanism of mass formation remains elusive. In this work, we present scanning tunnelling microscopy (STM) measurements of the TCI Pb 1â'x Sn x Se for a wide range of alloy compositions spanning the topological and non-topological regimes. The STM topographies reveal a symmetry-breaking distortion on the surface, which imparts mass to the otherwise massless Dirac electrons-a mechanism analogous to the long sought-after Higgs mechanism in particle physics. Interestingly, the measured Dirac gap decreases on approaching the trivial phase, whereas the magnitude of the distortion remains nearly constant. Our data and calculations reveal that the penetration depth of Dirac surface states controls the magnitude of the Dirac mass. At the limit of the critical composition, the penetration depth is predicted to go to infinity, resulting in zero mass, consistent with our measurements. Finally, we discover the existence of surface states in the non-topological regime, which have the characteristics of gapped, double-branched Dirac fermions and could be exploited in realizing superconductivity in these materials.},
author = {Zeljkovic, Ilija and Okada, Yoshinori and Maksym Serbyn and Sankar, Raman and Walkup, Daniel and Zhou, Wenwen and Liu, Junwei and Chang, Guoqing and Wang, Yungjui and Hasan, Md Z and Chou, Fangcheng and Lin, Hsin and Bansil, Arun and Fu, Liang and Madhavan, Vidya},
journal = {Nature Materials},
number = {3},
pages = {318 -- 324},
publisher = {Nature Publishing Group},
title = {{Dirac mass generation from crystal symmetry breaking on the surfaces of topological crystalline insulators}},
doi = {10.1038/nmat4215},
volume = {14},
year = {2015},
}
@article{982,
abstract = {We propose a new approach to probing ergodicity and its breakdown in one-dimensional quantum manybody systems based on their response to a local perturbation. We study the distribution of matrix elements of a local operator between the system's eigenstates, finding a qualitatively different behavior in the manybody localized (MBL) and ergodic phases. To characterize how strongly a local perturbation modifies the eigenstates, we introduce the parameter g(L) = (In (Vnm/δ)) which represents the disorder-averaged ratio of a typical matrix element of a local operator V to energy level spacing δ this parameter is reminiscent of the Thouless conductance in the single-particle localization. We show that the parameter g(L) decreases with system size L in the MBL phase and grows in the ergodic phase. We surmise that the delocalization transition occurs when g(L) is independent of system size, g(L)=gc ~ 1. We illustrate our approach by studying the many-body localization transition and resolving the many-body mobility edge in a disordered one-dimensional XXZ spin-1=2 chain using exact diagonalization and time-evolving block-decimation methods. Our criterion for the MBL transition gives insights into microscopic details of transition. Its direct physical consequences, in particular, logarithmically slow transport at the transition and extensive entanglement entropy of the eigenstates, are consistent with recent renormalization-group predictions.},
author = {Maksym Serbyn and Papić, Zlatko and Abanin, Dmitry A},
journal = {Physical Review X},
number = {4},
publisher = {American Physical Society},
title = {{Criterion for many-body localization-delocalization phase transition}},
doi = {10.1103/PhysRevX.5.041047},
volume = {5},
year = {2015},
}
@article{99,
abstract = {Quasiparticle excitations can compromise the performance of superconducting devices, causing high-frequency dissipation, decoherence in Josephson qubits, and braiding errors in proposed Majorana-based topological quantum computers. Quasiparticle dynamics have been studied in detail in metallic superconductors but remain relatively unexplored in semiconductor-superconductor structures, which are now being intensely pursued in the context of topological superconductivity. To this end, we use a system comprising a gate-confined semiconductor nanowire with an epitaxially grown superconductor layer, yielding an isolated, proximitized nanowire segment. We identify bound states in the semiconductor by means of bias spectroscopy, determine the characteristic temperatures and magnetic fields for quasiparticle excitations, and extract a parity lifetime (poisoning time) of the bound state in the semiconductor exceeding 10 ms.},
author = {Higginbotham, Andrew P and Albrecht, S M and Kiršanskas, Gediminas and Chang, W and Kuemmeth, Ferdinand and Krogstrup, Peter and Jespersen, Thomas and Nygård, Jesper and Flensberg, Karsten and Marcus, Charles},
journal = {Nature Physics},
number = {12},
pages = {1017 -- 1021},
publisher = {Nature Publishing Group},
title = {{Parity lifetime of bound states in a proximitized semiconductor nanowire}},
doi = {10.1038/nphys3461},
volume = {11},
year = {2015},
}
@article{388,
abstract = {We use ultrafast optical spectroscopy to observe binding of charged single-particle excitations (SE) in the magnetically frustrated Mott insulator Na2IrO3. Above the antiferromagnetic ordering temperature (TN) the system response is due to both Hubbard excitons (HE) and their constituent unpaired SE. The SE response becomes strongly suppressed immediately below TN. We argue that this increase in binding energy is due to a unique interplay between the frustrated Kitaev and the weak Heisenberg-type ordering term in the Hamiltonian, mediating an effective interaction between the spin-singlet SE. This interaction grows with distance causing the SE to become trapped in the HE, similar to quark confinement inside hadrons. This binding of charged particles, induced by magnetic ordering, is a result of a confinement-deconfinement transition of spin excitations. This observation provides evidence for spin liquid type behavior which is expected in Na2IrO3.},
author = {Alpichshev, Zhanybek and Mahmood, Fahad and Cao, Gang and Gedik, Nuh},
journal = {Physical Review Letters},
number = {1},
publisher = {American Physical Society},
title = {{Confinement deconfinement transition as an indication of spin liquid type behavior in Na2IrO3}},
doi = {10.1103/PhysRevLett.114.017203},
volume = {114},
year = {2015},
}
@phdthesis{1401,
abstract = {The human ability to recognize objects in complex scenes has driven research in the computer vision field over couple of decades. This thesis focuses on the object recognition task in images. That is, given the image, we want the computer system to be able to predict the class of the object that appears in the image. A recent succesful attempt to bridge semantic understanding of the image perceived by humans and by computers uses attribute-based models. Attributes are semantic properties of the objects shared across different categories, which humans and computers can decide on. To explore the attribute-based models we take a statistical machine learning approach, and address two key learning challenges in view of object recognition task: learning augmented attributes as mid-level discriminative feature representation, and learning with attributes as privileged information. Our main contributions are parametric and non-parametric models and algorithms to solve these frameworks. In the parametric approach, we explore an autoencoder model combined with the large margin nearest neighbor principle for mid-level feature learning, and linear support vector machines for learning with privileged information. In the non-parametric approach, we propose a supervised Indian Buffet Process for automatic augmentation of semantic attributes, and explore the Gaussian Processes classification framework for learning with privileged information. A thorough experimental analysis shows the effectiveness of the proposed models in both parametric and non-parametric views.},
author = {Sharmanska, Viktoriia},
pages = {144},
publisher = {IST Austria},
title = {{Learning with attributes for object recognition: Parametric and non-parametrics views}},
year = {2015},
}
@article{1666,
abstract = {Evolution of gene regulation is crucial for our understanding of the phenotypic differences between species, populations and individuals. Sequence-specific binding of transcription factors to the regulatory regions on the DNA is a key regulatory mechanism that determines gene expression and hence heritable phenotypic variation. We use a biophysical model for directional selection on gene expression to estimate the rates of gain and loss of transcription factor binding sites (TFBS) in finite populations under both point and insertion/deletion mutations. Our results show that these rates are typically slow for a single TFBS in an isolated DNA region, unless the selection is extremely strong. These rates decrease drastically with increasing TFBS length or increasingly specific protein-DNA interactions, making the evolution of sites longer than ∼ 10 bp unlikely on typical eukaryotic speciation timescales. Similarly, evolution converges to the stationary distribution of binding sequences very slowly, making the equilibrium assumption questionable. The availability of longer regulatory sequences in which multiple binding sites can evolve simultaneously, the presence of “pre-sites” or partially decayed old sites in the initial sequence, and biophysical cooperativity between transcription factors, can all facilitate gain of TFBS and reconcile theoretical calculations with timescales inferred from comparative genomics.},
author = {Tugrul, Murat and Paixao, Tiago and Barton, Nicholas H and Tkacik, Gasper},
journal = {PLoS Genetics},
number = {11},
publisher = {Public Library of Science},
title = {{Dynamics of transcription factor binding site evolution}},
doi = {10.1371/journal.pgen.1005639},
volume = {11},
year = {2015},
}
@unpublished{8183,
abstract = {We study conditions under which a finite simplicial complex $K$ can be mapped to $\mathbb R^d$ without higher-multiplicity intersections. An almost $r$-embedding is a map $f: K\to \mathbb R^d$ such that the images of any $r$
pairwise disjoint simplices of $K$ do not have a common point. We show that if $r$ is not a prime power and $d\geq 2r+1$, then there is a counterexample to the topological Tverberg conjecture, i.e., there is an almost $r$-embedding of
the $(d+1)(r-1)$-simplex in $\mathbb R^d$. This improves on previous constructions of counterexamples (for $d\geq 3r$) based on a series of papers by M. \"Ozaydin, M. Gromov, P. Blagojevi\'c, F. Frick, G. Ziegler, and the second and fourth present authors. The counterexamples are obtained by proving the following algebraic criterion in codimension 2: If $r\ge3$ and if $K$ is a finite $2(r-1)$-complex then there exists an almost $r$-embedding $K\to \mathbb R^{2r}$ if and only if there exists a general position PL map $f:K\to \mathbb R^{2r}$ such that the algebraic intersection number of the $f$-images of any $r$ pairwise disjoint simplices of $K$ is zero. This result can be restated in terms of cohomological obstructions or equivariant maps, and extends an analogous codimension 3 criterion by the second and fourth authors. As another application we classify ornaments $f:S^3 \sqcup S^3\sqcup S^3\to \mathbb R^5$ up to ornament
concordance. It follows from work of M. Freedman, V. Krushkal and P. Teichner that the analogous criterion for $r=2$ is false. We prove a lemma on singular higher-dimensional Borromean rings, yielding an elementary proof of the counterexample.},
author = {Avvakumov, Sergey and Mabillard, Isaac and Skopenkov, A. and Wagner, Uli},
booktitle = {arXiv},
title = {{Eliminating higher-multiplicity intersections, III. Codimension 2}},
year = {2015},
}
@article{5749,
abstract = {Parasitism creates selection for resistance mechanisms in host populations and is hypothesized to promote increased host evolvability. However, the influence of these traits on host evolution when parasites are no longer present is unclear. We used experimental evolution and whole-genome sequencing of Escherichia coli to determine the effects of past and present exposure to parasitic viruses (phages) on the spread of mutator alleles, resistance, and bacterial competitive fitness. We found that mutator alleles spread rapidly during adaptation to any of four different phage species, and this pattern was even more pronounced with multiple phages present simultaneously. However, hypermutability did not detectably accelerate adaptation in the absence of phages and recovery of fitness costs associated with resistance. Several lineages evolved phage resistance through elevated mucoidy, and during subsequent evolution in phage-free conditions they rapidly reverted to nonmucoid, phage-susceptible phenotypes. Genome sequencing revealed that this phenotypic reversion was achieved by additional genetic changes rather than by genotypic reversion of the initial resistance mutations. Insertion sequence (IS) elements played a key role in both the acquisition of resistance and adaptation in the absence of parasites; unlike single nucleotide polymorphisms, IS insertions were not more frequent in mutator lineages. Our results provide a genetic explanation for rapid reversion of mucoidy, a phenotype observed in other bacterial species including human pathogens. Moreover, this demonstrates that the types of genetic change underlying adaptation to fitness costs, and consequently the impact of evolvability mechanisms such as increased point-mutation rates, depend critically on the mechanism of resistance.},
author = {Wielgoss, Sébastien and Bergmiller, Tobias and Bischofberger, Anna M. and Hall, Alex R.},
issn = {0737-4038},
journal = {Molecular Biology and Evolution},
number = {3},
pages = {770--782},
publisher = {Oxford University Press},
title = {{Adaptation to Parasites and Costs of Parasite Resistance in Mutator and Nonmutator Bacteria}},
doi = {10.1093/molbev/msv270},
volume = {33},
year = {2015},
}
@inproceedings{1607,
abstract = {We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m=O(n)) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of ϵ in time O(n⋅log(n/ϵ)) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O(n⋅log(|a⋅b|))=O(n⋅log(n⋅W)), when the output is ab, as compared to the previously best known algorithm with running time O(n2⋅log(n⋅W)). Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O(n2⋅m) time and the associated decision problem can be solved in O(n⋅m) time, improving the previous known O(n3⋅m⋅log(n⋅W)) and O(n2⋅m) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O(n⋅logn) time, improving the previous known O(n4⋅log(n⋅W)) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas},
location = {San Francisco, CA, USA},
pages = {140 -- 157},
publisher = {Springer},
title = {{Faster algorithms for quantitative verification in constant treewidth graphs}},
doi = {10.1007/978-3-319-21690-4_9},
volume = {9206},
year = {2015},
}
@article{9532,
abstract = {Genomic imprinting, an inherently epigenetic phenomenon defined by parent of origin-dependent gene expression, is observed in mammals and flowering plants. Genome-scale surveys of imprinted expression and the underlying differential epigenetic marks have led to the discovery of hundreds of imprinted plant genes and confirmed DNA and histone methylation as key regulators of plant imprinting. However, the biological roles of the vast majority of imprinted plant genes are unknown, and the evolutionary forces shaping plant imprinting remain rather opaque. Here, we review the mechanisms of plant genomic imprinting and discuss theories of imprinting evolution and biological significance in light of recent findings.},
author = {Rodrigues, Jessica A. and ZILBERMAN, Daniel},
issn = {1549-5477},
journal = {Genes and Development},
number = {24},
pages = {2517–2531},
publisher = {Cold Spring Harbor Laboratory Press},
title = {{Evolution and function of genomic imprinting in plants}},
doi = {10.1101/gad.269902.115},
volume = {29},
year = {2015},
}
@article{9575,
abstract = {We give several results showing that different discrete structures typically gain certain spanning substructures (in particular, Hamilton cycles) after a modest random perturbation. First, we prove that adding linearly many random edges to a dense k-uniform hypergraph ensures the (asymptotically almost sure) existence of a perfect matching or a loose Hamilton cycle. The proof involves an interesting application of Szemerédi's Regularity Lemma, which might be independently useful. We next prove that digraphs with certain strong expansion properties are pancyclic, and use this to show that adding a linear number of random edges typically makes a dense digraph pancyclic. Finally, we prove that perturbing a certain (minimum-degree-dependent) number of random edges in a tournament typically ensures the existence of multiple edge-disjoint Hamilton cycles. All our results are tight.},
author = {Krivelevich, Michael and Kwan, Matthew Alan and Sudakov, Benny},
issn = {1571-0653},
journal = {Electronic Notes in Discrete Mathematics},
pages = {181--187},
publisher = {Elsevier},
title = {{Cycles and matchings in randomly perturbed digraphs and hypergraphs}},
doi = {10.1016/j.endm.2015.06.027},
volume = {49},
year = {2015},
}
@article{1619,
abstract = {The emergence of drug resistant pathogens is a serious public health problem. It is a long-standing goal to predict rates of resistance evolution and design optimal treatment strategies accordingly. To this end, it is crucial to reveal the underlying causes of drug-specific differences in the evolutionary dynamics leading to resistance. However, it remains largely unknown why the rates of resistance evolution via spontaneous mutations and the diversity of mutational paths vary substantially between drugs. Here we comprehensively quantify the distribution of fitness effects (DFE) of mutations, a key determinant of evolutionary dynamics, in the presence of eight antibiotics representing the main modes of action. Using precise high-throughput fitness measurements for genome-wide Escherichia coli gene deletion strains, we find that the width of the DFE varies dramatically between antibiotics and, contrary to conventional wisdom, for some drugs the DFE width is lower than in the absence of stress. We show that this previously underappreciated divergence in DFE width among antibiotics is largely caused by their distinct drug-specific dose-response characteristics. Unlike the DFE, the magnitude of the changes in tolerated drug concentration resulting from genome-wide mutations is similar for most drugs but exceptionally small for the antibiotic nitrofurantoin, i.e., mutations generally have considerably smaller resistance effects for nitrofurantoin than for other drugs. A population genetics model predicts that resistance evolution for drugs with this property is severely limited and confined to reproducible mutational paths. We tested this prediction in laboratory evolution experiments using the “morbidostat”, a device for evolving bacteria in well-controlled drug environments. Nitrofurantoin resistance indeed evolved extremely slowly via reproducible mutations—an almost paradoxical behavior since this drug causes DNA damage and increases the mutation rate. Overall, we identified novel quantitative characteristics of the evolutionary landscape that provide the conceptual foundation for predicting the dynamics of drug resistance evolution.},
author = {Chevereau, Guillaume and Dravecka, Marta and Batur, Tugce and Guvenek, Aysegul and Ayhan, Dilay and Toprak, Erdal and Bollenbach, Mark Tobias},
journal = {PLoS Biology},
number = {11},
publisher = {Public Library of Science},
title = {{Quantifying the determinants of evolutionary dynamics leading to drug resistance}},
doi = {10.1371/journal.pbio.1002299},
volume = {13},
year = {2015},
}
@article{2261,
abstract = {To reveal the full potential of human pluripotent stem cells, new methods for rapid, site-specific genomic engineering are needed. Here, we describe a system for precise genetic modification of human embryonic stem cells (ESCs) and induced pluripotent stem cells (iPSCs). We identified a novel human locus, H11, located in a safe, intergenic, transcriptionally active region of chromosome 22, as the recipient site, to provide robust, ubiquitous expression of inserted genes. Recipient cell lines were established by site-specific placement of a ‘landing pad’ cassette carrying attP sites for phiC31 and Bxb1 integrases at the H11 locus by spontaneous or TALEN-assisted homologous recombination. Dual integrase cassette exchange (DICE) mediated by phiC31 and Bxb1 integrases was used to insert genes of interest flanked by phiC31 and Bxb1 attB sites at the H11 locus, replacing the landing pad. This system provided complete control over content, direction and copy number of inserted genes, with a specificity of 100%. A series of genes, including mCherry and various combinations of the neural transcription factors LMX1a, FOXA2 and OTX2, were inserted in recipient cell lines derived from H9 ESC, as well as iPSC lines derived from a Parkinson’s disease patient and a normal sibling control. The DICE system offers rapid, efficient and precise gene insertion in ESC and iPSC and is particularly well suited for repeated modifications of the same locus.},
author = {Zhu, Fangfang and Gamboa, Matthew and Farruggio, Alfonso and Hippenmeyer, Simon and Tasic, Bosiljka and Schüle, Birgitt and Chen Tsai, Yanru and Calos, Michele},
journal = {Nucleic Acids Research},
number = {5},
publisher = {Oxford University Press},
title = {{DICE, an efficient system for iterative genomic editing in human pluripotent stem cells}},
doi = {10.1093/nar/gkt1290},
volume = {42},
year = {2014},
}
@inproceedings{2275,
abstract = {Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches.
This partial enumeration technique reduces complex high-order energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed.
Our main application of interest is curvature regularization. In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach.
},
author = {Olsson, Carl and Ulen, Johannes and Boykov, Yuri and Kolmogorov, Vladimir},
location = {Sydney, Australia},
pages = {2936 -- 2943},
publisher = {IEEE},
title = {{Partial enumeration and curvature regularization}},
doi = {10.1109/ICCV.2013.365},
year = {2014},
}
@article{2281,
abstract = {We consider two-dimensional Bose-Einstein condensates with attractive interaction, described by the Gross-Pitaevskii functional. Minimizers of this functional exist only if the interaction strength a satisfies {Mathematical expression}, where Q is the unique positive radial solution of {Mathematical expression} in {Mathematical expression}. We present a detailed analysis of the behavior of minimizers as a approaches a*, where all the mass concentrates at a global minimum of the trapping potential.},
author = {Guo, Yujin and Seiringer, Robert},
journal = {Letters in Mathematical Physics},
number = {2},
pages = {141 -- 156},
publisher = {Springer},
title = {{On the mass concentration for Bose-Einstein condensates with attractive interactions}},
doi = {10.1007/s11005-013-0667-9},
volume = {104},
year = {2014},
}
@article{2285,
abstract = {GABAergic inhibitory interneurons control fundamental aspects of neuronal network function. Their functional roles are assumed to be defined by the identity of their input synapses, the architecture of their dendritic tree, the passive and active membrane properties and finally the nature of their postsynaptic targets. Indeed, interneurons display a high degree of morphological and physiological heterogeneity. However, whether their morphological and physiological characteristics are correlated and whether interneuron diversity can be described by a continuum of GABAergic cell types or by distinct classes has remained unclear. Here we perform a detailed morphological and physiological characterization of GABAergic cells in the dentate gyrus, the input region of the hippocampus. To achieve an unbiased and efficient sampling and classification we used knock-in mice expressing the enhanced green fluorescent protein (eGFP) in glutamate decarboxylase 67 (GAD67)-positive neurons and performed cluster analysis. We identified five interneuron classes, each of them characterized by a distinct set of anatomical and physiological parameters. Cross-correlation analysis further revealed a direct relation between morphological and physiological properties indicating that dentate gyrus interneurons fall into functionally distinct classes which may differentially control neuronal network activity.},
author = {Hosp, Jonas and Strüber, Michael and Yanagawa, Yuchio and Obata, Kunihiko and Vida, Imre and Jonas, Peter M and Bartos, Marlene},
journal = {Hippocampus},
number = {2},
pages = {189 -- 203},
publisher = {Wiley-Blackwell},
title = {{Morpho-physiological criteria divide dentate gyrus interneurons into classes}},
doi = {10.1002/hipo.22214},
volume = {23},
year = {2014},
}
@article{2407,
abstract = {Two definitions of the effective mass of a particle interacting with a quantum field, such as a polaron, are considered and shown to be equal in models similar to the Fröhlich polaron model. These are: 1. the mass defined by the low momentum energy E(P)≈E(0)+P2/2 M of the translation invariant system constrained to have momentum P and 2. the mass M of a simple particle in an arbitrary slowly varying external potential, V, described by the nonrelativistic Schrödinger equation, whose ground state energy equals that of the combined particle/field system in a bound state in the same V.},
author = {Lieb, Élliott and Seiringer, Robert},
journal = {Journal of Statistical Physics},
number = {1-2},
pages = {51 -- 57},
publisher = {Springer},
title = {{Equivalence of two definitions of the effective mass of a polaron}},
doi = {10.1007/s10955-013-0791-z},
volume = {154},
year = {2014},
}
@article{248,
abstract = {For any pencil of conics or higher-dimensional quadrics over ℚ, with all degenerate fibres defined over ℚ, we show that the Brauer–Manin obstruction controls weak approximation. The proof is based on the Hasse principle and weak approximation for some special intersections of quadrics over ℚ, which is a consequence of recent advances in additive combinatorics.},
author = {Timothy Browning and Matthiesen, Lilian and Skorobogatov, Alexei N},
journal = {Annals of Mathematics},
number = {1},
pages = {381 -- 402},
publisher = {John Hopkins University Press},
title = {{Rational points on pencils of conics and quadrics with many degenerate fibres}},
doi = {https://doi.org/10.4007/annals.2014.180.1.8},
volume = {180},
year = {2014},
}
@article{2699,
abstract = {We prove the universality of the β-ensembles with convex analytic potentials and for any β >
0, i.e. we show that the spacing distributions of log-gases at any inverse temperature β coincide with those of the Gaussian β-ensembles.},
author = {Erdös, László and Bourgade, Paul and Yau, Horng},
journal = {Duke Mathematical Journal},
number = {6},
pages = {1127 -- 1190},
publisher = {Duke University Press},
title = {{Universality of general β-ensembles}},
doi = {10.1215/00127094-2649752},
volume = {163},
year = {2014},
}
@article{2716,
abstract = {Multi-dimensional mean-payoff and energy games provide the mathematical foundation for the quantitative study of reactive systems, and play a central role in the emerging quantitative theory of verification and synthesis. In this work, we study the strategy synthesis problem for games with such multi-dimensional objectives along with a parity condition, a canonical way to express ω ω -regular conditions. While in general, the winning strategies in such games may require infinite memory, for synthesis the most relevant problem is the construction of a finite-memory winning strategy (if one exists). Our main contributions are as follows. First, we show a tight exponential bound (matching upper and lower bounds) on the memory required for finite-memory winning strategies in both multi-dimensional mean-payoff and energy games along with parity objectives. This significantly improves the triple exponential upper bound for multi energy games (without parity) that could be derived from results in literature for games on vector addition systems with states. Second, we present an optimal symbolic and incremental algorithm to compute a finite-memory winning strategy (if one exists) in such games. Finally, we give a complete characterization of when finite memory of strategies can be traded off for randomness. In particular, we show that for one-dimension mean-payoff parity games, randomized memoryless strategies are as powerful as their pure finite-memory counterparts.},
author = {Chatterjee, Krishnendu and Randour, Mickael and Raskin, Jean},
journal = {Acta Informatica},
number = {3-4},
pages = {129 -- 163},
publisher = {Springer},
title = {{Strategy synthesis for multi-dimensional quantitative objectives}},
doi = {10.1007/s00236-013-0182-6},
volume = {51},
year = {2014},
}
@inproceedings{2905,
abstract = {Persistent homology is a recent grandchild of homology that has found use in
science and engineering as well as in mathematics. This paper surveys the method as well
as the applications, neglecting completeness in favor of highlighting ideas and directions.},
author = {Edelsbrunner, Herbert and Morozovy, Dmitriy},
location = {Kraków, Poland},
pages = {31 -- 50},
publisher = {European Mathematical Society Publishing House},
title = {{Persistent homology: Theory and practice}},
doi = {10.4171/120-1/3},
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{8044,
abstract = {Many questions concerning models in quantum mechanics require a detailed analysis of the spectrum of the corresponding Hamiltonian, a linear operator on a suitable Hilbert space. Of particular relevance for an understanding of the low-temperature properties of a system is the structure of the excitation spectrum, which is the part of the spectrum close to the spectral bottom. We present recent progress on this question for bosonic many-body quantum systems with weak two-body interactions. Such system are currently of great interest, due to their experimental realization in ultra-cold atomic gases. We investigate the accuracy of the Bogoliubov approximations, which predicts that the low-energy spectrum is made up of sums of elementary excitations, with linear dispersion law at low momentum. The latter property is crucial for the superfluid behavior the system.},
author = {Seiringer, Robert},
booktitle = {Proceeding of the International Congress of Mathematicans},
isbn = {9788961058063},
location = {Seoul, South Korea},
pages = {1175--1194},
publisher = {Kyung Moon SA},
title = {{Structure of the excitation spectrum for many-body quantum systems}},
volume = {3},
year = {2014},
}
@inproceedings{1702,
abstract = {In this paper we present INTERHORN, a solver for recursion-free Horn clauses. The main application domain of INTERHORN lies in solving interpolation problems arising in software verification. We show how a range of interpolation problems, including path, transition, nested, state/transition and well-founded interpolation can be handled directly by INTERHORN. By detailing these interpolation problems and their Horn clause representations, we hope to encourage the emergence of a common back-end interpolation interface useful for diverse verification tools.},
author = {Gupta, Ashutosh and Popeea, Corneliu and Rybalchenko, Andrey},
booktitle = {Electronic Proceedings in Theoretical Computer Science, EPTCS},
location = {Vienna, Austria},
pages = {31 -- 38},
publisher = {Open Publishing},
title = {{Generalised interpolation by solving recursion free-horn clauses}},
doi = {10.4204/EPTCS.169.5},
volume = {169},
year = {2014},
}
@article{1733,
abstract = {The classical (boolean) notion of refinement for behavioral interfaces of system components is the alternating refinement preorder. In this paper, we define a distance for interfaces, called interface simulation distance. It makes the alternating refinement preorder quantitative by, intuitively, tolerating errors (while counting them) in the alternating simulation game. We show that the interface simulation distance satisfies the triangle inequality, that the distance between two interfaces does not increase under parallel composition with a third interface, that the distance between two interfaces can be bounded from above and below by distances between abstractions of the two interfaces, and how to synthesize an interface from incompatible requirements. We illustrate the framework, and the properties of the distances under composition of interfaces, with two case studies.},
author = {Cerny, Pavol and Chmelik, Martin and Henzinger, Thomas A and Radhakrishna, Arjun},
journal = {Theoretical Computer Science},
number = {3},
pages = {348 -- 363},
publisher = {Elsevier},
title = {{Interface simulation distances}},
doi = {10.1016/j.tcs.2014.08.019},
volume = {560},
year = {2014},
}
@article{1761,
abstract = {Metal silicides formed by means of thermal annealing processes are employed as contact materials in microelectronics. Control of the structure of silicide/silicon interfaces becomes a critical issue when the characteristic size of the device is reduced below a few tens of nanometers. Here, we report on silicide clustering occurring within the channel of PtSi/Si/PtSi Schottky-barrier transistors. This phenomenon is investigated through atomistic simulations and low-temperature resonant-tunneling spectroscopy. Our results provide evidence for the segregation of a PtSi cluster with a diameter of a few nanometers from the silicide contact. The cluster acts as a metallic quantum dot giving rise to distinct signatures of quantum transport through its discrete energy states.},
author = {Mongillo, Massimo and Spathis, Panayotis N and Georgios Katsaros and De Franceschi, Silvano and Gentile, Pascal and Rurali, Riccardo and Cartoixà, Xavier},
journal = {Physical Review X},
number = {4},
publisher = {American Physical Society},
title = {{PtSi clustering in silicon probed by transport spectroscopy}},
doi = {10.1103/PhysRevX.3.041025},
volume = {3},
year = {2014},
}
@article{1816,
abstract = {Watermarking techniques for vector graphics dislocate vertices in order to embed imperceptible, yet detectable, statistical features into the input data. The embedding process may result in a change of the topology of the input data, e.g., by introducing self-intersections, which is undesirable or even disastrous for many applications. In this paper we present a watermarking framework for two-dimensional vector graphics that employs conventional watermarking techniques but still provides the guarantee that the topology of the input data is preserved. The geometric part of this framework computes so-called maximum perturbation regions (MPR) of vertices. We propose two efficient algorithms to compute MPRs based on Voronoi diagrams and constrained triangulations. Furthermore, we present two algorithms to conditionally correct the watermarked data in order to increase the watermark embedding capacity and still guarantee topological correctness. While we focus on the watermarking of input formed by straight-line segments, one of our approaches can also be extended to circular arcs. We conclude the paper by demonstrating and analyzing the applicability of our framework in conjunction with two well-known watermarking techniques.},
author = {Huber, Stefan and Held, Martin and Meerwald, Peter and Kwitt, Roland},
journal = {International Journal of Computational Geometry and Applications},
number = {1},
pages = {61 -- 86},
publisher = {World Scientific Publishing},
title = {{Topology-preserving watermarking of vector graphics}},
doi = {10.1142/S0218195914500034},
volume = {24},
year = {2014},
}
@article{1821,
abstract = {We review recent progress towards a rigorous understanding of the Bogoliubov approximation for bosonic quantum many-body systems. We focus, in particular, on the excitation spectrum of a Bose gas in the mean-field (Hartree) limit. A list of open problems will be discussed at the end.},
author = {Seiringer, Robert},
journal = {Journal of Mathematical Physics},
number = {7},
publisher = {American Institute of Physics},
title = {{Bose gases, Bose-Einstein condensation, and the Bogoliubov approximation}},
doi = {10.1063/1.4881536},
volume = {55},
year = {2014},
}
@article{1842,
abstract = {We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on 2n vertices are bounded by O(n3) and O(n10), in the convex and general case, respectively. We then apply similar methods to prove an (Formula presented.) upper bound on the Ramsey number of a path with n ordered vertices.},
author = {Cibulka, Josef and Gao, Pu and Krcál, Marek and Valla, Tomáš and Valtr, Pavel},
journal = {Discrete & Computational Geometry},
number = {1},
pages = {64 -- 79},
publisher = {Springer},
title = {{On the geometric ramsey number of outerplanar graphs}},
doi = {10.1007/s00454-014-9646-x},
volume = {53},
year = {2014},
}
@article{1844,
abstract = {Local protein interactions ("molecular context" effects) dictate amino acid replacements and can be described in terms of site-specific, energetic preferences for any different amino acid. It has been recently debated whether these preferences remain approximately constant during evolution or whether, due to coevolution of sites, they change strongly. Such research highlights an unresolved and fundamental issue with far-reaching implications for phylogenetic analysis and molecular evolution modeling. Here, we take advantage of the recent availability of phenotypically supported laboratory resurrections of Precambrian thioredoxins and β-lactamases to experimentally address the change of site-specific amino acid preferences over long geological timescales. Extensive mutational analyses support the notion that evolutionary adjustment to a new amino acid may occur, but to a large extent this is insufficient to erase the primitive preference for amino acid replacements. Generally, site-specific amino acid preferences appear to remain conserved throughout evolutionary history despite local sequence divergence. We show such preference conservation to be readily understandable in molecular terms and we provide crystallographic evidence for an intriguing structural-switch mechanism: Energetic preference for an ancestral amino acid in a modern protein can be linked to reorganization upon mutation to the ancestral local structure around the mutated site. Finally, we point out that site-specific preference conservation naturally leads to one plausible evolutionary explanation for the existence of intragenic global suppressor mutations.},
author = {Risso, Valeria and Manssour Triedo, Fadia and Delgado Delgado, Asuncion and Arco, Rocio and Barroso Deljesús, Alicia and Inglés Prieto, Álvaro and Godoy Ruiz, Raquel and Gavira, Josè and Gaucher, Eric and Ibarra Molero, Beatriz and Sánchez Ruiz, Jose},
journal = {Molecular Biology and Evolution},
number = {2},
pages = {440 -- 455},
publisher = {Oxford University Press},
title = {{Mutational studies on resurrected ancestral proteins reveal conservation of site-specific amino acid preferences throughout evolutionary history}},
doi = {10.1093/molbev/msu312},
volume = {32},
year = {2014},
}
@article{1852,
abstract = {To control morphogenesis, molecular regulatory networks have to interfere with the mechanical properties of the individual cells of developing organs and tissues, but how this is achieved is not well known. We study this issue here in the shoot meristem of higher plants, a group of undifferentiated cells where complex changes in growth rates and directions lead to the continuous formation of new organs [1, 2]. Here, we show that the plant hormone auxin plays an important role in this process via a dual, local effect on the extracellular matrix, the cell wall, which determines cell shape. Our study reveals that auxin not only causes a limited reduction in wall stiffness but also directly interferes with wall anisotropy via the regulation of cortical microtubule dynamics. We further show that to induce growth isotropy and organ outgrowth, auxin somehow interferes with the cortical microtubule-ordering activity of a network of proteins, including AUXIN BINDING PROTEIN 1 and KATANIN 1. Numerical simulations further indicate that the induced isotropy is sufficient to amplify the effects of the relatively minor changes in wall stiffness to promote organogenesis and the establishment of new growth axes in a robust manner.},
author = {Sassi, Massimiliano and Ali, Olivier and Boudon, Frédéric and Cloarec, Gladys and Abad, Ursula and Cellier, Coralie and Chen, Xu and Gilles, Benjamin and Milani, Pascale and Friml, Jirí and Vernoux, Teva and Godin, Christophe and Hamant, Olivier and Traas, Jan},
journal = {Current Biology},
number = {19},
pages = {2335 -- 2342},
publisher = {Cell Press},
title = {{An auxin-mediated shift toward growth isotropy promotes organ formation at the shoot meristem in Arabidopsis}},
doi = {10.1016/j.cub.2014.08.036},
volume = {24},
year = {2014},
}
@article{1854,
abstract = {In this paper, we present a method for non-rigid, partial shape matching in vector graphics. Given a user-specified query region in a 2D shape, similar regions are found, even if they are non-linearly distorted. Furthermore, a non-linear mapping is established between the query regions and these matches, which allows the automatic transfer of editing operations such as texturing. This is achieved by a two-step approach. First, pointwise correspondences between the query region and the whole shape are established. The transformation parameters of these correspondences are registered in an appropriate transformation space. For transformations between similar regions, these parameters form surfaces in transformation space, which are extracted in the second step of our method. The extracted regions may be related to the query region by a non-rigid transform, enabling non-rigid shape matching. In this paper, we present a method for non-rigid, partial shape matching in vector graphics. Given a user-specified query region in a 2D shape, similar regions are found, even if they are non-linearly distorted. Furthermore, a non-linear mapping is established between the query regions and these matches, which allows the automatic transfer of editing operations such as texturing. This is achieved by a two-step approach. First, pointwise correspondences between the query region and the whole shape are established. The transformation parameters of these correspondences are registered in an appropriate transformation space. For transformations between similar regions, these parameters form surfaces in transformation space, which are extracted in the second step of our method. The extracted regions may be related to the query region by a non-rigid transform, enabling non-rigid shape matching.},
author = {Guerrero, Paul and Auzinger, Thomas and Wimmer, Michael and Jeschke, Stefan},
journal = {Computer Graphics Forum},
number = {1},
pages = {239 -- 252},
publisher = {Wiley},
title = {{Partial shape matching using transformation parameter similarity}},
doi = {10.1111/cgf.12509},
volume = {34},
year = {2014},
}
@article{1862,
abstract = {The prominent and evolutionarily ancient role of the plant hormone auxin is the regulation of cell expansion. Cell expansion requires ordered arrangement of the cytoskeleton but molecular mechanisms underlying its regulation by signalling molecules including auxin are unknown. Here we show in the model plant Arabidopsis thaliana that in elongating cells exogenous application of auxin or redistribution of endogenous auxin induces very rapid microtubule re-orientation from transverse to longitudinal, coherent with the inhibition of cell expansion. This fast auxin effect requires auxin binding protein 1 (ABP1) and involves a contribution of downstream signalling components such as ROP6 GTPase, ROP-interactive protein RIC1 and the microtubule-severing protein katanin. These components are required for rapid auxin-and ABP1-mediated re-orientation of microtubules to regulate cell elongation in roots and dark-grown hypocotyls as well as asymmetric growth during gravitropic responses.},
author = {Chen, Xu and Grandont, Laurie and Li, Hongjiang and Hauschild, Robert and Paque, Sébastien and Abuzeineh, Anas and Rakusová, Hana and Benková, Eva and Perrot Rechenmann, Catherine and Friml, Jirí},
journal = {Nature},
number = {729},
pages = {90 -- 93},
publisher = {Nature Publishing Group},
title = {{Inhibition of cell expansion by rapid ABP1-mediated auxin effect on microtubules}},
doi = {10.1038/nature13889},
volume = {516},
year = {2014},
}
@inproceedings{1870,
abstract = {We investigate the problem of checking if a finite-state transducer is robust to uncertainty in its input. Our notion of robustness is based on the analytic notion of Lipschitz continuity - a transducer is K-(Lipschitz) robust if the perturbation in its output is at most K times the perturbation in its input. We quantify input and output perturbation using similarity functions. We show that K-robustness is undecidable even for deterministic transducers. We identify a class of functional transducers, which admits a polynomial time automata-theoretic decision procedure for K-robustness. This class includes Mealy machines and functional letter-to-letter transducers. We also study K-robustness of nondeterministic transducers. Since a nondeterministic transducer generates a set of output words for each input word, we quantify output perturbation using setsimilarity functions. We show that K-robustness of nondeterministic transducers is undecidable, even for letter-to-letter transducers. We identify a class of set-similarity functions which admit decidable K-robustness of letter-to-letter transducers.},
author = {Henzinger, Thomas A and Otop, Jan and Samanta, Roopsha},
booktitle = {Leibniz International Proceedings in Informatics, LIPIcs},
location = {Delhi, India},
pages = {431 -- 443},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Lipschitz robustness of finite-state transducers}},
doi = {10.4230/LIPIcs.FSTTCS.2014.431},
volume = {29},
year = {2014},
}
@inproceedings{1872,
abstract = {Extensionality axioms are common when reasoning about data collections, such as arrays and functions in program analysis, or sets in mathematics. An extensionality axiom asserts that two collections are equal if they consist of the same elements at the same indices. Using extensionality is often required to show that two collections are equal. A typical example is the set theory theorem (∀x)(∀y)x∪y = y ∪x. Interestingly, while humans have no problem with proving such set identities using extensionality, they are very hard for superposition theorem provers because of the calculi they use. In this paper we show how addition of a new inference rule, called extensionality resolution, allows first-order theorem provers to easily solve problems no modern first-order theorem prover can solve. We illustrate this by running the VAMPIRE theorem prover with extensionality resolution on a number of set theory and array problems. Extensionality resolution helps VAMPIRE to solve problems from the TPTP library of first-order problems that were never solved before by any prover.},
author = {Gupta, Ashutosh and Kovács, Laura and Kragl, Bernhard and Voronkov, Andrei},
booktitle = {ATVA 2014},
editor = {Cassez, Franck and Raskin, Jean-François},
location = {Sydney, Australia},
pages = {185 -- 200},
publisher = {Springer},
title = {{Extensional crisis and proving identity}},
doi = {10.1007/978-3-319-11936-6_14},
volume = {8837},
year = {2014},
}
@inproceedings{1875,
abstract = {We present a formal framework for repairing infinite-state, imperative, sequential programs, with (possibly recursive) procedures and multiple assertions; the framework can generate repaired programs by modifying the original erroneous program in multiple program locations, and can ensure the readability of the repaired program using user-defined expression templates; the framework also generates a set of inductive assertions that serve as a proof of correctness of the repaired program. As a step toward integrating programmer intent and intuition in automated program repair, we present a cost-aware formulation - given a cost function associated with permissible statement modifications, the goal is to ensure that the total program modification cost does not exceed a given repair budget. As part of our predicate abstractionbased solution framework, we present a sound and complete algorithm for repair of Boolean programs. We have developed a prototype tool based on SMT solving and used it successfully to repair diverse errors in benchmark C programs.},
author = {Samanta, Roopsha and Olivo, Oswaldo and Allen, Emerson},
editor = {Müller-Olm, Markus and Seidl, Helmut},
location = {Munich, Germany},
pages = {268 -- 284},
publisher = {Springer},
title = {{Cost-aware automatic program repair}},
doi = {10.1007/978-3-319-10936-7_17},
volume = {8723},
year = {2014},
}
@article{1876,
abstract = {We study densities of functionals over uniformly bounded triangulations of a Delaunay set of vertices, and prove that the minimum is attained for the Delaunay triangulation if this is the case for finite sets.},
author = {Dolbilin, Nikolai and Edelsbrunner, Herbert and Glazyrin, Alexey and Musin, Oleg},
journal = {Moscow Mathematical Journal},
number = {3},
pages = {491 -- 504},
publisher = {Independent University of Moscow},
title = {{Functionals on triangulations of delaunay sets}},
volume = {14},
year = {2014},
}
@article{1886,
abstract = {Information processing in the sensory periphery is shaped by natural stimulus statistics. In the periphery, a transmission bottleneck constrains performance; thus efficient coding implies that natural signal components with a predictably wider range should be compressed. In a different regime—when sampling limitations constrain performance—efficient coding implies that more resources should be allocated to informative features that are more variable. We propose that this regime is relevant for sensory cortex when it extracts complex features from limited numbers of sensory samples. To test this prediction, we use central visual processing as a model: we show that visual sensitivity for local multi-point spatial correlations, described by dozens of independently-measured parameters, can be quantitatively predicted from the structure of natural images. This suggests that efficient coding applies centrally, where it extends to higher-order sensory features and operates in a regime in which sensitivity increases with feature variability.},
author = {Hermundstad, Ann and Briguglio, John and Conte, Mary and Victor, Jonathan and Balasubramanian, Vijay and Tkacik, Gasper},
journal = {eLife},
number = {November},
publisher = {eLife Sciences Publications},
title = {{Variance predicts salience in central sensory processing}},
doi = {10.7554/eLife.03722},
year = {2014},
}