@article{1576,
abstract = {Gene expression is controlled primarily by interactions between transcription factor proteins (TFs) and the regulatory DNA sequence, a process that can be captured well by thermodynamic models of regulation. These models, however, neglect regulatory crosstalk: the possibility that noncognate TFs could initiate transcription, with potentially disastrous effects for the cell. Here, we estimate the importance of crosstalk, suggest that its avoidance strongly constrains equilibrium models of TF binding, and propose an alternative nonequilibrium scheme that implements kinetic proofreading to suppress erroneous initiation. This proposal is consistent with the observed covalent modifications of the transcriptional apparatus and predicts increased noise in gene expression as a trade-off for improved specificity. Using information theory, we quantify this trade-off to find when optimal proofreading architectures are favored over their equilibrium counterparts. Such architectures exhibit significant super-Poisson noise at low expression in steady state.},
author = {Cepeda Humerez, Sarah A and Rieckh, Georg and Tkacik, Gasper},
journal = {Physical Review Letters},
number = {24},
publisher = {American Physical Society},
title = {{Stochastic proofreading mechanism alleviates crosstalk in transcriptional regulation}},
doi = {10.1103/PhysRevLett.115.248101},
volume = {115},
year = {2015},
}
@article{1577,
abstract = {Contrary to the pattern seen in mammalian sex chromosomes, where most Y-linked genes have X-linked homologs, the Drosophila X and Y chromosomes appear to be unrelated. Most of the Y-linked genes have autosomal paralogs, so autosome-to-Y transposition must be the main source of Drosophila Y-linked genes. Here we show how these genes were acquired. We found a previously unidentified gene (flagrante delicto Y, FDY) that originated from a recent duplication of the autosomal gene vig2 to the Y chromosome of Drosophila melanogaster. Four contiguous genes were duplicated along with vig2, but they became pseudogenes through the accumulation of deletions and transposable element insertions, whereas FDY remained functional, acquired testis-specific expression, and now accounts for ∼20% of the vig2-like mRNA in testis. FDY is absent in the closest relatives of D. melanogaster, and DNA sequence divergence indicates that the duplication to the Y chromosome occurred ∼2 million years ago. Thus, FDY provides a snapshot of the early stages of the establishment of a Y-linked gene and demonstrates how the Drosophila Y has been accumulating autosomal genes.},
author = {Carvalho, Antonio and Vicoso, Beatriz and Russo, Claudia and Swenor, Bonnielin and Clark, Andrew},
journal = {PNAS},
number = {40},
pages = {12450 -- 12455},
publisher = {National Academy of Sciences},
title = {{Birth of a new gene on the Y chromosome of Drosophila melanogaster}},
doi = {10.1073/pnas.1516543112},
volume = {112},
year = {2015},
}
@article{1579,
abstract = {We show that the Galois group of any Schubert problem involving lines in projective space contains the alternating group. This constitutes the largest family of enumerative problems whose Galois groups have been largely determined. Using a criterion of Vakil and a special position argument due to Schubert, our result follows from a particular inequality among Kostka numbers of two-rowed tableaux. In most cases, a combinatorial injection proves the inequality. For the remaining cases, we use the Weyl integral formulas to obtain an integral formula for these Kostka numbers. This rewrites the inequality as an integral, which we estimate to establish the inequality.},
author = {Brooks, Christopher and Martin Del Campo Sanchez, Abraham and Sottile, Frank},
journal = {Transactions of the American Mathematical Society},
number = {6},
pages = {4183 -- 4206},
publisher = {American Mathematical Society},
title = {{Galois groups of Schubert problems of lines are at least alternating}},
doi = {10.1090/S0002-9947-2014-06192-8},
volume = {367},
year = {2015},
}
@article{1580,
abstract = {Synapsins (Syns) are an evolutionarily conserved family of presynaptic proteins crucial for the fine-tuning of synaptic function. A large amount of experimental evidences has shown that Syns are involved in the development of epileptic phenotypes and several mutations in Syn genes have been associated with epilepsy in humans and animal models. Syn mutations induce alterations in circuitry and neurotransmitter release, differentially affecting excitatory and inhibitory synapses, thus causing an excitation/inhibition imbalance in network excitability toward hyperexcitability that may be a determinant with regard to the development of epilepsy. Another approach to investigate epileptogenic mechanisms is to understand how silencing Syn affects the cellular behavior of single neurons and is associated with the hyperexcitable phenotypes observed in epilepsy. Here, we examined the functional effects of antisense-RNA inhibition of Syn expression on individually identified and isolated serotonergic cells of the Helix land snail. We found that Helix synapsin silencing increases cell excitability characterized by a slightly depolarized resting membrane potential, decreases the rheobase, reduces the threshold for action potential (AP) firing and increases the mean and instantaneous firing rates, with respect to control cells. The observed increase of Ca2+ and BK currents in Syn-silenced cells seems to be related to changes in the shape of the AP waveform. These currents sustain the faster spiking in Syn-deficient cells by increasing the after hyperpolarization and limiting the Na+ and Ca2+ channel inactivation during repetitive firing. This in turn speeds up the depolarization phase by reaching the AP threshold faster. Our results provide evidence that Syn silencing increases intrinsic cell excitability associated with increased Ca2+ and Ca2+-dependent BK currents in the absence of excitatory or inhibitory inputs.},
author = {Brenes, Oscar and Vandael, David H and Carbone, Emilio and Montarolo, Pier and Ghirardi, Mirella},
journal = {Neuroscience},
pages = {430 -- 443},
publisher = {Elsevier},
title = {{Knock-down of synapsin alters cell excitability and action potential waveform by potentiating BK and voltage gated Ca2 currents in Helix serotonergic neurons}},
doi = {10.1016/j.neuroscience.2015.10.046},
volume = {311},
year = {2015},
}
@article{1582,
abstract = {We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.},
author = {Biedl, Therese and Held, Martin and Huber, Stefan and Kaaser, Dominik and Palfrader, Peter},
journal = {Computational Geometry: Theory and Applications},
number = {2},
pages = {120 -- 133},
publisher = {Elsevier},
title = {{Weighted straight skeletons in the plane}},
doi = {10.1016/j.comgeo.2014.08.006},
volume = {48},
year = {2015},
}
@article{1583,
abstract = {We study the characteristics of straight skeletons of monotone polygonal chains and use them to devise an algorithm for computing positively weighted straight skeletons of monotone polygons. Our algorithm runs in O(nlogn) time and O(n) space, where n denotes the number of vertices of the polygon.},
author = {Biedl, Therese and Held, Martin and Huber, Stefan and Kaaser, Dominik and Palfrader, Peter},
journal = {Information Processing Letters},
number = {2},
pages = {243 -- 247},
publisher = {Elsevier},
title = {{A simple algorithm for computing positively weighted straight skeletons of monotone polygons}},
doi = {10.1016/j.ipl.2014.09.021},
volume = {115},
year = {2015},
}
@article{1584,
abstract = {We investigate weighted straight skeletons from a geometric, graph-theoretical, and combinatorial point of view. We start with a thorough definition and shed light on some ambiguity issues in the procedural definition. We investigate the geometry, combinatorics, and topology of faces and the roof model, and we discuss in which cases a weighted straight skeleton is connected. Finally, we show that the weighted straight skeleton of even a simple polygon may be non-planar and may contain cycles, and we discuss under which restrictions on the weights and/or the input polygon the weighted straight skeleton still behaves similar to its unweighted counterpart. In particular, we obtain a non-procedural description and a linear-time construction algorithm for the straight skeleton of strictly convex polygons with arbitrary weights.},
author = {Biedl, Therese and Held, Martin and Huber, Stefan and Kaaser, Dominik and Palfrader, Peter},
journal = {Computational Geometry: Theory and Applications},
number = {5},
pages = {429 -- 442},
publisher = {Elsevier},
title = {{Reprint of: Weighted straight skeletons in the plane}},
doi = {10.1016/j.comgeo.2015.01.004},
volume = {48},
year = {2015},
}
@article{1587,
abstract = {We investigate the quantum interference shifts between energetically close states, where the state structure is observed by laser spectroscopy. We report a compact and analytical expression that models the quantum interference induced shift for any admixture of circular polarization of the incident laser and angle of observation. An experimental scenario free of quantum interference can thus be predicted with this formula. Although this study is exemplified here for muonic deuterium, it can be applied to any other laser spectroscopy measurement of ns-n′p frequencies of a nonrelativistic atomic system, via an ns→n′p→n′′s scheme.},
author = {Amaro, Pedro and Fratini, Filippo and Safari, Laleh and Antognini, Aldo and Indelicato, Paul and Pohl, Randolf and Santos, José},
journal = {Physical Review A - Atomic, Molecular, and Optical Physics},
number = {6},
publisher = {American Physical Society},
title = {{Quantum interference shifts in laser spectroscopy with elliptical polarization}},
doi = {10.1103/PhysRevA.92.062506},
volume = {92},
year = {2015},
}
@article{1589,
abstract = {We investigate the dynamics of ferrofluidic wavy vortex flows in the counter-rotating Taylor-Couette system, with a focus on wavy flows with a mixture of the dominant azimuthal modes. Without external magnetic field flows are stable and pro-grade with respect to the rotation of the inner cylinder. More complex behaviors can arise when an axial or a transverse magnetic field is applied. Depending on the direction and strength of the field, multi-stable wavy states and bifurcations can occur. We uncover the phenomenon of flow pattern reversal as the strength of the magnetic field is increased through a critical value. In between the regimes of pro-grade and retrograde flow rotations, standing waves with zero angular velocities can emerge. A striking finding is that, under a transverse magnetic field, a second reversal in the flow pattern direction can occur, where the flow pattern evolves into pro-grade rotation again from a retrograde state. Flow reversal is relevant to intriguing phenomena in nature such as geomagnetic reversal. Our results suggest that, in ferrofluids, flow pattern reversal can be induced by varying a magnetic field in a controlled manner, which can be realized in laboratory experiments with potential applications in the development of modern fluid devices.},
author = {Altmeyer, Sebastian and Do, Younghae and Lai, Ying},
journal = {Scientific Reports},
publisher = {Nature Publishing Group},
title = {{Magnetic field induced flow pattern reversal in a ferrofluidic Taylor-Couette system}},
doi = {10.1038/srep18589},
volume = {5},
year = {2015},
}
@inbook{1590,
abstract = {The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process. In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed.},
author = {Aichholzer, Oswin and Biedl, Therese and Hackl, Thomas and Held, Martin and Huber, Stefan and Palfrader, Peter and Vogtenhuber, Birgit},
booktitle = {Graph Drawing and Network Visualization},
location = {Los Angeles, CA, United States},
pages = {335 -- 347},
publisher = {Springer},
title = {{Representing directed trees as straight skeletons}},
doi = {10.1007/978-3-319-27261-0_28},
volume = {9411},
year = {2015},
}
@article{1591,
abstract = {Auxin participates in a multitude of developmental processes, as well as responses to environmental cues. Compared with other plant hormones, auxin exhibits a unique property, as it undergoes directional, cell-to-cell transport facilitated by plasma membrane-localized transport proteins. Among them, a prominent role has been ascribed to the PIN family of auxin efflux facilitators. PIN proteins direct polar auxin transport on account of their asymmetric subcellular localizations. In this review, we provide an overview of the multiple developmental roles of PIN proteins, including the atypical endoplasmic reticulum-localized members of the family, and look at the family from an evolutionary perspective. Next, we cover the cell biological and molecular aspects of PIN function, in particular the establishment of their polar subcellular localization. Hormonal and environmental inputs into the regulation of PIN action are summarized as well.},
author = {Adamowski, Maciek and Friml, Jirí},
journal = {Plant Cell},
number = {1},
pages = {20 -- 32},
publisher = {American Society of Plant Biologists},
title = {{PIN-dependent auxin transport: Action, regulation, and evolution}},
doi = {10.1105/tpc.114.134874},
volume = {27},
year = {2015},
}
@article{1593,
abstract = {Plants are sessile organisms that are permanently restricted to their site of germination. To compensate for their lack of mobility, plants evolved unique mechanisms enabling them to rapidly react to ever changing environmental conditions and flexibly adapt their postembryonic developmental program. A prominent demonstration of this developmental plasticity is their ability to bend organs in order to reach the position most optimal for growth and utilization of light, nutrients, and other resources. Shortly after germination, dicotyledonous seedlings form a bended structure, the so-called apical hook, to protect the delicate shoot meristem and cotyledons from damage when penetrating through the soil. Upon perception of a light stimulus, the apical hook rapidly opens and the photomorphogenic developmental program is activated. After germination, plant organs are able to align their growth with the light source and adopt the most favorable orientation through bending, in a process named phototropism. On the other hand, when roots and shoots are diverted from their upright orientation, they immediately detect a change in the gravity vector and bend to maintain a vertical growth direction. Noteworthy, despite the diversity of external stimuli perceived by different plant organs, all plant tropic movements share a common mechanistic basis: differential cell growth. In our review, we will discuss the molecular principles underlying various tropic responses with the focus on mechanisms mediating the perception of external signals, transduction cascades and downstream responses that regulate differential cell growth and consequently, organ bending. In particular, we highlight common and specific features of regulatory pathways in control of the bending of organs and a role for the plant hormone auxin as a key regulatory component.},
author = {Žádníková, Petra and Smet, Dajo and Zhu, Qiang and Van Der Straeten, Dominique and Benková, Eva},
journal = {Frontiers in Plant Science},
number = {4},
publisher = {Frontiers Research Foundation},
title = {{Strategies of seedlings to overcome their sessile nature: Auxin in mobility control}},
doi = {10.3389/fpls.2015.00218},
volume = {6},
year = {2015},
}
@inproceedings{1595,
abstract = {A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, . . . , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing- free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth.},
author = {Fulek, Radoslav and Pelsmajer, Michael and Schaefer, Marcus},
location = {Los Angeles, CA, USA},
pages = {99 -- 110},
publisher = {Springer},
title = {{Hanani-Tutte for radial planarity}},
doi = {10.1007/978-3-319-27261-0_9},
volume = {9411},
year = {2015},
}
@inproceedings{1596,
abstract = {Let C={C1,...,Cn} denote a collection of translates of a regular convex k-gon in the plane with the stacking order. The collection C forms a visibility clique if for everyi < j the intersection Ci and (Ci ∩ Cj)\⋃i<l<jCl =∅.elements that are stacked between them, i.e., We show that if C forms a visibility clique its size is bounded from above by O(k4) thereby improving the upper bound of 22k from the aforementioned paper. We also obtain an upper bound of 22(k/2)+2 on the size of a visibility clique for homothetes of a convex (not necessarily regular) k-gon.},
author = {Fulek, Radoslav and Radoičić, Radoš},
location = {Los Angeles, CA, United States},
pages = {373 -- 379},
publisher = {Springer},
title = {{Vertical visibility among parallel polygons in three dimensions}},
doi = {10.1007/978-3-319-27261-0_31},
volume = {9411},
year = {2015},
}
@article{1598,
abstract = {We consider Markov decision processes (MDPs) with specifications given as Büchi (liveness) objectives, and examine the problem of computing the set of almost-sure winning vertices such that the objective can be ensured with probability 1 from these vertices. We study for the first time the average-case complexity of the classical algorithm for computing the set of almost-sure winning vertices for MDPs with Büchi objectives. Our contributions are as follows: First, we show that for MDPs with constant out-degree the expected number of iterations is at most logarithmic and the average-case running time is linear (as compared to the worst-case linear number of iterations and quadratic time complexity). Second, for the average-case analysis over all MDPs we show that the expected number of iterations is constant and the average-case running time is linear (again as compared to the worst-case linear number of iterations and quadratic time complexity). Finally we also show that when all MDPs are equally likely, the probability that the classical algorithm requires more than a constant number of iterations is exponentially small.},
author = {Chatterjee, Krishnendu and Joglekar, Manas and Shah, Nisarg},
journal = {Theoretical Computer Science},
number = {3},
pages = {71 -- 89},
publisher = {Elsevier},
title = {{Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives}},
doi = {10.1016/j.tcs.2015.01.050},
volume = {573},
year = {2015},
}
@inproceedings{1601,
abstract = {We propose a flexible exchange format for ω-automata, as typically used in formal verification, and implement support for it in a range of established tools. Our aim is to simplify the interaction of tools, helping the research community to build upon other people’s work. A key feature of the format is the use of very generic acceptance conditions, specified by Boolean combinations of acceptance primitives, rather than being limited to common cases such as Büchi, Streett, or Rabin. Such flexibility in the choice of acceptance conditions can be exploited in applications, for example in probabilistic model checking, and furthermore encourages the development of acceptance-agnostic tools for automata manipulations. The format allows acceptance conditions that are either state-based or transition-based, and also supports alternating automata.},
author = {Babiak, Tomáš and Blahoudek, František and Duret Lutz, Alexandre and Klein, Joachim and Kretinsky, Jan and Mueller, Daniel and Parker, David and Strejček, Jan},
location = {San Francisco, CA, United States},
pages = {479 -- 486},
publisher = {Springer},
title = {{The Hanoi omega-automata format}},
doi = {10.1007/978-3-319-21690-4_31},
volume = {9206},
year = {2015},
}
@article{1602,
abstract = {Interprocedural analysis is at the heart of numerous applications in programming languages, such as alias analysis, constant propagation, etc. Recursive state machines (RSMs) are standard models for interprocedural analysis. We consider a general framework with RSMs where the transitions are labeled from a semiring, and path properties are algebraic with semiring operations. RSMs with algebraic path properties can model interprocedural dataflow analysis problems, the shortest path problem, the most probable path problem, etc. The traditional algorithms for interprocedural analysis focus on path properties where the starting point is fixed as the entry point of a specific method. In this work, we consider possible multiple queries as required in many applications such as in alias analysis. The study of multiple queries allows us to bring in a very important algorithmic distinction between the resource usage of the one-time preprocessing vs for each individual query. The second aspect that we consider is that the control flow graphs for most programs have constant treewidth. Our main contributions are simple and implementable algorithms that supportmultiple queries for algebraic path properties for RSMs that have constant treewidth. Our theoretical results show that our algorithms have small additional one-time preprocessing, but can answer subsequent queries significantly faster as compared to the current best-known solutions for several important problems, such as interprocedural reachability and shortest path. We provide a prototype implementation for interprocedural reachability and intraprocedural shortest path that gives a significant speed-up on several benchmarks.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Pavlogiannis, Andreas and Goyal, Prateesh},
journal = {ACM SIGPLAN Notices},
location = {Mumbai, India},
number = {1},
pages = {97 -- 109},
publisher = {ACM},
title = {{Faster algorithms for algebraic path properties in recursive state machines with constant treewidth}},
doi = {10.1145/2676726.2676979},
volume = {50},
year = {2015},
}
@inproceedings{1603,
abstract = {For deterministic systems, a counterexample to a property can simply be an error trace, whereas counterexamples in probabilistic systems are necessarily more complex. For instance, a set of erroneous traces with a sufficient cumulative probability mass can be used. Since these are too large objects to understand and manipulate, compact representations such as subchains have been considered. In the case of probabilistic systems with non-determinism, the situation is even more complex. While a subchain for a given strategy (or scheduler, resolving non-determinism) is a straightforward choice, we take a different approach. Instead, we focus on the strategy itself, and extract the most important decisions it makes, and present its succinct representation.
The key tools we employ to achieve this are (1) introducing a concept of importance of a state w.r.t. the strategy, and (2) learning using decision trees. There are three main consequent advantages of our approach. Firstly, it exploits the quantitative information on states, stressing the more important decisions. Secondly, it leads to a greater variability and degree of freedom in representing the strategies. Thirdly, the representation uses a self-explanatory data structure. In summary, our approach produces more succinct and more explainable strategies, as opposed to e.g. binary decision diagrams. Finally, our experimental results show that we can extract several rules describing the strategy even for very large systems that do not fit in memory, and based on the rules explain the erroneous behaviour.},
author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Chmelik, Martin and Fellner, Andreas and Kretinsky, Jan},
location = {San Francisco, CA, United States},
pages = {158 -- 177},
publisher = {Springer},
title = {{Counterexample explanation by learning small strategies in Markov decision processes}},
doi = {10.1007/978-3-319-21690-4_10},
volume = {9206},
year = {2015},
}
@inproceedings{1605,
abstract = {Multiaffine hybrid automata (MHA) represent a powerful formalism to model complex dynamical systems. This formalism is particularly suited for the representation of biological systems which often exhibit highly non-linear behavior. In this paper, we consider the problem of parameter identification for MHA. We present an abstraction of MHA based on linear hybrid automata, which can be analyzed by the SpaceEx model checker. This abstraction enables a precise handling of time-dependent properties. We demonstrate the potential of our approach on a model of a genetic regulatory network and a myocyte model.},
author = {Bogomolov, Sergiy and Schilling, Christian and Bartocci, Ezio and Batt, Grégory and Kong, Hui and Grosu, Radu},
location = {Haifa, Israel},
pages = {19 -- 35},
publisher = {Springer},
title = {{Abstraction-based parameter synthesis for multiaffine systems}},
doi = {10.1007/978-3-319-26287-1_2},
volume = {9434},
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},
}
@inproceedings{1609,
abstract = {The synthesis problem asks for the automatic construction of a system from its specification. In the traditional setting, the system is “constructed from scratch” rather than composed from reusable components. However, this is rare in practice, and almost every non-trivial software system relies heavily on the use of libraries of reusable components. Recently, Lustig and Vardi introduced dataflow and controlflow synthesis from libraries of reusable components. They proved that dataflow synthesis is undecidable, while controlflow synthesis is decidable. The problem of controlflow synthesis from libraries of probabilistic components was considered by Nain, Lustig and Vardi, and was shown to be decidable for qualitative analysis (that asks that the specification be satisfied with probability 1). Our main contribution for controlflow synthesis from probabilistic components is to establish better complexity bounds for the qualitative analysis problem, and to show that the more general quantitative problem is undecidable. For the qualitative analysis, we show that the problem (i) is EXPTIME-complete when the specification is given as a deterministic parity word automaton, improving the previously known 2EXPTIME upper bound; and (ii) belongs to UP ∩ coUP and is parity-games hard, when the specification is given directly as a parity condition on the components, improving the previously known EXPTIME upper bound.},
author = {Chatterjee, Krishnendu and Doyen, Laurent and Vardi, Moshe},
location = {Kyoto, Japan},
pages = {108 -- 120},
publisher = {Springer},
title = {{The complexity of synthesis from probabilistic components}},
doi = {10.1007/978-3-662-47666-6_9},
volume = {9135},
year = {2015},
}
@article{1611,
abstract = {Biosensors for signaling molecules allow the study of physiological processes by bringing together the fields of protein engineering, fluorescence imaging, and cell biology. Construction of genetically encoded biosensors generally relies on the availability of a binding "core" that is both specific and stable, which can then be combined with fluorescent molecules to create a sensor. However, binding proteins with the desired properties are often not available in nature and substantial improvement to sensors can be required, particularly with regard to their durability. Ancestral protein reconstruction is a powerful protein-engineering tool able to generate highly stable and functional proteins. In this work, we sought to establish the utility of ancestral protein reconstruction to biosensor development, beginning with the construction of an l-arginine biosensor. l-arginine, as the immediate precursor to nitric oxide, is an important molecule in many physiological contexts including brain function. Using a combination of ancestral reconstruction and circular permutation, we constructed a Förster resonance energy transfer (FRET) biosensor for l-arginine (cpFLIPR). cpFLIPR displays high sensitivity and specificity, with a Kd of ∼14 μM and a maximal dynamic range of 35%. Importantly, cpFLIPR was highly robust, enabling accurate l-arginine measurement at physiological temperatures. We established that cpFLIPR is compatible with two-photon excitation fluorescence microscopy and report l-arginine concentrations in brain tissue.},
author = {Whitfield, Jason and Zhang, William and Herde, Michel and Clifton, Ben and Radziejewski, Johanna and Janovjak, Harald L and Henneberger, Christian and Jackson, Colin},
journal = {Protein Science},
number = {9},
pages = {1412 -- 1422},
publisher = {Wiley},
title = {{Construction of a robust and sensitive arginine biosensor through ancestral protein reconstruction}},
doi = {10.1002/pro.2721},
volume = {24},
year = {2015},
}
@article{1614,
abstract = {GABAergic perisoma-inhibiting fast-spiking interneurons (PIIs) effectively control the activity of large neuron populations by their wide axonal arborizations. It is generally assumed that the output of one PII to its target cells is strong and rapid. Here, we show that, unexpectedly, both strength and time course of PII-mediated perisomatic inhibition change with distance between synaptically connected partners in the rodent hippocampus. Synaptic signals become weaker due to lower contact numbers and decay more slowly with distance, very likely resulting from changes in GABAA receptor subunit composition. When distance-dependent synaptic inhibition is introduced to a rhythmically active neuronal network model, randomly driven principal cell assemblies are strongly synchronized by the PIIs, leading to higher precision in principal cell spike times than in a network with uniform synaptic inhibition. },
author = {Strüber, Michael and Jonas, Peter M and Bartos, Marlene},
journal = {PNAS},
number = {4},
pages = {1220 -- 1225},
publisher = {National Academy of Sciences},
title = {{Strength and duration of perisomatic GABAergic inhibition depend on distance between synaptically connected cells}},
doi = {10.1073/pnas.1412996112},
volume = {112},
year = {2015},
}
@article{1615,
abstract = {Loss-of-function mutations in the synaptic adhesion protein Neuroligin-4 are among the most common genetic abnormalities associated with autism spectrum disorders, but little is known about the function of Neuroligin-4 and the consequences of its loss. We assessed synaptic and network characteristics in Neuroligin-4 knockout mice, focusing on the hippocampus as a model brain region with a critical role in cognition and memory, and found that Neuroligin-4 deletion causes subtle defects of the protein composition and function of GABAergic synapses in the hippocampal CA3 region. Interestingly, these subtle synaptic changes are accompanied by pronounced perturbations of γ-oscillatory network activity, which has been implicated in cognitive function and is altered in multiple psychiatric and neurodevelopmental disorders. Our data provide important insights into the mechanisms by which Neuroligin-4-dependent GABAergic synapses may contribute to autism phenotypes and indicate new strategies for therapeutic approaches.},
author = {Hammer, Matthieu and Krueger Burg, Dilja and Tuffy, Liam and Cooper, Benjamin and Taschenberger, Holger and Goswami, Sarit and Ehrenreich, Hannelore and Jonas, Peter M and Varoqueaux, Frederique and Rhee, Jeong and Brose, Nils},
journal = {Cell Reports},
number = {3},
pages = {516 -- 523},
publisher = {Cell Press},
title = {{Perturbed hippocampal synaptic inhibition and γ-oscillations in a neuroligin-4 knockout mouse model of autism}},
doi = {10.1016/j.celrep.2015.09.011},
volume = {13},
year = {2015},
}
@article{1618,
abstract = {CCL19 and CCL21 are chemokines involved in the trafficking of immune cells, particularly within the lymphatic system, through activation of CCR7. Concurrent expression of PSGL-1 and CCR7 in naive T-cells enhances recruitment of these cells to secondary lymphoid organs by CCL19 and CCL21. Here the solution structure of CCL19 is reported. It contains a canonical chemokine domain. Chemical shift mapping shows the N-termini of PSGL-1 and CCR7 have overlapping binding sites for CCL19 and binding is competitive. Implications for the mechanism of PSGL-1's enhancement of resting T-cell recruitment are discussed.},
author = {Veldkamp, Christopher and Kiermaier, Eva and Gabel Eissens, Skylar and Gillitzer, Miranda and Lippner, David and Disilvio, Frank and Mueller, Casey and Wantuch, Paeton and Chaffee, Gary and Famiglietti, Michael and Zgoba, Danielle and Bailey, Asha and Bah, Yaya and Engebretson, Samantha and Graupner, David and Lackner, Emily and Larosa, Vincent and Medeiros, Tysha and Olson, Michael and Phillips, Andrew and Pyles, Harley and Richard, Amanda and Schoeller, Scott and Touzeau, Boris and Williams, Larry and Sixt, Michael K and Peterson, Francis},
journal = {Biochemistry},
number = {27},
pages = {4163 -- 4166},
publisher = {ACS},
title = {{Solution structure of CCL19 and identification of overlapping CCR7 and PSGL-1 binding sites}},
doi = {10.1021/acs.biochem.5b00560},
volume = {54},
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{1623,
abstract = {Background
Photosynthetic cyanobacteria are attractive for a range of biotechnological applications including biofuel production. However, due to slow growth, screening of mutant libraries using microtiter plates is not feasible.
Results
We present a method for high-throughput, single-cell analysis and sorting of genetically engineered l-lactate-producing strains of Synechocystis sp. PCC6803. A microfluidic device is used to encapsulate single cells in picoliter droplets, assay the droplets for l-lactate production, and sort strains with high productivity. We demonstrate the separation of low- and high-producing reference strains, as well as enrichment of a more productive l-lactate-synthesizing population after UV-induced mutagenesis. The droplet platform also revealed population heterogeneity in photosynthetic growth and lactate production, as well as the presence of metabolically stalled cells.
Conclusions
The workflow will facilitate metabolic engineering and directed evolution studies and will be useful in studies of cyanobacteria biochemistry and physiology.
},
author = {Hammar, Petter and Angermayr, Andreas and Sjostrom, Staffan and Van Der Meer, Josefin and Hellingwerf, Klaas and Hudson, Elton and Joensson, Hakaan},
journal = {Biotechnology for Biofuels},
number = {1},
publisher = {BioMed Central},
title = {{Single-cell screening of photosynthetic growth and lactate production by cyanobacteria}},
doi = {10.1186/s13068-015-0380-2},
volume = {8},
year = {2015},
}
@article{1624,
abstract = {Population structure can facilitate evolution of cooperation. In a structured population, cooperators can form clusters which resist exploitation by defectors. Recently, it was observed that a shift update rule is an extremely strong amplifier of cooperation in a one dimensional spatial model. For the shift update rule, an individual is chosen for reproduction proportional to fecundity; the offspring is placed next to the parent; a random individual dies. Subsequently, the population is rearranged (shifted) until all individual cells are again evenly spaced out. For large population size and a one dimensional population structure, the shift update rule favors cooperation for any benefit-to-cost ratio greater than one. But every attempt to generalize shift updating to higher dimensions while maintaining its strong effect has failed. The reason is that in two dimensions the clusters are fragmented by the movements caused by rearranging the cells. Here we introduce the natural phenomenon of a repulsive force between cells of different types. After a birth and death event, the cells are being rearranged minimizing the overall energy expenditure. If the repulsive force is sufficiently high, shift becomes a strong promoter of cooperation in two dimensions.},
author = {Pavlogiannis, Andreas and Chatterjee, Krishnendu and Adlam, Ben and Nowak, Martin},
journal = {Scientific Reports},
publisher = {Nature Publishing Group},
title = {{Cellular cooperation with shift updating and repulsion}},
doi = {10.1038/srep17147},
volume = {5},
year = {2015},
}
@inproceedings{1628,
abstract = {We propose a method for fabricating deformable objects with spatially varying elasticity using 3D printing. Using a single, relatively stiff printer material, our method designs an assembly of smallscale microstructures that have the effect of a softer material at the object scale, with properties depending on the microstructure used in each part of the object. We build on work in the area of metamaterials, using numerical optimization to design tiled microstructures with desired properties, but with the key difference that our method designs families of related structures that can be interpolated to smoothly vary the material properties over a wide range. To create an object with spatially varying elastic properties, we tile the object's interior with microstructures drawn from these families, generating a different microstructure for each cell using an efficient algorithm to select compatible structures for neighboring cells. We show results computed for both 2D and 3D objects, validating several 2D and 3D printed structures using standard material tests as well as demonstrating various example applications.},
author = {Schumacher, Christian and Bickel, Bernd and Rys, Jan and Marschner, Steve and Daraio, Chiara and Gross, Markus},
location = {Los Angeles, CA, USA},
number = {4},
publisher = {ACM},
title = {{Microstructures to control elasticity in 3D printing}},
doi = {10.1145/2766926},
volume = {34},
year = {2015},
}
@inproceedings{1630,
abstract = {We present a method to learn and propagate shape placements in 2D polygonal scenes from a few examples provided by a user. The placement of a shape is modeled as an oriented bounding box. Simple geometric relationships between this bounding box and nearby scene polygons define a feature set for the placement. The feature sets of all example placements are then used to learn a probabilistic model over all possible placements and scenes. With this model, we can generate a new set of placements with similar geometric relationships in any given scene. We introduce extensions that enable propagation and generation of shapes in 3D scenes, as well as the application of a learned modeling session to large scenes without additional user interaction. These concepts allow us to generate complex scenes with thousands of objects with relatively little user interaction.},
author = {Guerrero, Paul and Jeschke, Stefan and Wimmer, Michael and Wonka, Peter},
location = {Los Angeles, CA, United States},
number = {4},
publisher = {ACM},
title = {{Learning shape placements by example}},
doi = {10.1145/2766933},
volume = {34},
year = {2015},
}
@inproceedings{1632,
abstract = {This paper presents a liquid simulation technique that enforces the incompressibility condition using a stream function solve instead of a pressure projection. Previous methods have used stream function techniques for the simulation of detailed single-phase flows, but a formulation for liquid simulation has proved elusive in part due to the free surface boundary conditions. In this paper, we introduce a stream function approach to liquid simulations with novel boundary conditions for free surfaces, solid obstacles, and solid-fluid coupling.
Although our approach increases the dimension of the linear system necessary to enforce incompressibility, it provides interesting and surprising benefits. First, the resulting flow is guaranteed to be divergence-free regardless of the accuracy of the solve. Second, our free-surface boundary conditions guarantee divergence-free motion even in the un-simulated air phase, which enables two-phase flow simulation by only computing a single phase. We implemented this method using a variant of FLIP simulation which only samples particles within a narrow band of the liquid surface, and we illustrate the effectiveness of our method for detailed two-phase flow simulations with complex boundaries, detailed bubble interactions, and two-way solid-fluid coupling.},
author = {Ando, Ryoichi and Thuerey, Nils and Wojtan, Christopher J},
location = {Los Angeles, CA, USA},
number = {4},
publisher = {ACM},
title = {{A stream function solver for liquid simulations}},
doi = {10.1145/2766935},
volume = {34},
year = {2015},
}
@inproceedings{1633,
abstract = {We present a method for simulating brittle fracture under the assumptions of quasi-static linear elastic fracture mechanics (LEFM). Using the boundary element method (BEM) and Lagrangian crack-fronts, we produce highly detailed fracture surfaces. The computational cost of the BEM is alleviated by using a low-resolution mesh and interpolating the resulting stress intensity factors when propagating the high-resolution crack-front.
Our system produces physics-based fracture surfaces with high spatial and temporal resolution, taking spatial variation of material toughness and/or strength into account. It also allows for crack initiation to be handled separately from crack propagation, which is not only more reasonable from a physics perspective, but can also be used to control the simulation.
Separating the resolution of the crack-front from the resolution of the computational mesh increases the efficiency and therefore the amount of visual detail on the resulting fracture surfaces. The BEM also allows us to re-use previously computed blocks of the system matrix.},
author = {Hahn, David and Wojtan, Christopher J},
location = {Los Angeles, CA, United States},
number = {4},
publisher = {ACM},
title = {{High-resolution brittle fracture simulation with boundary elements}},
doi = {10.1145/2766896},
volume = {34},
year = {2015},
}
@inproceedings{1634,
abstract = {Simulating the delightful dynamics of soap films, bubbles, and foams has traditionally required the use of a fully three-dimensional many-phase Navier-Stokes solver, even though their visual appearance is completely dominated by the thin liquid surface. We depart from earlier work on soap bubbles and foams by noting that their dynamics are naturally described by a Lagrangian vortex sheet model in which circulation is the primary variable. This leads us to derive a novel circulation-preserving surface-only discretization of foam dynamics driven by surface tension on a non-manifold triangle mesh. We represent the surface using a mesh-based multimaterial surface tracker which supports complex bubble topology changes, and evolve the surface according to the ambient air flow induced by a scalar circulation field stored on the mesh. Surface tension forces give rise to a simple update rule for circulation, even at non-manifold Plateau borders, based on a discrete measure of signed scalar mean curvature. We further incorporate vertex constraints to enable the interaction of soap films with wires. The result is a method that is at once simple, robust, and efficient, yet able to capture an array of soap films behaviors including foam rearrangement, catenoid collapse, blowing bubbles, and double bubbles being pulled apart.},
author = {Da, Fang and Batty, Christopher and Wojtan, Christopher J and Grinspun, Eitan},
location = {Los Angeles, CA, United States},
number = {4},
publisher = {ACM},
title = {{Double bubbles sans toil and trouble: discrete circulation-preserving vortex sheets for soap films and foams}},
doi = {10.1145/2767003},
volume = {34},
year = {2015},
}
@article{1635,
abstract = {We calculate a Ricci curvature lower bound for some classical examples of random walks, namely, a chain on a slice of the n-dimensional discrete cube (the so-called Bernoulli-Laplace model) and the random transposition shuffle of the symmetric group of permutations on n letters.},
author = {Erbar, Matthias and Maas, Jan and Tetali, Prasad},
journal = {Annales de la faculté des sciences de Toulouse},
number = {4},
pages = {781 -- 800},
publisher = {Univ. Paul Sabatier},
title = {{Discrete Ricci curvature bounds for Bernoulli-Laplace and random transposition models}},
doi = {10.5802/afst.1464},
volume = {24},
year = {2015},
}
@inproceedings{1636,
abstract = {Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism R→ΓΓ between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a prominent research direction, especially for the fixed template CSPs where the right side ΓΓ is fixed and the left side R is unconstrained.
Far fewer results are known for the hybrid setting that restricts both sides simultaneously. It assumes that R belongs to a certain class of relational structures (called a structural restriction in this paper). We study which structural restrictions are effective, i.e. there exists a fixed template ΓΓ (from a certain class of languages) for which the problem is tractable when R is restricted, and NP-hard otherwise. We provide a characterization for structural restrictions that are closed under inverse homomorphisms. The criterion is based on the chromatic number of a relational structure defined in this paper; it generalizes the standard chromatic number of a graph.
As our main tool, we use the algebraic machinery developed for fixed template CSPs. To apply it to our case, we introduce a new construction called a “lifted language”. We also give a characterization for structural restrictions corresponding to minor-closed families of graphs, extend results to certain Valued CSPs (namely conservative valued languages), and state implications for (valued) CSPs with ordered variables and for the maximum weight independent set problem on some restricted families of graphs.},
author = {Kolmogorov, Vladimir and Rolinek, Michal and Takhanov, Rustem},
location = {Nagoya, Japan},
pages = {566 -- 577},
publisher = {Springer},
title = {{Effectiveness of structural restrictions for hybrid CSPs}},
doi = {10.1007/978-3-662-48971-0_48},
volume = {9472},
year = {2015},
}
@inproceedings{1637,
abstract = {An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. We study, assuming that P ≠ NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in {0, ∞} corresponds to ordinary CSPs, where one deals only with the feasibility issue and there is no optimization. This case is the subject of the Algebraic CSP Dichotomy Conjecture predicting for which constraint languages CSPs are tractable (i.e. solvable in polynomial time) and for which NP-hard. The case when all allowed functions take only finite values corresponds to finite-valued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Zivny. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e. the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs.},
author = {Kolmogorov, Vladimir and Krokhin, Andrei and Rolinek, Michal},
location = {Berkeley, CA, United States},
pages = {1246 -- 1258},
publisher = {IEEE},
title = {{The complexity of general-valued CSPs}},
doi = {10.1109/FOCS.2015.80},
year = {2015},
}
@article{1639,
abstract = {In this paper the optimal transport and the metamorphosis perspectives are combined. For a pair of given input images geodesic paths in the space of images are defined as minimizers of a resulting path energy. To this end, the underlying Riemannian metric measures the rate of transport cost and the rate of viscous dissipation. Furthermore, the model is capable to deal with strongly varying image contrast and explicitly allows for sources and sinks in the transport equations which are incorporated in the metric related to the metamorphosis approach by Trouvé and Younes. In the non-viscous case with source term existence of geodesic paths is proven in the space of measures. The proposed model is explored on the range from merely optimal transport to strongly dissipative dynamics. For this model a robust and effective variational time discretization of geodesic paths is proposed. This requires to minimize a discrete path energy consisting of a sum of consecutive image matching functionals. These functionals are defined on corresponding pairs of intensity functions and on associated pairwise matching deformations. Existence of time discrete geodesics is demonstrated. Furthermore, a finite element implementation is proposed and applied to instructive test cases and to real images. In the non-viscous case this is compared to the algorithm proposed by Benamou and Brenier including a discretization of the source term. Finally, the model is generalized to define discrete weighted barycentres with applications to textures and objects.},
author = {Maas, Jan and Rumpf, Martin and Schönlieb, Carola and Simon, Stefan},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis},
number = {6},
pages = {1745 -- 1769},
publisher = {EDP Sciences},
title = {{A generalized model for optimal transport of images including dissipation and density modulation}},
doi = {10.1051/m2an/2015043},
volume = {49},
year = {2015},
}
@article{1640,
abstract = {Auxin and cytokinin are key endogenous regulators of plant development. Although cytokinin-mediated modulation of auxin distribution is a developmentally crucial hormonal interaction, its molecular basis is largely unknown. Here we show a direct regulatory link between cytokinin signalling and the auxin transport machinery uncovering a mechanistic framework for cytokinin-auxin cross-talk. We show that the CYTOKININ RESPONSE FACTORS (CRFs), transcription factors downstream of cytokinin perception, transcriptionally control genes encoding PIN-FORMED (PIN) auxin transporters at a specific PIN CYTOKININ RESPONSE ELEMENT (PCRE) domain. Removal of this cis-regulatory element effectively uncouples PIN transcription from the CRF-mediated cytokinin regulation and attenuates plant cytokinin sensitivity. We propose that CRFs represent a missing cross-talk component that fine-tunes auxin transport capacity downstream of cytokinin signalling to control plant development.},
author = {Šimášková, Mária and O'Brien, José and Khan-Djamei, Mamoona and Van Noorden, Giel and Ötvös, Krisztina and Vieten, Anne and De Clercq, Inge and Van Haperen, Johanna and Cuesta, Candela and Hoyerová, Klára and Vanneste, Steffen and Marhavy, Peter and Wabnik, Krzysztof T and Van Breusegem, Frank and Nowack, Moritz and Murphy, Angus and Friml, Jiřĺ and Weijers, Dolf and Beeckman, Tom and Benková, Eva},
journal = {Nature Communications},
publisher = {Nature Publishing Group},
title = {{Cytokinin response factors regulate PIN-FORMED auxin transporters}},
doi = {10.1038/ncomms9717},
volume = {6},
year = {2015},
}
@article{1642,
abstract = {The Hanani-Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani-Tutte theorem in the case when each cluster induces a connected subgraph. Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident to at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.},
author = {Fulek, Radoslav and Kynčl, Jan and Malinovič, Igor and Pálvölgyi, Dömötör},
journal = {Electronic Journal of Combinatorics},
number = {4},
publisher = {Electronic Journal of Combinatorics},
title = {{Clustered planarity testing revisited}},
volume = {22},
year = {2015},
}
@inproceedings{1644,
abstract = {Increasing the computational complexity of evaluating a hash function, both for the honest users as well as for an adversary, is a useful technique employed for example in password-based cryptographic schemes to impede brute-force attacks, and also in so-called proofs of work (used in protocols like Bitcoin) to show that a certain amount of computation was performed by a legitimate user. A natural approach to adjust the complexity of a hash function is to iterate it c times, for some parameter c, in the hope that any query to the scheme requires c evaluations of the underlying hash function. However, results by Dodis et al. (Crypto 2012) imply that plain iteration falls short of achieving this goal, and designing schemes which provably have such a desirable property remained an open problem. This paper formalizes explicitly what it means for a given scheme to amplify the query complexity of a hash function. In the random oracle model, the goal of a secure query-complexity amplifier (QCA) scheme is captured as transforming, in the sense of indifferentiability, a random oracle allowing R queries (for the adversary) into one provably allowing only r < R queries. Turned around, this means that making r queries to the scheme requires at least R queries to the actual random oracle. Second, a new scheme, called collision-free iteration, is proposed and proven to achieve c-fold QCA for both the honest parties and the adversary, for any fixed parameter c.},
author = {Demay, Grégory and Gazi, Peter and Maurer, Ueli and Tackmann, Björn},
location = {Lugano, Switzerland},
pages = {159 -- 180},
publisher = {Springer},
title = {{Query-complexity amplification for random oracles}},
doi = {10.1007/978-3-319-17470-9_10},
volume = {9063},
year = {2015},
}
@inproceedings{1646,
abstract = {A pseudorandom function (PRF) is a keyed function F : K × X → Y where, for a random key k ∈ K, the function F(k, ·) is indistinguishable from a uniformly random function, given black-box access. A key-homomorphic PRF has the additional feature that for any keys k, k' and any input x, we have F(k+k', x) = F(k, x)⊕F(k', x) for some group operations +,⊕ on K and Y, respectively. A constrained PRF for a family of setsS ⊆ P(X) has the property that, given any key k and set S ∈ S, one can efficiently compute a “constrained” key kS that enables evaluation of F(k, x) on all inputs x ∈ S, while the values F(k, x) for x /∈ S remain pseudorandom even given kS. In this paper we construct PRFs that are simultaneously constrained and key homomorphic, where the homomorphic property holds even for constrained keys. We first show that the multilinear map-based bit-fixing and circuit-constrained PRFs of Boneh and Waters (Asiacrypt 2013) can be modified to also be keyhomomorphic. We then show that the LWE-based key-homomorphic PRFs of Banerjee and Peikert (Crypto 2014) are essentially already prefix-constrained PRFs, using a (non-obvious) definition of constrained keys and associated group operation. Moreover, the constrained keys themselves are pseudorandom, and the constraining and evaluation functions can all be computed in low depth. As an application of key-homomorphic constrained PRFs,we construct a proxy re-encryption schemewith fine-grained access control. This scheme allows storing encrypted data on an untrusted server, where each file can be encrypted relative to some attributes, so that only parties whose constrained keys match the attributes can decrypt. Moreover, the server can re-key (arbitrary subsets of) the ciphertexts without learning anything about the plaintexts, thus permitting efficient and finegrained revocation.},
author = {Banerjee, Abishek and Fuchsbauer, Georg and Peikert, Chris and Pietrzak, Krzysztof Z and Stevens, Sophie},
location = {Warsaw, Poland},
pages = {31 -- 60},
publisher = {Springer},
title = {{Key-homomorphic constrained pseudorandom functions}},
doi = {10.1007/978-3-662-46497-7_2},
volume = {9015},
year = {2015},
}
@inproceedings{1647,
abstract = {Round-optimal blind signatures are notoriously hard to construct in the standard model, especially in the malicious-signer model, where blindness must hold under adversarially chosen keys. This is substantiated by several impossibility results. The only construction that can be termed theoretically efficient, by Garg and Gupta (Eurocrypt’14), requires complexity leveraging, inducing an exponential security loss. We present a construction of practically efficient round-optimal blind signatures in the standard model. It is conceptually simple and builds on the recent structure-preserving signatures on equivalence classes (SPSEQ) from Asiacrypt’14. While the traditional notion of blindness follows from standard assumptions, we prove blindness under adversarially chosen keys under an interactive variant of DDH. However, we neither require non-uniform assumptions nor complexity leveraging. We then show how to extend our construction to partially blind signatures and to blind signatures on message vectors, which yield a construction of one-show anonymous credentials à la “anonymous credentials light” (CCS’13) in the standard model. Furthermore, we give the first SPS-EQ construction under noninteractive assumptions and show how SPS-EQ schemes imply conventional structure-preserving signatures, which allows us to apply optimality results for the latter to SPS-EQ.},
author = {Fuchsbauer, Georg and Hanser, Christian and Slamanig, Daniel},
location = {Santa Barbara, CA, United States},
pages = {233 -- 253},
publisher = {Springer},
title = {{Practical round-optimal blind signatures in the standard model}},
doi = {10.1007/978-3-662-48000-7_12},
volume = {9216},
year = {2015},
}
@inproceedings{1648,
abstract = {Generalized Selective Decryption (GSD), introduced by Panjwani [TCC’07], is a game for a symmetric encryption scheme Enc that captures the difficulty of proving adaptive security of certain protocols, most notably the Logical Key Hierarchy (LKH) multicast encryption protocol. In the GSD game there are n keys k1,..., kn, which the adversary may adaptively corrupt (learn); moreover, it can ask for encryptions Encki (kj) of keys under other keys. The adversary’s task is to distinguish keys (which it cannot trivially compute) from random. Proving the hardness of GSD assuming only IND-CPA security of Enc is surprisingly hard. Using “complexity leveraging” loses a factor exponential in n, which makes the proof practically meaningless. We can think of the GSD game as building a graph on n vertices, where we add an edge i → j when the adversary asks for an encryption of kj under ki. If restricted to graphs of depth ℓ, Panjwani gave a reduction that loses only a factor exponential in ℓ (not n). To date, this is the only non-trivial result known for GSD. In this paper we give almost-polynomial reductions for large classes of graphs. Most importantly, we prove the security of the GSD game restricted to trees losing only a quasi-polynomial factor n3 log n+5. Trees are an important special case capturing real-world protocols like the LKH protocol. Our new bound improves upon Panjwani’s on some LKH variants proposed in the literature where the underlying tree is not balanced. Our proof builds on ideas from the “nested hybrids” technique recently introduced by Fuchsbauer et al. [Asiacrypt’14] for proving the adaptive security of constrained PRFs.},
author = {Fuchsbauer, Georg and Jafargholi, Zahra and Pietrzak, Krzysztof Z},
location = {Santa Barbara, CA, USA},
pages = {601 -- 620},
publisher = {Springer},
title = {{A quasipolynomial reduction for generalized selective decryption on trees}},
doi = {10.1007/978-3-662-47989-6_29},
volume = {9215},
year = {2015},
}
@inproceedings{1649,
abstract = {We extend a commitment scheme based on the learning with errors over rings (RLWE) problem, and present efficient companion zeroknowledge proofs of knowledge. Our scheme maps elements from the ring (or equivalently, n elements from },
author = {Benhamouda, Fabrice and Krenn, Stephan and Lyubashevsky, Vadim and Pietrzak, Krzysztof Z},
location = {Vienna, Austria},
pages = {305 -- 325},
publisher = {Springer},
title = {{Efficient zero-knowledge proofs for commitments from learning with errors over rings}},
doi = {10.1007/978-3-319-24174-6_16},
volume = {9326},
year = {2015},
}
@inproceedings{1650,
abstract = {We consider the task of deriving a key with high HILL entropy (i.e., being computationally indistinguishable from a key with high min-entropy) from an unpredictable source.
Previous to this work, the only known way to transform unpredictability into a key that was ϵ indistinguishable from having min-entropy was via pseudorandomness, for example by Goldreich-Levin (GL) hardcore bits. This approach has the inherent limitation that from a source with k bits of unpredictability entropy one can derive a key of length (and thus HILL entropy) at most k−2log(1/ϵ) bits. In many settings, e.g. when dealing with biometric data, such a 2log(1/ϵ) bit entropy loss in not an option. Our main technical contribution is a theorem that states that in the high entropy regime, unpredictability implies HILL entropy. Concretely, any variable K with |K|−d bits of unpredictability entropy has the same amount of so called metric entropy (against real-valued, deterministic distinguishers), which is known to imply the same amount of HILL entropy. The loss in circuit size in this argument is exponential in the entropy gap d, and thus this result only applies for small d (i.e., where the size of distinguishers considered is exponential in d).
To overcome the above restriction, we investigate if it’s possible to first “condense” unpredictability entropy and make the entropy gap small. We show that any source with k bits of unpredictability can be condensed into a source of length k with k−3 bits of unpredictability entropy. Our condenser simply “abuses" the GL construction and derives a k bit key from a source with k bits of unpredicatibily. The original GL theorem implies nothing when extracting that many bits, but we show that in this regime, GL still behaves like a “condenser" for unpredictability. This result comes with two caveats (1) the loss in circuit size is exponential in k and (2) we require that the source we start with has no HILL entropy (equivalently, one can efficiently check if a guess is correct). We leave it as an intriguing open problem to overcome these restrictions or to prove they’re inherent.},
author = {Skórski, Maciej and Golovnev, Alexander and Pietrzak, Krzysztof Z},
location = {Kyoto, Japan},
pages = {1046 -- 1057},
publisher = {Springer},
title = {{Condensed unpredictability }},
doi = {10.1007/978-3-662-47672-7_85},
volume = {9134},
year = {2015},
}
@inproceedings{1652,
abstract = {We develop new theoretical tools for proving lower-bounds on the (amortized) complexity of certain functions in models of parallel computation. We apply the tools to construct a class of functions with high amortized memory complexity in the parallel Random Oracle Model (pROM); a variant of the standard ROM allowing for batches of simultaneous queries. In particular we obtain a new, more robust, type of Memory-Hard Functions (MHF); a security primitive which has recently been gaining acceptance in practice as an effective means of countering brute-force attacks on security relevant functions. Along the way we also demonstrate an important shortcoming of previous definitions of MHFs and give a new definition addressing the problem. The tools we develop represent an adaptation of the powerful pebbling paradigm (initially introduced by Hewitt and Paterson [HP70] and Cook [Coo73]) to a simple and intuitive parallel setting. We define a simple pebbling game Gp over graphs which aims to abstract parallel computation in an intuitive way. As a conceptual contribution we define a measure of pebbling complexity for graphs called cumulative complexity (CC) and show how it overcomes a crucial shortcoming (in the parallel setting) exhibited by more traditional complexity measures used in the past. As a main technical contribution we give an explicit construction of a constant in-degree family of graphs whose CC in Gp approaches maximality to within a polylogarithmic factor for any graph of equal size (analogous to the graphs of Tarjan et. al. [PTC76, LT82] for sequential pebbling games). Finally, for a given graph G and related function fG, we derive a lower-bound on the amortized memory complexity of fG in the pROM in terms of the CC of G in the game Gp.},
author = {Alwen, Joel F and Serbinenko, Vladimir},
booktitle = {Proceedings of the 47th annual ACM symposium on Theory of computing},
location = {Portland, OR, United States},
pages = {595 -- 603},
publisher = {ACM},
title = {{High parallel complexity graphs and memory-hard functions}},
doi = {10.1145/2746539.2746622},
year = {2015},
}
@inproceedings{1654,
abstract = {HMAC and its variant NMAC are the most popular approaches to deriving a MAC (and more generally, a PRF) from a cryptographic hash function. Despite nearly two decades of research, their exact security still remains far from understood in many different contexts. Indeed, recent works have re-surfaced interest for {\em generic} attacks, i.e., attacks that treat the compression function of the underlying hash function as a black box.
Generic security can be proved in a model where the underlying compression function is modeled as a random function -- yet, to date, the question of proving tight, non-trivial bounds on the generic security of HMAC/NMAC even as a PRF remains a challenging open question.
In this paper, we ask the question of whether a small modification to HMAC and NMAC can allow us to exactly characterize the security of the resulting constructions, while only incurring little penalty with respect to efficiency. To this end, we present simple variants of NMAC and HMAC, for which we prove tight bounds on the generic PRF security, expressed in terms of numbers of construction and compression function queries necessary to break the construction. All of our constructions are obtained via a (near) {\em black-box} modification of NMAC and HMAC, which can be interpreted as an initial step of key-dependent message pre-processing.
While our focus is on PRF security, a further attractive feature of our new constructions is that they clearly defeat all recent generic attacks against properties such as state recovery and universal forgery. These exploit properties of the so-called ``functional graph'' which are not directly accessible in our new constructions. },
author = {Gazi, Peter and Pietrzak, Krzysztof Z and Tessaro, Stefano},
location = {Auckland, New Zealand},
pages = {85 -- 109},
publisher = {Springer},
title = {{Generic security of NMAC and HMAC with input whitening}},
doi = {10.1007/978-3-662-48800-3_4},
volume = {9453},
year = {2015},
}
@article{1655,
abstract = {Quantifying behaviors of robots which were generated autonomously from task-independent objective functions is an important prerequisite for objective comparisons of algorithms and movements of animals. The temporal sequence of such a behavior can be considered as a time series and hence complexity measures developed for time series are natural candidates for its quantification. The predictive information and the excess entropy are such complexity measures. They measure the amount of information the past contains about the future and thus quantify the nonrandom structure in the temporal sequence. However, when using these measures for systems with continuous states one has to deal with the fact that their values will depend on the resolution with which the systems states are observed. For deterministic systems both measures will diverge with increasing resolution. We therefore propose a new decomposition of the excess entropy in resolution dependent and resolution independent parts and discuss how they depend on the dimensionality of the dynamics, correlations and the noise level. For the practical estimation we propose to use estimates based on the correlation integral instead of the direct estimation of the mutual information based on next neighbor statistics because the latter allows less control of the scale dependencies. Using our algorithm we are able to show how autonomous learning generates behavior of increasing complexity with increasing learning duration.},
author = {Martius, Georg S and Olbrich, Eckehard},
journal = {Entropy},
number = {10},
pages = {7266 -- 7297},
publisher = {Multidisciplinary Digital Publishing Institute},
title = {{Quantifying emergent behavior of autonomous robots}},
doi = {10.3390/e17107266},
volume = {17},
year = {2015},
}
@inproceedings{1659,
abstract = {The target discounted-sum problem is the following: Given a rational discount factor 0 < λ < 1 and three rational values a, b, and t, does there exist a finite or an infinite sequence w ε(a, b)∗ or w ε(a, b)w, such that Σ|w| i=0 w(i)λi equals t? The problem turns out to relate to many fields of mathematics and computer science, and its decidability question is surprisingly hard to solve. We solve the finite version of the problem, and show the hardness of the infinite version, linking it to various areas and open problems in mathematics and computer science: β-expansions, discounted-sum automata, piecewise affine maps, and generalizations of the Cantor set. We provide some partial results to the infinite version, among which are solutions to its restriction to eventually-periodic sequences and to the cases that λ λ 1/2 or λ = 1/n, for every n ε N. We use our results for solving some open problems on discounted-sum automata, among which are the exact-value problem for nondeterministic automata over finite words and the universality and inclusion problems for functional automata.},
author = {Boker, Udi and Henzinger, Thomas A and Otop, Jan},
booktitle = {LICS},
issn = {1043-6871 },
location = {Kyoto, Japan},
pages = {750 -- 761},
publisher = {IEEE},
title = {{The target discounted-sum problem}},
doi = {10.1109/LICS.2015.74},
year = {2015},
}
@inproceedings{1660,
abstract = {We study the pattern frequency vector for runs in probabilistic Vector Addition Systems with States (pVASS). Intuitively, each configuration of a given pVASS is assigned one of finitely many patterns, and every run can thus be seen as an infinite sequence of these patterns. The pattern frequency vector assigns to each run the limit of pattern frequencies computed for longer and longer prefixes of the run. If the limit does not exist, then the vector is undefined. We show that for one-counter pVASS, the pattern frequency vector is defined and takes one of finitely many values for almost all runs. Further, these values and their associated probabilities can be approximated up to an arbitrarily small relative error in polynomial time. For stable two-counter pVASS, we show the same result, but we do not provide any upper complexity bound. As a byproduct of our study, we discover counterexamples falsifying some classical results about stochastic Petri nets published in the 80s.},
author = {Brázdil, Tomáš and Kiefer, Stefan and Kučera, Antonín and Novotny, Petr},
location = {Kyoto, Japan},
pages = {44 -- 55},
publisher = {IEEE},
title = {{Long-run average behaviour of probabilistic vector addition systems}},
doi = {10.1109/LICS.2015.15},
year = {2015},
}
@inproceedings{1661,
abstract = {The computation of the winning set for one-pair Streett objectives and for k-pair Streett objectives in (standard) graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formed ness of specifications, and the synthesis of reactive systems. We give faster algorithms for the computation of the winning set for (1) one-pair Streett objectives (aka parity-3 problem) in game graphs and (2) for k-pair Streett objectives in graphs. For both problems this represents the first improvement in asymptotic running time in 15 years.},
author = {Chatterjee, Krishnendu and Henzinger, Monika and Loitzenbauer, Veronika},
booktitle = {Proceedings - Symposium on Logic in Computer Science},
location = {Kyoto, Japan},
publisher = {IEEE},
title = {{Improved algorithms for one-pair and k-pair Streett objectives}},
doi = {10.1109/LICS.2015.34},
volume = {2015-July},
year = {2015},
}
@article{1664,
abstract = {Over a century of research into the origin of turbulence in wall-bounded shear flows has resulted in a puzzling picture in which turbulence appears in a variety of different states competing with laminar background flow. At moderate flow speeds, turbulence is confined to localized patches; it is only at higher speeds that the entire flow becomes turbulent. The origin of the different states encountered during this transition, the front dynamics of the turbulent regions and the transformation to full turbulence have yet to be explained. By combining experiments, theory and computer simulations, here we uncover a bifurcation scenario that explains the transformation to fully turbulent pipe flow and describe the front dynamics of the different states encountered in the process. Key to resolving this problem is the interpretation of the flow as a bistable system with nonlinear propagation (advection) of turbulent fronts. These findings bridge the gap between our understanding of the onset of turbulence and fully turbulent flows.},
author = {Barkley, Dwight and Song, Baofang and Vasudevan, Mukund and Lemoult, Grégoire M and Avila, Marc and Hof, Björn},
journal = {Nature},
number = {7574},
pages = {550 -- 553},
publisher = {Nature Publishing Group},
title = {{The rise of fully turbulent flow}},
doi = {10.1038/nature15701},
volume = {526},
year = {2015},
}
@article{1665,
abstract = {Which genetic alterations drive tumorigenesis and how they evolve over the course of disease and therapy are central questions in cancer biology. Here we identify 44 recurrently mutated genes and 11 recurrent somatic copy number variations through whole-exome sequencing of 538 chronic lymphocytic leukaemia (CLL) and matched germline DNA samples, 278 of which were collected in a prospective clinical trial. These include previously unrecognized putative cancer drivers (RPS15, IKZF3), and collectively identify RNA processing and export, MYC activity, and MAPK signalling as central pathways involved in CLL. Clonality analysis of this large data set further enabled reconstruction of temporal relationships between driver events. Direct comparison between matched pre-treatment and relapse samples from 59 patients demonstrated highly frequent clonal evolution. Thus, large sequencing data sets of clinically informative samples enable the discovery of novel genes associated with cancer, the network of relationships between the driver events, and their impact on disease relapse and clinical outcome.},
author = {Landau, Dan and Tausch, Eugen and Taylor Weiner, Amaro and Stewart, Chip and Reiter, Johannes and Bahlo, Jasmin and Kluth, Sandra and Božić, Ivana and Lawrence, Michael and Böttcher, Sebastian and Carter, Scott and Cibulskis, Kristian and Mertens, Daniel and Sougnez, Carrie and Rosenberg, Mara and Hess, Julian and Edelmann, Jennifer and Kless, Sabrina and Kneba, Michael and Ritgen, Matthias and Fink, Anna and Fischer, Kirsten and Gabriel, Stacey and Lander, Eric and Nowak, Martin and Döhner, Hartmut and Hallek, Michael and Neuberg, Donna and Getz, Gad and Stilgenbauer, Stephan and Wu, Catherine},
journal = {Nature},
number = {7574},
pages = {525 -- 530},
publisher = {Nature Publishing Group},
title = {{Mutations driving CLL and their evolution in progression and relapse}},
doi = {10.1038/nature15395},
volume = {526},
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},
}
@inproceedings{1667,
abstract = {We consider parametric version of fixed-delay continuoustime Markov chains (or equivalently deterministic and stochastic Petri nets, DSPN) where fixed-delay transitions are specified by parameters, rather than concrete values. Our goal is to synthesize values of these parameters that, for a given cost function, minimise expected total cost incurred before reaching a given set of target states. We show that under mild assumptions, optimal values of parameters can be effectively approximated using translation to a Markov decision process (MDP) whose actions correspond to discretized values of these parameters. To this end we identify and overcome several interesting phenomena arising in systems with fixed delays.},
author = {Brázdil, Tomáš and Korenčiak, L'Uboš and Krčál, Jan and Novotny, Petr and Řehák, Vojtěch},
location = {Madrid, Spain},
pages = {141 -- 159},
publisher = {Springer},
title = {{Optimizing performance of continuous-time stochastic systems using timeout synthesis}},
doi = {10.1007/978-3-319-22264-6_10},
volume = {9259},
year = {2015},
}
@inproceedings{1668,
abstract = {We revisit the security (as a pseudorandom permutation) of cascading-based constructions for block-cipher key-length extension. Previous works typically considered the extreme case where the adversary is given the entire codebook of the construction, the only complexity measure being the number qe of queries to the underlying ideal block cipher, representing adversary’s secret-key-independent computation. Here, we initiate a systematic study of the more natural case of an adversary restricted to adaptively learning a number qc of plaintext/ciphertext pairs that is less than the entire codebook. For any such qc, we aim to determine the highest number of block-cipher queries qe the adversary can issue without being able to successfully distinguish the construction (under a secret key) from a random permutation.
More concretely, we show the following results for key-length extension schemes using a block cipher with n-bit blocks and κ-bit keys:
Plain cascades of length ℓ=2r+1 are secure whenever qcqre≪2r(κ+n), qc≪2κ and qe≪22κ. The bound for r=1 also applies to two-key triple encryption (as used within Triple DES).
The r-round XOR-cascade is secure as long as qcqre≪2r(κ+n), matching an attack by Gaži (CRYPTO 2013).
We fully characterize the security of Gaži and Tessaro’s two-call },
author = {Gazi, Peter and Lee, Jooyoung and Seurin, Yannick and Steinberger, John and Tessaro, Stefano},
location = {Istanbul, Turkey},
pages = {319 -- 341},
publisher = {Springer},
title = {{Relaxing full-codebook security: A refined analysis of key-length extension schemes}},
doi = {10.1007/978-3-662-48116-5_16},
volume = {9054},
year = {2015},
}
@inproceedings{1669,
abstract = {Computational notions of entropy (a.k.a. pseudoentropy) have found many applications, including leakage-resilient cryptography, deterministic encryption or memory delegation. The most important tools to argue about pseudoentropy are chain rules, which quantify by how much (in terms of quantity and quality) the pseudoentropy of a given random variable X decreases when conditioned on some other variable Z (think for example of X as a secret key and Z as information leaked by a side-channel). In this paper we give a very simple and modular proof of the chain rule for HILL pseudoentropy, improving best known parameters. Our version allows for increasing the acceptable length of leakage in applications up to a constant factor compared to the best previous bounds. As a contribution of independent interest, we provide a comprehensive study of all known versions of the chain rule, comparing their worst-case strength and limitations.},
author = {Pietrzak, Krzysztof Z and Skórski, Maciej},
location = {Guadalajara, Mexico},
pages = {81 -- 98},
publisher = {Springer},
title = {{The chain rule for HILL pseudoentropy, revisited}},
doi = {10.1007/978-3-319-22174-8_5},
volume = {9230},
year = {2015},
}
@inproceedings{1671,
abstract = {This paper studies the concrete security of PRFs and MACs obtained by keying hash functions based on the sponge paradigm. One such hash function is KECCAK, selected as NIST’s new SHA-3 standard. In contrast to other approaches like HMAC, the exact security of keyed sponges is not well understood. Indeed, recent security analyses delivered concrete security bounds which are far from existing attacks. This paper aims to close this gap. We prove (nearly) exact bounds on the concrete PRF security of keyed sponges using a random permutation. These bounds are tight for the most relevant ranges of parameters, i.e., for messages of length (roughly) l ≤ min{2n/4, 2r} blocks, where n is the state size and r is the desired output length; and for l ≤ q queries (to the construction or the underlying permutation). Moreover, we also improve standard-model bounds. As an intermediate step of independent interest, we prove tight bounds on the PRF security of the truncated CBC-MAC construction, which operates as plain CBC-MAC, but only returns a prefix of the output.},
author = {Gazi, Peter and Pietrzak, Krzysztof Z and Tessaro, Stefano},
location = {Santa Barbara, CA, United States},
pages = {368 -- 387},
publisher = {Springer},
title = {{The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC}},
doi = {10.1007/978-3-662-47989-6_18},
volume = {9215},
year = {2015},
}
@inproceedings{1672,
abstract = {Composable notions of incoercibility aim to forbid a coercer from using anything beyond the coerced parties’ inputs and outputs to catch them when they try to deceive him. Existing definitions are restricted to weak coercion types, and/or are not universally composable. Furthermore, they often make too strong assumptions on the knowledge of coerced parties—e.g., they assume they known the identities and/or the strategies of other coerced parties, or those of corrupted parties— which makes them unsuitable for applications of incoercibility such as e-voting, where colluding adversarial parties may attempt to coerce honest voters, e.g., by offering them money for a promised vote, and use their own view to check that the voter keeps his end of the bargain. In this work we put forward the first universally composable notion of incoercible multi-party computation, which satisfies the above intuition and does not assume collusions among coerced parties or knowledge of the corrupted set. We define natural notions of UC incoercibility corresponding to standard coercion-types, i.e., receipt-freeness and resistance to full-active coercion. Importantly, our suggested notion has the unique property that it builds on top of the well studied UC framework by Canetti instead of modifying it. This guarantees backwards compatibility, and allows us to inherit results from the rich UC literature. We then present MPC protocols which realize our notions of UC incoercibility given access to an arguably minimal setup—namely honestly generate tamper-proof hardware performing a very simple cryptographic operation—e.g., a smart card. This is, to our knowledge, the first proposed construction of an MPC protocol (for more than two parties) that is incoercibly secure and universally composable, and therefore the first construction of a universally composable receipt-free e-voting protocol.},
author = {Alwen, Joel F and Ostrovsky, Rafail and Zhou, Hongsheng and Zikas, Vassilis},
location = {Santa Barbara, CA, United States},
pages = {763 -- 780},
publisher = {Springer},
title = {{Incoercible multi-party computation and universally composable receipt-free voting}},
doi = {10.1007/978-3-662-48000-7_37},
volume = {9216},
year = {2015},
}
@article{1673,
abstract = {When a new mutant arises in a population, there is a probability it outcompetes the residents and fixes. The structure of the population can affect this fixation probability. Suppressing population structures reduce the difference between two competing variants, while amplifying population structures enhance the difference. Suppressors are ubiquitous and easy to construct, but amplifiers for the large population limit are more elusive and only a few examples have been discovered. Whether or not a population structure is an amplifier of selection depends on the probability distribution for the placement of the invading mutant. First, we prove that there exist only bounded amplifiers for adversarial placement-that is, for arbitrary initial conditions. Next, we show that the Star population structure, which is known to amplify for mutants placed uniformly at random, does not amplify for mutants that arise through reproduction and are therefore placed proportional to the temperatures of the vertices. Finally, we construct population structures that amplify for all mutational events that arise through reproduction, uniformly at random, or through some combination of the two. },
author = {Adlam, Ben and Chatterjee, Krishnendu and Nowak, Martin},
journal = {Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences},
number = {2181},
publisher = {Royal Society of London},
title = {{Amplifiers of selection}},
doi = {10.1098/rspa.2015.0114},
volume = {471},
year = {2015},
}
@article{1674,
abstract = {We consider N × N random matrices of the form H = W + V where W is a real symmetric Wigner matrix and V a random or deterministic, real, diagonal matrix whose entries are independent of W. We assume subexponential decay for the matrix entries of W and we choose V so that the eigenvalues of W and V are typically of the same order. For a large class of diagonal matrices V, we show that the rescaled distribution of the extremal eigenvalues is given by the Tracy-Widom distribution F1 in the limit of large N. Our proofs also apply to the complex Hermitian setting, i.e. when W is a complex Hermitian Wigner matrix.},
author = {Lee, Jioon and Schnelli, Kevin},
journal = {Reviews in Mathematical Physics},
number = {8},
publisher = {World Scientific Publishing},
title = {{Edge universality for deformed Wigner matrices}},
doi = {10.1142/S0129055X1550018X},
volume = {27},
year = {2015},
}
@article{1677,
abstract = {We consider real symmetric and complex Hermitian random matrices with the additional symmetry hxy = hN-y,N-x. The matrix elements are independent (up to the fourfold symmetry) and not necessarily identically distributed. This ensemble naturally arises as the Fourier transform of a Gaussian orthogonal ensemble. Italso occurs as the flip matrix model - an approximation of the two-dimensional Anderson model at small disorder. We show that the density of states converges to the Wigner semicircle law despite the new symmetry type. We also prove the local version of the semicircle law on the optimal scale.},
author = {Alt, Johannes},
journal = {Journal of Mathematical Physics},
number = {10},
publisher = {American Institute of Physics},
title = {{The local semicircle law for random matrices with a fourfold symmetry}},
doi = {10.1063/1.4932606},
volume = {56},
year = {2015},
}
@article{1678,
abstract = {High-throughput live-cell screens are intricate elements of systems biology studies and drug discovery pipelines. Here, we demonstrate an optogenetics-assisted method that avoids the need for chemical activators and reporters, reduces the number of operational steps and increases information content in a cell-based small-molecule screen against human protein kinases, including an orphan receptor tyrosine kinase. This blueprint for all-optical screening can be adapted to many drug targets and cellular processes.},
author = {Inglés Prieto, Álvaro and Gschaider-Reichhart, Eva and Muellner, Markus and Nowak, Matthias and Nijman, Sebastian and Grusch, Michael and Janovjak, Harald L},
journal = {Nature Chemical Biology},
number = {12},
pages = {952 -- 954},
publisher = {Nature Publishing Group},
title = {{Light-assisted small-molecule screening against protein kinases}},
doi = {10.1038/nchembio.1933},
volume = {11},
year = {2015},
}
@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},
}
@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{1687,
abstract = {Guided cell movement is essential for development and integrity of animals and crucially involved in cellular immune responses. Leukocytes are professional migratory cells that can navigate through most types of tissues and sense a wide range of directional cues. The responses of these cells to attractants have been mainly explored in tissue culture settings. How leukocytes make directional decisions in situ, within the challenging environment of a tissue maze, is less understood. Here we review recent advances in how leukocytes sense chemical cues in complex tissue settings and make links with paradigms of directed migration in development and Dictyostelium discoideum amoebae.},
author = {Sarris, Milka and Sixt, Michael K},
journal = {Current Opinion in Cell Biology},
number = {10},
pages = {93 -- 102},
publisher = {Elsevier},
title = {{Navigating in tissue mazes: Chemoattractant interpretation in complex environments}},
doi = {10.1016/j.ceb.2015.08.001},
volume = {36},
year = {2015},
}
@article{1688,
abstract = {We estimate the selection constant in the following geometric selection theorem by Pach: For every positive integer d, there is a constant (Formula presented.) such that whenever (Formula presented.) are n-element subsets of (Formula presented.), we can find a point (Formula presented.) and subsets (Formula presented.) for every i∈[d+1], each of size at least cdn, such that p belongs to all rainbowd-simplices determined by (Formula presented.) simplices with one vertex in each Yi. We show a super-exponentially decreasing upper bound (Formula presented.). The ideas used in the proof of the upper bound also help us to prove Pach’s theorem with (Formula presented.), which is a lower bound doubly exponentially decreasing in d (up to some polynomial in the exponent). For comparison, Pach’s original approach yields a triply exponentially decreasing lower bound. On the other hand, Fox, Pach, and Suk recently obtained a hypergraph density result implying a proof of Pach’s theorem with (Formula presented.). In our construction for the upper bound, we use the fact that the minimum solid angle of every d-simplex is super-exponentially small. This fact was previously unknown and might be of independent interest. For the lower bound, we improve the ‘separation’ part of the argument by showing that in one of the key steps only d+1 separations are necessary, compared to 2d separations in the original proof. We also provide a measure version of Pach’s theorem.},
author = {Karasev, Roman and Kynčl, Jan and Paták, Pavel and Patakova, Zuzana and Tancer, Martin},
journal = {Discrete & Computational Geometry},
number = {3},
pages = {610 -- 636},
publisher = {Springer},
title = {{Bounds for Pach's selection theorem and for the minimum solid angle in a simplex}},
doi = {10.1007/s00454-015-9720-z},
volume = {54},
year = {2015},
}
@inproceedings{1689,
abstract = {We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. We demonstrate our approach on an illustrative case study.},
author = {Svoreňová, Mária and Kretinsky, Jan and Chmelik, Martin and Chatterjee, Krishnendu and Cěrná, Ivana and Belta, Cǎlin},
booktitle = {Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control},
location = {Seattle, WA, United States},
pages = {259 -- 268},
publisher = {ACM},
title = {{Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games}},
doi = {10.1145/2728606.2728608},
year = {2015},
}
@article{1693,
abstract = {Quantum interference between energetically close states is theoretically investigated, with the state structure being observed via laser spectroscopy. In this work, we focus on hyperfine states of selected hydrogenic muonic isotopes, and on how quantum interference affects the measured Lamb shift. The process of photon excitation and subsequent photon decay is implemented within the framework of nonrelativistic second-order perturbation theory. Due to its experimental interest, calculations are performed for muonic hydrogen, deuterium, and helium-3. We restrict our analysis to the case of photon scattering by incident linear polarized photons and the polarization of the scattered photons not being observed. We conclude that while quantum interference effects can be safely neglected in muonic hydrogen and helium-3, in the case of muonic deuterium there are resonances with close proximity, where quantum interference effects can induce shifts up to a few percent of the linewidth, assuming a pointlike detector. However, by taking into account the geometry of the setup used by the CREMA collaboration, this effect is reduced to less than 0.2% of the linewidth in all possible cases, which makes it irrelevant at the present level of accuracy. © 2015 American Physical Society.},
author = {Amaro, Pedro and Franke, Beatrice and Krauth, Julian and Diepold, Marc and Fratini, Filippo and Safari, Laleh and Machado, Jorge and Antognini, Aldo and Kottmann, Franz and Indelicato, Paul and Pohl, Randolf and Santos, José},
journal = {Physical Review A},
number = {2},
publisher = {American Physical Society},
title = {{Quantum interference effects in laser spectroscopy of muonic hydrogen, deuterium, and helium-3}},
doi = {10.1103/PhysRevA.92.022514},
volume = {92},
year = {2015},
}
@article{1695,
abstract = {We give a comprehensive introduction into a diagrammatic method that allows for the evaluation of Gutzwiller wave functions in finite spatial dimensions. We discuss in detail some numerical schemes that turned out to be useful in the real-space evaluation of the diagrams. The method is applied to the problem of d-wave superconductivity in a two-dimensional single-band Hubbard model. Here, we discuss in particular the role of long-range contributions in our diagrammatic expansion. We further reconsider our previous analysis on the kinetic energy gain in the superconducting state.},
author = {Kaczmarczyk, Jan and Schickling, Tobias and Bünemann, Jörg},
journal = {Physica Status Solidi (B): Basic Solid State Physics},
number = {9},
pages = {2059 -- 2071},
publisher = {Wiley},
title = {{Evaluation techniques for Gutzwiller wave functions in finite dimensions}},
doi = {10.1002/pssb.201552082},
volume = {252},
year = {2015},
}
@article{1696,
abstract = {The recently proposed diagrammatic expansion (DE) technique for the full Gutzwiller wave function (GWF) is applied to the Anderson lattice model. This approach allows for a systematic evaluation of the expectation values with full Gutzwiller wave function in finite-dimensional systems. It introduces results extending in an essential manner those obtained by means of the standard Gutzwiller approximation (GA), which is variationally exact only in infinite dimensions. Within the DE-GWF approach we discuss the principal paramagnetic properties and their relevance to heavy-fermion systems. We demonstrate the formation of an effective, narrow f band originating from atomic f-electron states and subsequently interpret this behavior as a direct itineracy of f electrons; it represents a combined effect of both the hybridization and the correlations induced by the Coulomb repulsive interaction. Such a feature is absent on the level of GA, which is equivalent to the zeroth order of our expansion. Formation of the hybridization- and electron-concentration-dependent narrow f band rationalizes the common assumption of such dispersion of f levels in the phenomenological modeling of the band structure of CeCoIn5. Moreover, it is shown that the emerging f-electron direct itineracy leads in a natural manner to three physically distinct regimes within a single model that are frequently discussed for 4f- or 5f-electron compounds as separate model situations. We identify these regimes as (i) the mixed-valence regime, (ii) Kondo/almost-Kondo insulating regime, and (iii) the Kondo-lattice limit when the f-electron occupancy is very close to the f-state half filling, ⟨nˆf⟩→1. The nonstandard features of the emerging correlated quantum liquid state are stressed.},
author = {Wysokiński, Marcin and Kaczmarczyk, Jan and Spałek, Jozef},
journal = {Physical Review B},
number = {12},
publisher = {American Physical Society},
title = {{Gutzwiller wave function solution for Anderson lattice model: Emerging universal regimes of heavy quasiparticle states}},
doi = {10.1103/PhysRevB.92.125135},
volume = {92},
year = {2015},
}
@article{1697,
abstract = {Motion tracking is a challenge the visual system has to solve by reading out the retinal population. It is still unclear how the information from different neurons can be combined together to estimate the position of an object. Here we recorded a large population of ganglion cells in a dense patch of salamander and guinea pig retinas while displaying a bar moving diffusively. We show that the bar’s position can be reconstructed from retinal activity with a precision in the hyperacuity regime using a linear decoder acting on 100+ cells. We then took advantage of this unprecedented precision to explore the spatial structure of the retina’s population code. The classical view would have suggested that the firing rates of the cells form a moving hill of activity tracking the bar’s position. Instead, we found that most ganglion cells in the salamander fired sparsely and idiosyncratically, so that their neural image did not track the bar. Furthermore, ganglion cell activity spanned an area much larger than predicted by their receptive fields, with cells coding for motion far in their surround. As a result, population redundancy was high, and we could find multiple, disjoint subsets of neurons that encoded the trajectory with high precision. This organization allows for diverse collections of ganglion cells to represent high-accuracy motion information in a form easily read out by downstream neural circuits.},
author = {Marre, Olivier and Botella Soler, Vicente and Simmons, Kristina and Mora, Thierry and Tkacik, Gasper and Berry, Michael},
journal = {PLoS Computational Biology},
number = {7},
publisher = {Public Library of Science},
title = {{High accuracy decoding of dynamical motion from a large retinal population}},
doi = {10.1371/journal.pcbi.1004304},
volume = {11},
year = {2015},
}
@article{1698,
abstract = {In mean-payoff games, the objective of the protagonist is to ensure that the limit average of an infinite sequence of numeric weights is nonnegative. In energy games, the objective is to ensure that the running sum of weights is always nonnegative. Multi-mean-payoff and multi-energy games replace individual weights by tuples, and the limit average (resp., running sum) of each coordinate must be (resp., remain) nonnegative. We prove finite-memory determinacy of multi-energy games and show inter-reducibility of multi-mean-payoff and multi-energy games for finite-memory strategies. We improve the computational complexity for solving both classes with finite-memory strategies: we prove coNP-completeness improving the previous known EXPSPACE bound. For memoryless strategies, we show that deciding the existence of a winning strategy for the protagonist is NP-complete. We present the first solution of multi-mean-payoff games with infinite-memory strategies: we show that mean-payoff-sup objectives can be decided in NP∩coNP, whereas mean-payoff-inf objectives are coNP-complete.},
author = {Velner, Yaron and Chatterjee, Krishnendu and Doyen, Laurent and Henzinger, Thomas A and Rabinovich, Alexander and Raskin, Jean},
journal = {Information and Computation},
number = {4},
pages = {177 -- 196},
publisher = {Elsevier},
title = {{The complexity of multi-mean-payoff and multi-energy games}},
doi = {10.1016/j.ic.2015.03.001},
volume = {241},
year = {2015},
}
@article{1699,
abstract = {By hybridization and backcrossing, alleles can surmount species boundaries and be incorporated into the genome of a related species. This introgression of genes is of particular evolutionary relevance if it involves the transfer of adaptations between populations. However, any beneficial allele will typically be associated with other alien alleles that are often deleterious and hamper the introgression process. In order to describe the introgression of an adaptive allele, we set up a stochastic model with an explicit genetic makeup of linked and unlinked deleterious alleles. Based on the theory of reducible multitype branching processes, we derive a recursive expression for the establishment probability of the beneficial allele after a single hybridization event. We furthermore study the probability that slightly deleterious alleles hitchhike to fixation. The key to the analysis is a split of the process into a stochastic phase in which the advantageous alleles establishes and a deterministic phase in which it sweeps to fixation. We thereafter apply the theory to a set of biologically relevant scenarios such as introgression in the presence of many unlinked or few closely linked deleterious alleles. A comparison to computer simulations shows that the approximations work well over a large parameter range.},
author = {Uecker, Hildegard and Setter, Derek and Hermisson, Joachim},
journal = {Journal of Mathematical Biology},
number = {7},
pages = {1523 -- 1580},
publisher = {Springer},
title = {{Adaptive gene introgression after secondary contact}},
doi = {10.1007/s00285-014-0802-y},
volume = {70},
year = {2015},
}
@article{1700,
abstract = {We use the dual boson approach to reveal the phase diagram of the Fermi-Hubbard model with long-range dipole-dipole interactions. By using a large-scale finite-temperature calculation on a 64×64 square lattice we demonstrate the existence of a novel phase, possessing an "ultralong-range" order. The fingerprint of this phase - the density correlation function - features a nontrivial behavior on a scale of tens of lattice sites. We study the properties and the stability of the ultralong-range-ordered phase, and show that it is accessible in modern experiments with ultracold polar molecules and magnetic atoms.},
author = {Van Loon, Erik and Katsnelson, Mikhail and Lemeshko, Mikhail},
journal = {Physical Review B},
number = {8},
publisher = {American Physical Society},
title = {{Ultralong-range order in the Fermi-Hubbard model with long-range interactions}},
doi = {10.1103/PhysRevB.92.081106},
volume = {92},
year = {2015},
}
@article{1701,
abstract = {The activity of a neural network is defined by patterns of spiking and silence from the individual neurons. Because spikes are (relatively) sparse, patterns of activity with increasing numbers of spikes are less probable, but, with more spikes, the number of possible patterns increases. This tradeoff between probability and numerosity is mathematically equivalent to the relationship between entropy and energy in statistical physics. We construct this relationship for populations of up to N = 160 neurons in a small patch of the vertebrate retina, using a combination of direct and model-based analyses of experiments on the response of this network to naturalistic movies. We see signs of a thermodynamic limit, where the entropy per neuron approaches a smooth function of the energy per neuron as N increases. The form of this function corresponds to the distribution of activity being poised near an unusual kind of critical point. We suggest further tests of criticality, and give a brief discussion of its functional significance. },
author = {Tkacik, Gasper and Mora, Thierry and Marre, Olivier and Amodei, Dario and Palmer, Stephanie and Berry Ii, Michael and Bialek, William},
journal = {PNAS},
number = {37},
pages = {11508 -- 11513},
publisher = {National Academy of Sciences},
title = {{Thermodynamics and signatures of criticality in a network of neurons}},
doi = {10.1073/pnas.1514188112},
volume = {112},
year = {2015},
}
@article{1704,
abstract = {Given a convex function (Formula presented.) and two hermitian matrices A and B, Lewin and Sabin study in (Lett Math Phys 104:691–705, 2014) the relative entropy defined by (Formula presented.). Among other things, they prove that the so-defined quantity is monotone if and only if (Formula presented.) is operator monotone. The monotonicity is then used to properly define (Formula presented.) for bounded self-adjoint operators acting on an infinite-dimensional Hilbert space by a limiting procedure. More precisely, for an increasing sequence of finite-dimensional projections (Formula presented.) with (Formula presented.) strongly, the limit (Formula presented.) is shown to exist and to be independent of the sequence of projections (Formula presented.). The question whether this sequence converges to its "obvious" limit, namely (Formula presented.), has been left open. We answer this question in principle affirmatively and show that (Formula presented.). If the operators A and B are regular enough, that is (A − B), (Formula presented.) and (Formula presented.) are trace-class, the identity (Formula presented.) holds.},
author = {Deuchert, Andreas and Hainzl, Christian and Seiringer, Robert},
journal = {Letters in Mathematical Physics},
number = {10},
pages = {1449 -- 1466},
publisher = {Springer},
title = {{Note on a family of monotone quantum relative entropies}},
doi = {10.1007/s11005-015-0787-5},
volume = {105},
year = {2015},
}
@inproceedings{1706,
abstract = {We consider a problem of learning kernels for use in SVM classification in the multi-task and lifelong scenarios and provide generalization bounds on the error of a large margin classifier. Our results show that, under mild conditions on the family of kernels used for learning, solving several related tasks simultaneously is beneficial over single task learning. In particular, as the number of observed tasks grows, assuming that in the considered family of kernels there exists one that yields low approximation error on all tasks, the overhead associated with learning such a kernel vanishes and the complexity converges to that of learning when this good kernel is given to the learner.},
author = {Pentina, Anastasia and Ben David, Shai},
location = {Banff, AB, Canada},
pages = {194 -- 208},
publisher = {Springer},
title = {{Multi-task and lifelong learning of kernels}},
doi = {10.1007/978-3-319-24486-0_13},
volume = {9355},
year = {2015},
}
@article{1709,
abstract = {The competition for resources among cells, individuals or species is a fundamental characteristic of evolution. Biological all-pay auctions have been used to model situations where multiple individuals compete for a single resource. However, in many situations multiple resources with various values exist and single reward auctions are not applicable. We generalize the model to multiple rewards and study the evolution of strategies. In biological all-pay auctions the bid of an individual corresponds to its strategy and is equivalent to its payment in the auction. The decreasingly ordered rewards are distributed according to the decreasingly ordered bids of the participating individuals. The reproductive success of an individual is proportional to its fitness given by the sum of the rewards won minus its payments. Hence, successful bidding strategies spread in the population. We find that the results for the multiple reward case are very different from the single reward case. While the mixed strategy equilibrium in the single reward case with more than two players consists of mostly low-bidding individuals, we show that the equilibrium can convert to many high-bidding individuals and a few low-bidding individuals in the multiple reward case. Some reward values lead to a specialization among the individuals where one subpopulation competes for the rewards and the other subpopulation largely avoids costly competitions. Whether the mixed strategy equilibrium is an evolutionarily stable strategy (ESS) depends on the specific values of the rewards.},
author = {Reiter, Johannes and Kanodia, Ayush and Gupta, Raghav and Nowak, Martin and Chatterjee, Krishnendu},
journal = {Proceedings of the Royal Society of London Series B Biological Sciences},
number = {1812},
publisher = {Royal Society},
title = {{Biological auctions with multiple rewards}},
doi = {10.1098/rspb.2015.1041},
volume = {282},
year = {2015},
}
@article{1710,
abstract = {We consider the hollow on the half-plane {(x, y) : y ≤ 0} ⊂ ℝ2 defined by a function u : (-1, 1) → ℝ, u(x) < 0, and a vertical flow of point particles incident on the hollow. It is assumed that u satisfies the so-called single impact condition (SIC): each incident particle is elastically reflected by graph(u) and goes away without hitting the graph of u anymore. We solve the problem: find the function u minimizing the force of resistance created by the flow. We show that the graph of the minimizer is formed by two arcs of parabolas symmetric to each other with respect to the y-axis. Assuming that the resistance of u ≡ 0 equals 1, we show that the minimal resistance equals π/2 - 2arctan(1/2) ≈ 0.6435. This result completes the previously obtained result [SIAM J. Math. Anal., 46 (2014), pp. 2730-2742] stating in particular that the minimal resistance of a hollow in higher dimensions equals 0.5. We additionally consider a similar problem of minimal resistance, where the hollow in the half-space {(x1,...,xd,y) : y ≤ 0} ⊂ ℝd+1 is defined by a radial function U satisfying the SIC, U(x) = u(|x|), with x = (x1,...,xd), u(ξ) < 0 for 0 ≤ ξ < 1, and u(ξ) = 0 for ξ ≥ 1, and the flow is parallel to the y-axis. The minimal resistance is greater than 0.5 (and coincides with 0.6435 when d = 1) and converges to 0.5 as d → ∞.},
author = {Akopyan, Arseniy and Plakhov, Alexander},
journal = {Society for Industrial and Applied Mathematics},
number = {4},
pages = {2754 -- 2769},
publisher = {SIAM},
title = {{Minimal resistance of curves under the single impact assumption}},
doi = {10.1137/140993843},
volume = {47},
year = {2015},
}
@article{1712,
abstract = {The majority of immune cells in Drosophila melanogaster are plasmatocytes; they carry out similar functions to vertebrate macrophages, influencing development as well as protecting against infection and cancer. Plasmatocytes, sometimes referred to with the broader term of hemocytes, migrate widely during embryonic development and cycle in the larvae between sessile and circulating positions. Here we discuss the similarities of plasmatocyte developmental migration and its functions to that of vertebrate macrophages, considering the recent controversy regarding the functions of Drosophila PDGF/VEGF related ligands. We also examine recent findings on the significance of adhesion for plasmatocyte migration in the embryo, as well as proliferation, trans-differentiation, and tumor responses in the larva. We spotlight parallels throughout to vertebrate immune responses.},
author = {Ratheesh, Aparna and Belyaeva, Vera and Siekhaus, Daria E},
journal = {Current Opinion in Cell Biology},
number = {10},
pages = {71 -- 79},
publisher = {Elsevier},
title = {{Drosophila immune cell migration and adhesion during embryonic development and larval immune responses}},
doi = {10.1016/j.ceb.2015.07.003},
volume = {36},
year = {2015},
}
@article{1730,
abstract = {How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart). Our work builds upon Riemannian systolic inequalities, which bound the minimum length of non-trivial closed curves in terms of the genus and the area of the surface. We first describe a systematic way to translate Riemannian systolic inequalities to a discrete setting, and vice-versa. This implies a conjecture by Przytycka and Przytycki (Graph structure theory. Contemporary Mathematics, vol. 147, 1993), a number of new systolic inequalities in the discrete setting, and the fact that a theorem of Hutchinson on the edge-width of triangulated surfaces and Gromov’s systolic inequality for surfaces are essentially equivalent. We also discuss how these proofs generalize to higher dimensions. Then we focus on topological decompositions of surfaces. Relying on ideas of Buser, we prove the existence of pants decompositions of length O(g^(3/2)n^(1/2)) for any triangulated combinatorial surface of genus g with n triangles, and describe an O(gn)-time algorithm to compute such a decomposition. Finally, we consider the problem of embedding a cut graph (or more generally a cellular graph) with a given combinatorial map on a given surface. Using random triangulations, we prove (essentially) that, for any choice of a combinatorial map, there are some surfaces on which any cellular embedding with that combinatorial map has length superlinear in the number of triangles of the triangulated combinatorial surface. There is also a similar result for graphs embedded on polyhedral triangulations.},
author = {Colin De Verdière, Éric and Hubard, Alfredo and De Mesmay, Arnaud N},
journal = {Discrete & Computational Geometry},
number = {3},
pages = {587 -- 620},
publisher = {Springer},
title = {{Discrete systolic inequalities and decompositions of triangulated surfaces}},
doi = {10.1007/s00454-015-9679-9},
volume = {53},
year = {2015},
}
@article{1731,
abstract = {We consider two-player zero-sum games on graphs. These games can be classified on the basis of the information of the players and on the mode of interaction between them. On the basis of information the classification is as follows: (a) partial-observation (both players have partial view of the game); (b) one-sided complete-observation (one player has complete observation); and (c) complete-observation (both players have complete view of the game). On the basis of mode of interaction we have the following classification: (a) concurrent (both players interact simultaneously); and (b) turn-based (both players interact in turn). The two sources of randomness in these games are randomness in transition function and randomness in strategies. In general, randomized strategies are more powerful than deterministic strategies, and randomness in transitions gives more general classes of games. In this work we present a complete characterization for the classes of games where randomness is not helpful in: (a) the transition function probabilistic transition can be simulated by deterministic transition); and (b) strategies (pure strategies are as powerful as randomized strategies). As consequence of our characterization we obtain new undecidability results for these games. },
author = {Chatterjee, Krishnendu and Doyen, Laurent and Gimbert, Hugo and Henzinger, Thomas A},
journal = {Information and Computation},
number = {12},
pages = {3 -- 16},
publisher = {Elsevier},
title = {{Randomness for free}},
doi = {10.1016/j.ic.2015.06.003},
volume = {245},
year = {2015},
}
@inproceedings{1732,
abstract = {We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.},
author = {Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Raghav and Kanodia, Ayush},
location = {Seattle, WA, United States},
pages = {325 -- 330},
publisher = {IEEE},
title = {{Qualitative analysis of POMDPs with temporal logic specifications for robotics applications}},
doi = {10.1109/ICRA.2015.7139019},
year = {2015},
}
@article{1735,
abstract = {This work presents a method for efficiently simplifying the pressure projection step in a liquid simulation. We first devise a straightforward dimension reduction technique that dramatically reduces the cost of solving the pressure projection. Next, we introduce a novel change of basis that satisfies free-surface boundary conditions exactly, regardless of the accuracy of the pressure solve. When combined, these ideas greatly reduce the computational complexity of the pressure solve without compromising free surface boundary conditions at the highest level of detail. Our techniques are easy to parallelize, and they effectively eliminate the computational bottleneck for large liquid simulations.},
author = {Ando, Ryoichi and Thürey, Nils and Wojtan, Christopher J},
journal = {Computer Graphics Forum},
number = {2},
pages = {473 -- 480},
publisher = {Wiley},
title = {{A dimension-reduced pressure solver for liquid simulations}},
doi = {10.1111/cgf.12576},
volume = {34},
year = {2015},
}
@article{1789,
abstract = {Intellectual disability (ID) has an estimated prevalence of 2-3%. Due to its extreme heterogeneity, the genetic basis of ID remains elusive in many cases. Recently, whole exome sequencing (WES) studies revealed that a large proportion of sporadic cases are caused by de novo gene variants. To identify further genes involved in ID, we performed WES in 250 patients with unexplained ID and their unaffected parents and included exomes of 51 previously sequenced child-parents trios in the analysis. Exome analysis revealed de novo intragenic variants in SET domain-containing 5 (SETD5) in two patients. One patient carried a nonsense variant, and the other an 81 bp deletion located across a splice-donor site. Chromosomal microarray diagnostics further identified four de novo non-recurrent microdeletions encompassing SETD5. CRISPR/Cas9 mutation modelling of the two intragenic variants demonstrated nonsense-mediated decay of the resulting transcripts, pointing to a loss-of-function (LoF) and haploinsufficiency as the common disease-causing mechanism of intragenic SETD5 sequence variants and SETD5-containing microdeletions. In silico domain prediction of SETD5, a predicted SET domain-containing histone methyltransferase (HMT), substantiated the presence of a SET domain and identified a novel putative PHD domain, strengthening a functional link to well-known histone-modifying ID genes. All six patients presented with ID and certain facial dysmorphisms, suggesting that SETD5 sequence variants contribute substantially to the microdeletion 3p25.3 phenotype. The present report of two SETD5 LoF variants in 301 patients demonstrates a prevalence of 0.7% and thus SETD5 variants as a relatively frequent cause of ID.},
author = {Kuechler, Alma and Zink, Alexander and Wieland, Thomas and Lüdecke, Hermann and Cremer, Kirsten and Salviati, Leonardo and Magini, Pamela and Najafi, Kimia and Zweier, Christiane and Czeschik, Johanna and Aretz, Stefan and Endele, Sabine and Tamburrino, Federica and Pinato, Claudia and Clementi, Maurizio and Gundlach, Jasmin and Maylahn, Carina and Mazzanti, Laura and Wohlleber, Eva and Schwarzmayr, Thomas and Kariminejad, Roxana and Schlessinger, Avner and Wieczorek, Dagmar and Strom, Tim and Novarino, Gaia and Engels, Hartmut},
journal = {European Journal of Human Genetics},
number = {6},
pages = {753 -- 760},
publisher = {Nature Publishing Group},
title = {{Loss-of-function variants of SETD5 cause intellectual disability and the core phenotype of microdeletion 3p25.3 syndrome}},
doi = {10.1038/ejhg.2014.165},
volume = {23},
year = {2015},
}
@article{1793,
abstract = {We present a software platform for reconstructing and analyzing the growth of a plant root system from a time-series of 3D voxelized shapes. It aligns the shapes with each other, constructs a geometric graph representation together with the function that records the time of growth, and organizes the branches into a hierarchy that reflects the order of creation. The software includes the automatic computation of structural and dynamic traits for each root in the system enabling the quantification of growth on fine-scale. These are important advances in plant phenotyping with applications to the study of genetic and environmental influences on growth.},
author = {Symonova, Olga and Topp, Christopher and Edelsbrunner, Herbert},
journal = {PLoS One},
number = {6},
publisher = {Public Library of Science},
title = {{DynamicRoots: A software platform for the reconstruction and analysis of growing plant roots}},
doi = {10.1371/journal.pone.0127657},
volume = {10},
year = {2015},
}
@article{1804,
abstract = {It is known that in classical fluids turbulence typically occurs at high Reynolds numbers. But can turbulence occur at low Reynolds numbers? Here we investigate the transition to turbulence in the classic Taylor-Couette system in which the rotating fluids are manufactured ferrofluids with magnetized nanoparticles embedded in liquid carriers. We find that, in the presence of a magnetic field transverse to the symmetry axis of the system, turbulence can occur at Reynolds numbers that are at least one order of magnitude smaller than those in conventional fluids. This is established by extensive computational ferrohydrodynamics through a detailed investigation of transitions in the flow structure, and characterization of behaviors of physical quantities such as the energy, the wave number, and the angular momentum through the bifurcations. A finding is that, as the magnetic field is increased, onset of turbulence can be determined accurately and reliably. Our results imply that experimental investigation of turbulence may be feasible by using ferrofluids. Our study of transition to and evolution of turbulence in the Taylor-Couette ferrofluidic flow system provides insights into the challenging problem of turbulence control.},
author = {Altmeyer, Sebastian and Do, Younghae and Lai, Ying},
journal = {Scientific Reports},
publisher = {Nature Publishing Group},
title = {{Transition to turbulence in Taylor-Couette ferrofluidic flow}},
doi = {10.1038/srep10781},
volume = {5},
year = {2015},
}
@article{1807,
abstract = {We study a double Cahn-Hilliard type functional related to the Gross-Pitaevskii energy of two-components Bose-Einstein condensates. In the case of large but same order intercomponent and intracomponent coupling strengths, we prove Γ-convergence to a perimeter minimisation functional with an inhomogeneous surface tension. We study the asymptotic behavior of the surface tension as the ratio between the intercomponent and intracomponent coupling strengths becomes very small or very large and obtain good agreement with the physical literature. We obtain as a consequence, symmetry breaking of the minimisers for the harmonic potential.},
author = {Goldman, Michael and Royo-Letelier, Jimena},
journal = {ESAIM - Control, Optimisation and Calculus of Variations},
number = {3},
pages = {603 -- 624},
publisher = {EDP Sciences},
title = {{Sharp interface limit for two components Bose-Einstein condensates}},
doi = {10.1051/cocv/2014040},
volume = {21},
year = {2015},
}
@article{1809,
abstract = {Background: Indirect genetic effects (IGEs) occur when genes expressed in one individual alter the expression of traits in social partners. Previous studies focused on the evolutionary consequences and evolutionary dynamics of IGEs, using equilibrium solutions to predict phenotypes in subsequent generations. However, whether or not such steady states may be reached may depend on the dynamics of interactions themselves. Results: In our study, we focus on the dynamics of social interactions and indirect genetic effects and investigate how they modify phenotypes over time. Unlike previous IGE studies, we do not analyse evolutionary dynamics; rather we consider within-individual phenotypic changes, also referred to as phenotypic plasticity. We analyse iterative interactions, when individuals interact in a series of discontinuous events, and investigate the stability of steady state solutions and the dependence on model parameters, such as population size, strength, and the nature of interactions. We show that for interactions where a feedback loop occurs, the possible parameter space of interaction strength is fairly limited, affecting the evolutionary consequences of IGEs. We discuss the implications of our results for current IGE model predictions and their limitations.},
author = {Trubenova, Barbora and Novak, Sebastian and Hager, Reinmar},
journal = {PLoS One},
number = {5},
publisher = {Public Library of Science},
title = {{Indirect genetic effects and the dynamics of social interactions}},
doi = {10.1371/journal.pone.0126907},
volume = {10},
year = {2015},
}
@article{1810,
abstract = {Combining antibiotics is a promising strategy for increasing treatment efficacy and for controlling resistance evolution. When drugs are combined, their effects on cells may be amplified or weakened, that is the drugs may show synergistic or antagonistic interactions. Recent work revealed the underlying mechanisms of such drug interactions by elucidating the drugs'; joint effects on cell physiology. Moreover, new treatment strategies that use drug combinations to exploit evolutionary tradeoffs were shown to affect the rate of resistance evolution in predictable ways. High throughput studies have further identified drug candidates based on their interactions with established antibiotics and general principles that enable the prediction of drug interactions were suggested. Overall, the conceptual and technical foundation for the rational design of potent drug combinations is rapidly developing.},
author = {Bollenbach, Mark Tobias},
journal = {Current Opinion in Microbiology},
pages = {1 -- 9},
publisher = {Elsevier},
title = {{Antimicrobial interactions: Mechanisms and implications for drug discovery and resistance evolution}},
doi = {10.1016/j.mib.2015.05.008},
volume = {27},
year = {2015},
}
@article{1811,
abstract = {Atomic form factors are widely used for the characterization of targets and specimens, from crystallography to biology. By using recent mathematical results, here we derive an analytical expression for the atomic form factor within the independent particle model constructed from nonrelativistic screened hydrogenic wave functions. The range of validity of this analytical expression is checked by comparing the analytically obtained form factors with the ones obtained within the Hartee-Fock method. As an example, we apply our analytical expression for the atomic form factor to evaluate the differential cross section for Rayleigh scattering off neutral atoms.},
author = {Safari, Laleh and Santos, José and Amaro, Pedro and Jänkälä, Kari and Fratini, Filippo},
journal = {Journal of Mathematical Physics},
number = {5},
publisher = {American Institute of Physics},
title = {{Analytical evaluation of atomic form factors: Application to Rayleigh scattering}},
doi = {10.1063/1.4921227},
volume = {56},
year = {2015},
}
@article{1812,
abstract = {We investigate the occurrence of rotons in a quadrupolar Bose–Einstein condensate confined to two dimensions. Depending on the particle density, the ratio of the contact and quadrupole–quadrupole interactions, and the alignment of the quadrupole moments with respect to the confinement plane, the dispersion relation features two or four point-like roton minima or one ring-shaped minimum. We map out the entire parameter space of the roton behavior and identify the instability regions. We propose to observe the exotic rotons by monitoring the characteristic density wave dynamics resulting from a short local perturbation, and discuss the possibilities to detect the predicted effects in state-of-the-art experiments with ultracold homonuclear molecules.
},
author = {Lahrz, Martin and Lemeshko, Mikhail and Mathey, Ludwig},
journal = {New Journal of Physics},
number = {4},
publisher = {IOP Publishing Ltd.},
title = {{Exotic roton excitations in quadrupolar Bose–Einstein condensates }},
doi = {10.1088/1367-2630/17/4/045005},
volume = {17},
year = {2015},
}
@article{1813,
abstract = {We develop a microscopic theory describing a quantum impurity whose rotational degree of freedom is coupled to a many-particle bath. We approach the problem by introducing the concept of an “angulon”—a quantum rotor dressed by a quantum field—and reveal its quasiparticle properties using a combination of variational and diagrammatic techniques. Our theory predicts renormalization of the impurity rotational structure, such as that observed in experiments with molecules in superfluid helium droplets, in terms of a rotational Lamb shift induced by the many-particle environment. Furthermore, we discover a rich many-body-induced fine structure, emerging in rotational spectra due to a redistribution of angular momentum within the quantum many-body system.},
author = {Schmidt, Richard and Lemeshko, Mikhail},
journal = {Physical Review Letters},
number = {20},
publisher = {American Physical Society},
title = {{Rotation of quantum impurities in the presence of a many-body environment}},
doi = {10.1103/PhysRevLett.114.203001},
volume = {114},
year = {2015},
}
@article{1814,
abstract = {We present an efficient wavefront tracking algorithm for animating bodies of water that interact with their environment. Our contributions include: a novel wavefront tracking technique that enables dispersion, refraction, reflection, and diffraction in the same simulation; a unique multivalued function interpolation method that enables our simulations to elegantly sidestep the Nyquist limit; a dispersion approximation for efficiently amplifying the number of simulated waves by several orders of magnitude; and additional extensions that allow for time-dependent effects and interactive artistic editing of the resulting animation. Our contributions combine to give us multitudes more wave details than similar algorithms, while maintaining high frame rates and allowing close camera zooms.},
author = {Jeschke, Stefan and Wojtan, Christopher J},
journal = {ACM Transactions on Graphics},
number = {3},
publisher = {ACM},
title = {{Water wave animation via wavefront parameter interpolation}},
doi = {10.1145/2714572},
volume = {34},
year = {2015},
}
@article{1817,
abstract = {Vertebrates have a unique 3D body shape in which correct tissue and organ shape and alignment are essential for function. For example, vision requires the lens to be centred in the eye cup which must in turn be correctly positioned in the head. Tissue morphogenesis depends on force generation, force transmission through the tissue, and response of tissues and extracellular matrix to force. Although a century ago D'Arcy Thompson postulated that terrestrial animal body shapes are conditioned by gravity, there has been no animal model directly demonstrating how the aforementioned mechano-morphogenetic processes are coordinated to generate a body shape that withstands gravity. Here we report a unique medaka fish (Oryzias latipes) mutant, hirame (hir), which is sensitive to deformation by gravity. hir embryos display a markedly flattened body caused by mutation of YAP, a nuclear executor of Hippo signalling that regulates organ size. We show that actomyosin-mediated tissue tension is reduced in hir embryos, leading to tissue flattening and tissue misalignment, both of which contribute to body flattening. By analysing YAP function in 3D spheroids of human cells, we identify the Rho GTPase activating protein ARHGAP18 as an effector of YAP in controlling tissue tension. Together, these findings reveal a previously unrecognised function of YAP in regulating tissue shape and alignment required for proper 3D body shape. Understanding this morphogenetic function of YAP could facilitate the use of embryonic stem cells to generate complex organs requiring correct alignment of multiple tissues. },
author = {Porazinski, Sean and Wang, Huijia and Asaoka, Yoichi and Behrndt, Martin and Miyamoto, Tatsuo and Morita, Hitoshi and Hata, Shoji and Sasaki, Takashi and Krens, Gabriel and Osada, Yumi and Asaka, Satoshi and Momoi, Akihiro and Linton, Sarah and Miesfeld, Joel and Link, Brian and Senga, Takeshi and Castillo Morales, Atahualpa and Urrutia, Araxi and Shimizu, Nobuyoshi and Nagase, Hideaki and Matsuura, Shinya and Bagby, Stefan and Kondoh, Hisato and Nishina, Hiroshi and Heisenberg, Carl-Philipp J and Furutani Seiki, Makoto},
journal = {Nature},
number = {7551},
pages = {217 -- 221},
publisher = {Nature Publishing Group},
title = {{YAP is essential for tissue tension to ensure vertebrate 3D body shape}},
doi = {10.1038/nature14215},
volume = {521},
year = {2015},
}
@article{1818,
abstract = {Why do species not adapt to ever-wider ranges of conditions, gradually expanding their ecological niche and geographic range? Gene flow across environments has two conflicting effects: although it increases genetic variation, which is a prerequisite for adaptation, gene flow may swamp adaptation to local conditions. In 1956, Haldane proposed that, when the environment varies across space, "swamping" by gene flow creates a positive feedback between low population size and maladaptation, leading to a sharp range margin. However, current deterministic theory shows that, when variance can evolve, there is no such limit. Using simple analytical tools and simulations, we show that genetic drift can generate a sharp margin to a species' range, by reducing genetic variance below the level needed for adaptation to spatially variable conditions. Aided by separation of ecological and evolutionary timescales, the identified effective dimensionless parameters reveal a simple threshold that predicts when adaptation at the range margin fails. Two observable parameters determine the threshold: (i) the effective environmental gradient, which can be measured by the loss of fitness due to dispersal to a different environment; and (ii) the efficacy of selection relative to genetic drift. The theory predicts sharp range margins even in the absence of abrupt changes in the environment. Furthermore, it implies that gradual worsening of conditions across a species' habitat may lead to a sudden range fragmentation, when adaptation to a wide span of conditions within a single species becomes impossible.},
author = {Polechova, Jitka and Barton, Nicholas H},
journal = {PNAS},
number = {20},
pages = {6401 -- 6406},
publisher = {National Academy of Sciences},
title = {{Limits to adaptation along environmental gradients}},
doi = {10.1073/pnas.1421515112},
volume = {112},
year = {2015},
}
@inproceedings{1820,
abstract = {We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objec- tive we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present ap- proximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst- case running time of our algorithm is double exponential, we present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples.},
author = {Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Raghav and Kanodia, Ayush},
booktitle = {Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence },
location = {Austin, TX, USA},
pages = {3496--3502},
publisher = {AAAI Press},
title = {{Optimal cost almost-sure reachability in POMDPs}},
volume = {5},
year = {2015},
}