@misc{5400,
abstract = {We consider partially observable Markov decision processes (POMDPs) with ω-regular conditions specified as parity objectives. The class of ω-regular languages extends regular languages to infinite strings and provides a robust specification language to express all properties used in verification, and parity objectives are canonical forms to express ω-regular conditions. The qualitative analysis problem given a POMDP and a parity objective asks whether there is a strategy to ensure that the objective is satis- fied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, we establish decidability (with optimal complexity) of the qualitative analysis problems for POMDPs with all parity objectives under finite- memory strategies. We establish asymptotically optimal (exponential) memory bounds and EXPTIME- completeness of the qualitative analysis problems under finite-memory strategies for POMDPs with parity objectives.},
author = {Chatterjee, Krishnendu and Chmelik, Martin and Tracol, Mathieu},
issn = {2664-1690},
pages = {41},
publisher = {IST Austria},
title = {{What is decidable about partially observable Markov decision processes with ω-regular objectives}},
doi = {10.15479/AT:IST-2013-109-v1-1},
year = {2013},
}
@techreport{5401,
abstract = {This document is created as a part of the project “Repository for Research Data at IST Austria”. It summarises the actual initiatives, projects and standards related to the project. It supports the preparation of standards and specifications for the project, which should be considered and followed to ensure interoperability and visibility of the uploaded data.},
author = {Porsche, Jana},
publisher = {IST Austria},
title = {{Initiatives and projects related to RD}},
year = {2013},
}
@misc{5402,
abstract = {Linearizability requires that the outcome of calls by competing threads to a concurrent data structure is the same as some sequential execution where each thread has exclusive access to the data structure. In an ordered data structure, such as a queue or a stack, linearizability is ensured by requiring threads commit in the order dictated by the sequential semantics of the data structure; e.g., in a concurrent queue implementation a dequeue can only remove the oldest element.
In this paper, we investigate the impact of this strict ordering, by comparing what linearizability allows to what existing implementations do. We first give an operational definition for linearizability which allows us to build the most general linearizable implementation as a transition system for any given sequential specification. We then use this operational definition to categorize linearizable implementations based on whether they are bound or free. In a bound implementation, whenever all threads observe the same logical state, the updates to the logical state and the temporal order of commits coincide. All existing queue implementations we know of are bound. We then proceed to present, to the best of our knowledge, the first ever free queue implementation. Our experiments show that free implementations have the potential for better performance by suffering less from contention.},
author = {Henzinger, Thomas A and Sezgin, Ali},
issn = {2664-1690},
pages = {16},
publisher = {IST Austria},
title = {{How free is your linearizable concurrent data structure?}},
doi = {10.15479/AT:IST-2013-123-v1-1},
year = {2013},
}
@misc{5403,
abstract = {We consider concurrent games played by two-players on a finite state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to every transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of mean-payoff games) that is not known to be in polynomial time.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus},
issn = {2664-1690},
pages = {33},
publisher = {IST Austria},
title = {{Qualitative analysis of concurrent mean-payoff games}},
doi = {10.15479/AT:IST-2013-126-v1-1},
year = {2013},
}
@misc{5404,
abstract = {We study finite-state two-player (zero-sum) concurrent mean-payoff games played on a graph. We focus on the important sub-class of ergodic games where all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy); (2) the approximation problem lie in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP and coNP is the long-standing best known bound). We show that the exact value can be expressed in the existential theory of the reals, and also establish square-root sum hardness for a related class of games.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus},
issn = {2664-1690},
pages = {29},
publisher = {IST Austria},
title = {{The complexity of ergodic games}},
doi = {10.15479/AT:IST-2013-127-v1-1},
year = {2013},
}
@misc{5405,
abstract = {The theory of graph games is the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic processes, we use 2-1/2-player games where some transitions of the game graph are controlled by two adversarial players, the System and the Environment, and the other transitions are determined probabilistically. We consider 2-1/2-player games where the objective of the System is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a mean-payoff condition). We establish that the problem of deciding whether the System can ensure that the probability to satisfy the mean-payoff parity objective is at least a given threshold is in NP ∩ coNP, matching the best known bound in the special case of 2-player games (where all transitions are deterministic) with only parity objectives, or with only mean-payoff objectives. We present an algorithm running
in time O(d · n^{2d}·MeanGame) to compute the set of almost-sure winning states from which the objective
can be ensured with probability 1, where n is the number of states of the game, d the number of priorities
of the parity objective, and MeanGame is the complexity to compute the set of almost-sure winning states
in 2-1/2-player mean-payoff games. Our results are useful in the synthesis of stochastic reactive systems
with both functional requirement (given as a qualitative objective) and performance requirement (given
as a quantitative objective).},
author = {Chatterjee, Krishnendu and Doyen, Laurent and Gimbert, Hugo and Oualhadj, Youssouf},
issn = {2664-1690},
pages = {22},
publisher = {IST Austria},
title = {{Perfect-information stochastic mean-payoff parity games}},
doi = {10.15479/AT:IST-2013-128-v1-1},
year = {2013},
}
@misc{5406,
abstract = {We consider the distributed synthesis problem fortemporal logic specifications. Traditionally, the problem has been studied for LTL, and the previous results show that the problem is decidable iff there is no information fork in the architecture. We consider the problem for fragments of LTLand our main results are as follows: (1) We show that the problem is undecidable for architectures with information forks even for the fragment of LTL with temporal operators restricted to next and eventually. (2) For specifications restricted to globally along with non-nested next operators, we establish decidability (in EXPSPACE) for star architectures where the processes receive disjoint inputs, whereas we establish undecidability for architectures containing an information fork-meet structure. (3)Finally, we consider LTL without the next operator, and establish decidability (NEXPTIME-complete) for all architectures for a fragment that consists of a set of safety assumptions, and a set of guarantees where each guarantee is a safety, reachability, or liveness condition.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan and Pavlogiannis, Andreas},
issn = {2664-1690},
pages = {11},
publisher = {IST Austria},
title = {{Distributed synthesis for LTL Fragments}},
doi = {10.15479/AT:IST-2013-130-v1-1},
year = {2013},
}
@techreport{5407,
abstract = {This document is created as a part of the project “Repository for Research Data at IST Austria”. It summarises the mandatory features, which need to be fulfilled to provide an institutional repository as a platform and also a service to the scientists at the institute. It also includes optional features, which would be of strong benefit for the scientists and would increase the usage of the repository, and hence the visibility of research at IST Austria.},
author = {Porsche, Jana},
publisher = {IST Austria},
title = {{Technical requirements and features}},
year = {2013},
}
@misc{5408,
abstract = {We consider two-player partial-observation stochastic games where player 1 has partial observation and player 2 has perfect observation. The winning condition we study are omega-regular conditions specified as parity objectives. The qualitative analysis problem given a partial-observation stochastic game and a parity objective asks whether there is a strategy to ensure that the objective is satisfied with probability 1 (resp. positive probability). While the qualitative analysis problems are known to be undecidable even for very special cases of parity objectives, they were shown to be decidable in 2EXPTIME under finite-memory strategies. We improve the complexity and show that the qualitative analysis problems for partial-observation stochastic parity games under finite-memory strategies are
EXPTIME-complete; and also establish optimal (exponential) memory bounds for finite-memory strategies required for qualitative analysis. },
author = {Chatterjee, Krishnendu and Doyen, Laurent and Nain, Sumit and Vardi, Moshe},
issn = {2664-1690},
pages = {17},
publisher = {IST Austria},
title = {{The complexity of partial-observation stochastic parity games with finite-memory strategies}},
doi = {10.15479/AT:IST-2013-141-v1-1},
year = {2013},
}
@misc{5409,
abstract = {The edit distance between two (untimed) traces is the minimum cost of a sequence of edit operations (insertion, deletion, or substitution) needed to transform one trace to the other. Edit distances have been extensively studied in the untimed setting, and form the basis for approximate matching of sequences in different domains such as coding theory, parsing, and speech recognition.
In this paper, we lift the study of edit distances from untimed languages to the timed setting. We define an edit distance between timed words which incorporates both the edit distance between the untimed words and the absolute difference in timestamps. Our edit distance between two timed words is computable in polynomial time. Further, we show that the edit distance between a timed word and a timed language generated by a timed automaton, defined as the edit distance between the word and the closest word in the language, is PSPACE-complete. While computing the edit distance between two timed automata is undecidable, we show that the approximate version, where we decide if the edit distance between two timed automata is either less than a given parameter or more than delta away from the parameter, for delta>0, can be solved in exponential space and is EXPSPACE-hard. Our definitions and techniques can be generalized to the setting of hybrid systems, and we show analogous decidability results for rectangular automata.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Majumdar, Rupak},
issn = {2664-1690},
pages = {12},
publisher = {IST Austria},
title = {{Edit distance for timed automata}},
doi = {10.15479/AT:IST-2013-144-v1-1},
year = {2013},
}
@misc{5410,
abstract = {Board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in development of mathematical and logical skills, but also in emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants.
Our approach generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. Also, the presence of such states for standard game variants like Tic-Tac-Toe on board size 4x4 opens up new games to be played that have not been played for ages since the default start state is heavily biased. },
author = {Ahmed, Umair and Chatterjee, Krishnendu and Gulwani, Sumit},
issn = {2664-1690},
pages = {13},
publisher = {IST Austria},
title = {{Automatic generation of alternative starting positions for traditional board games}},
doi = {10.15479/AT:IST-2013-146-v1-1},
year = {2013},
}
@inbook{5747,
author = {Dragoi, Cezara and Gupta, Ashutosh and Henzinger, Thomas A},
booktitle = {Computer Aided Verification},
isbn = {9783642397981},
issn = {0302-9743},
location = {Saint Petersburg, Russia},
pages = {174--190},
publisher = {Springer Berlin Heidelberg},
title = {{Automatic Linearizability Proofs of Concurrent Objects with Cooperating Updates}},
doi = {10.1007/978-3-642-39799-8_11},
volume = {8044},
year = {2013},
}
@article{2698,
abstract = {We consider non-interacting particles subject to a fixed external potential V and a self-generated magnetic field B. The total energy includes the field energy β∫B2 and we minimize over all particle states and magnetic fields. In the case of spin-1/2 particles this minimization leads to the coupled Maxwell-Pauli system. The parameter β tunes the coupling strength between the field and the particles and it effectively determines the strength of the field. We investigate the stability and the semiclassical asymptotics, h→0, of the total ground state energy E(β,h,V). The relevant parameter measuring the field strength in the semiclassical limit is κ=βh. We are not able to give the exact leading order semiclassical asymptotics uniformly in κ or even for fixed κ. We do however give upper and lower bounds on E with almost matching dependence on κ. In the simultaneous limit h→0 and κ→∞ we show that the standard non-magnetic Weyl asymptotics holds. The same result also holds for the spinless case, i.e. where the Pauli operator is replaced by the Schrödinger operator.},
author = {Erdös, László and Fournais, Søren and Solovej, Jan},
journal = {Journal of the European Mathematical Society},
number = {6},
pages = {2093 -- 2113},
publisher = {European Mathematical Society},
title = {{Stability and semiclassics in self-generated fields}},
doi = {10.4171/JEMS/416},
volume = {15},
year = {2013},
}
@inproceedings{2718,
abstract = {Even though both population and quantitative genetics, and evolutionary computation, deal with the same questions, they have developed largely independently of each other. I review key results from each field, emphasising those that apply independently of the (usually unknown) relation between genotype and phenotype. The infinitesimal model provides a simple framework for predicting the response of complex traits to selection, which in biology has proved remarkably successful. This allows one to choose the schedule of population sizes and selection intensities that will maximise the response to selection, given that the total number of individuals realised, C = ∑t Nt, is constrained. This argument shows that for an additive trait (i.e., determined by the sum of effects of the genes), the optimum population size and the maximum possible response (i.e., the total change in trait mean) are both proportional to √C.},
author = {Barton, Nicholas H and Paixao, Tiago},
booktitle = {Proceedings of the 15th annual conference on Genetic and evolutionary computation},
location = {Amsterdam, Netherlands},
pages = {1573 -- 1580},
publisher = {ACM},
title = {{Can quantitative and population genetics help us understand evolutionary computation?}},
doi = {10.1145/2463372.2463568},
year = {2013},
}
@inproceedings{2719,
abstract = {Prediction of the evolutionary process is a long standing problem both in the theory of evolutionary biology and evolutionary computation (EC). It has long been realized that heritable variation is crucial to both the response to selection and the success of genetic algorithms. However, not all variation contributes in the same way to the response. Quantitative genetics has developed a large body of work trying to estimate and understand how different components of the variance in fitness in the population contribute to the response to selection. We illustrate how to apply some concepts of quantitative genetics to the analysis of genetic algorithms. In particular, we derive estimates for the short term prediction of the response to selection and we use variance decomposition to gain insight on local aspects of the landscape. Finally, we propose a new population based genetic algorithm that uses these methods to improve its operation.},
author = {Paixao, Tiago and Barton, Nicholas H},
booktitle = {Proceedings of the 15th annual conference on Genetic and evolutionary computation},
location = {Amsterdam, Netherlands},
pages = {845 -- 852},
publisher = {ACM},
title = {{A variance decomposition approach to the analysis of genetic algorithms}},
doi = {10.1145/2463372.2463470},
year = {2013},
}
@article{2720,
abstract = {Knowledge of the rate and fitness effects of mutations is essential for understanding the process of evolution. Mutations are inherently difficult to study because they are rare and are frequently eliminated by natural selection. In the ciliate Tetrahymena thermophila, mutations can accumulate in the germline genome without being exposed to selection. We have conducted a mutation accumulation (MA) experiment in this species. Assuming that all mutations are deleterious and have the same effect, we estimate that the deleterious mutation rate per haploid germline genome per generation is U = 0.0047 (95% credible interval: 0.0015, 0.0125), and that germline mutations decrease fitness by s = 11% when expressed in a homozygous state (95% CI: 4.4%, 27%). We also estimate that deleterious mutations are partially recessive on average (h = 0.26; 95% CI: –0.022, 0.62) and that the rate of lethal mutations is <10% of the deleterious mutation rate. Comparisons between the observed evolutionary responses in the germline and somatic genomes and the results from individual-based simulations of MA suggest that the two genomes have similar mutational parameters. These are the first estimates of the deleterious mutation rate and fitness effects from the eukaryotic supergroup Chromalveolata and are within the range of those of other eukaryotes.},
author = {Long, Hongan and Paixao, Tiago and Azevedo, Ricardo and Zufall, Rebecca},
journal = {Genetics},
number = {2},
pages = {527--540},
publisher = {Genetics Society of America},
title = {{Accumulation of spontaneous mutations in the ciliate Tetrahymena thermophila}},
doi = {10.1534/genetics.113.153536},
volume = {195},
year = {2013},
}
@article{2782,
abstract = {We consider random n×n matrices of the form (XX*+YY*)^{-1/2}YY*(XX*+YY*)^{-1/2}, where X and Y have independent entries with zero mean and variance one. These matrices are the natural generalization of the Gaussian case, which are known as MANOVA matrices and which have joint eigenvalue density given by the third classical ensemble, the Jacobi ensemble. We show that, away from the spectral edge, the eigenvalue density converges to the limiting density of the Jacobi ensemble even on the shortest possible scales of order 1/n (up to log n factors). This result is the analogue of the local Wigner semicircle law and the local Marchenko-Pastur law for general MANOVA matrices.},
author = {Erdös, László and Farrell, Brendan},
journal = {Journal of Statistical Physics},
number = {6},
pages = {1003 -- 1032},
publisher = {Springer},
title = {{Local eigenvalue density for general MANOVA matrices}},
doi = {10.1007/s10955-013-0807-8},
volume = {152},
year = {2013},
}
@article{2806,
abstract = {A novel Taylor-Couette system has been constructed for investigations of transitional as well as high Reynolds number turbulent flows in very large aspect ratios. The flexibility of the setup enables studies of a variety of problems regarding hydrodynamic instabilities and turbulence in rotating flows. The inner and outer cylinders and the top and bottom endplates can be rotated independently with rotation rates of up to 30 Hz, thereby covering five orders of magnitude in Reynolds numbers (Re = 101-106). The radius ratio can be easily changed, the highest realized one is η = 0.98 corresponding to an aspect ratio of 260 gap width in the vertical and 300 in the azimuthal direction. For η < 0.98 the aspect ratio can be dynamically changed during measurements and complete transparency in the radial direction over the full length of the cylinders is provided by the usage of a precision glass inner cylinder. The temperatures of both cylinders are controlled independently. Overall this apparatus combines an unmatched variety in geometry, rotation rates, and temperatures, which is provided by a sophisticated high-precision bearing system. Possible applications are accurate studies of the onset of turbulence and spatio-temporal intermittent flow patterns in very large domains, transport processes of turbulence at high Re, the stability of Keplerian flows for different boundary conditions, and studies of baroclinic instabilities.},
author = {Avila, Kerstin and Hof, Björn},
journal = {Review of Scientific Instruments},
number = {6},
publisher = {American Institute of Physics},
title = {{High-precision Taylor-Couette experiment to study subcritical transitions and the role of boundary conditions and size effects}},
doi = {10.1063/1.4807704},
volume = {84},
year = {2013},
}
@inproceedings{2807,
abstract = {We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of computational complexity. The extension problem asks, given topological spaces X; Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that X and Y are represented as finite simplicial complexes, A is a subcomplex of X, and f is given as a simplicial map. In this generality the problem is undecidable, as follows from Novikov's result from the 1950s on uncomputability of the fundamental group π1(Y ). We thus study the problem under the assumption that, for some k ≥ 2, Y is (k - 1)-connected; informally, this means that Y has \no holes up to dimension k-1" (a basic example of such a Y is the sphere Sk). We prove that, on the one hand, this problem is still undecidable for dimX = 2k. On the other hand, for every fixed k ≥ 2, we obtain an algorithm that solves the extension problem in polynomial time assuming Y (k - 1)-connected and dimX ≤ 2k - 1. For dimX ≤ 2k - 2, the algorithm also provides a classification of all extensions up to homotopy (continuous deformation). This relies on results of our SODA 2012 paper, and the main new ingredient is a machinery of objects with polynomial-time homology, which is a polynomial-time analog of objects with effective homology developed earlier by Sergeraert et al. We also consider the computation of the higher homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, Anick proved in 1989 that computing πk(Y ) is #P-hard if k is a part of input, where Y is a cell complex with certain rather compact encoding. We strengthen his result to #P-hardness for Y given as a simplicial complex. },
author = {Čadek, Martin and Krcál, Marek and Matoušek, Jiří and Vokřínek, Lukáš and Wagner, Uli},
booktitle = {45th Annual ACM Symposium on theory of computing},
location = {Palo Alto, CA, United States},
pages = {595 -- 604},
publisher = {ACM},
title = {{Extending continuous maps: Polynomiality and undecidability}},
doi = {10.1145/2488608.2488683},
year = {2013},
}
@article{2808,
abstract = {In order to establish a reference for analysis of the function of auxin and the auxin biosynthesis regulators SHORT INTERNODE/ STYLISH (SHI/STY) during Physcomitrella patens reproductive development, we have described male (antheridial) and female (archegonial) development in detail, including temporal and positional information of organ initiation. This has allowed us to define discrete stages of organ morphogenesis and to show that reproductive organ development in P. patens is highly organized and that organ phyllotaxis differs between vegetative and reproductive development. Using the PpSHI1 and PpSHI2 reporter and knockout lines, the auxin reporters GmGH3pro:GUS and PpPINApro:GFP-GUS, and the auxin-conjugating transgene PpSHI2pro:IAAL, we could show that the PpSHI genes, and by inference also auxin, play important roles for reproductive organ development in moss. The PpSHI genes are required for the apical opening of the reproductive organs, the final differentiation of the egg cell, and the progression of canal cells into a cell death program. The apical cells of the archegonium, the canal cells, and the egg cell are also sites of auxin responsiveness and are affected by reduced levels of active auxin, suggesting that auxin mediates PpSHI function in the reproductive organs.},
author = {Landberg, Katarina and Pederson, Eric and Viaene, Tom and Bozorg, Behruz and Friml, Jirí and Jönsson, Henrik and Thelander, Mattias and Sundberg, Eva},
journal = {Plant Physiology},
number = {3},
pages = {1406 -- 1419},
publisher = {American Society of Plant Biologists},
title = {{The moss physcomitrella patens reproductive organ development is highly organized, affected by the two SHI/STY genes and by the level of active auxin in the SHI/STY expression domain}},
doi = {10.1104/pp.113.214023},
volume = {162},
year = {2013},
}
@article{2810,
abstract = {The epistatic interactions that underlie evolutionary constraint have mainly been studied for constant external conditions. However, environmental changes may modulate epistasis and hence affect genetic constraints. Here we investigate genetic constraints in the adaptive evolution of a novel regulatory function in variable environments, using the lac repressor, LacI, as a model system. We have systematically reconstructed mutational trajectories from wild type LacI to three different variants that each exhibit an inverse response to the inducing ligand IPTG, and analyzed the higher-order interactions between genetic and environmental changes. We find epistasis to depend strongly on the environment. As a result, mutational steps essential to inversion but inaccessible by positive selection in one environment, become accessible in another. We present a graphical method to analyze the observed complex higher-order interactions between multiple mutations and environmental change, and show how the interactions can be explained by a combination of mutational effects on allostery and thermodynamic stability. This dependency of genetic constraint on the environment should fundamentally affect evolutionary dynamics and affects the interpretation of phylogenetic data.},
author = {De Vos, Marjon and Poelwijk, Frank and Battich, Nico and Ndika, Joseph and Tans, Sander},
journal = {PLoS Genetics},
number = {6},
publisher = {Public Library of Science},
title = {{Environmental dependence of genetic constraint}},
doi = {10.1371/journal.pgen.1003580},
volume = {9},
year = {2013},
}
@article{2811,
abstract = {In pipe, channel, and boundary layer flows turbulence first occurs intermittently in space and time: at moderate Reynolds numbers domains of disordered turbulent motion are separated by quiescent laminar regions. Based on direct numerical simulations of pipe flow we argue here that the spatial intermittency has its origin in a nearest neighbor interaction between turbulent regions. We further show that in this regime turbulent flows are intrinsically intermittent with a well-defined equilibrium turbulent fraction but without ever assuming a steady pattern. This transition scenario is analogous to that found in simple models such as coupled map lattices. The scaling observed implies that laminar intermissions of the turbulent flow will persist to arbitrarily large Reynolds numbers.},
author = {Avila, Marc and Hof, Björn},
journal = {Physical Review E},
number = {6},
publisher = {American Institute of Physics},
title = {{Nature of laminar-turbulence intermittency in shear flows}},
doi = {10.1103/PhysRevE.87.063012},
volume = {87},
year = {2013},
}
@inproceedings{2812,
abstract = {We consider the problem of deciding whether the persistent homology group of a simplicial pair (K, L) can be realized as the homology H* (X) of some complex X with L ⊂ X ⊂ K. We show that this problem is NP-complete even if K is embedded in ℝ3. As a consequence, we show that it is NP-hard to simplify level and sublevel sets of scalar functions on S3 within a given tolerance constraint. This problem has relevance to the visualization of medical images by isosurfaces. We also show an implication to the theory of well groups of scalar functions: not every well group can be realized by some level set, and deciding whether a well group can be realized is NP-hard.},
author = {Attali, Dominique and Bauer, Ulrich and Devillers, Olivier and Glisse, Marc and Lieutier, André},
booktitle = {Proceedings of the 29th annual symposium on Computational Geometry},
location = {Rio de Janeiro, Brazil},
pages = {117 -- 125},
publisher = {ACM},
title = {{Homological reconstruction and simplification in R3}},
doi = {10.1145/2462356.2462373},
year = {2013},
}
@article{2813,
abstract = {Turbulence is ubiquitous in nature, yet even for the case of ordinary Newtonian fluids like water, our understanding of this phenomenon is limited. Many liquids of practical importance are more complicated (e.g., blood, polymer melts, paints), however; they exhibit elastic as well as viscous characteristics, and the relation between stress and strain is nonlinear. We demonstrate here for a model system of such complex fluids that at high shear rates, turbulence is not simply modified as previously believed but is suppressed and replaced by a different type of disordered motion, elasto-inertial turbulence. Elasto-inertial turbulence is found to occur at much lower Reynolds numbers than Newtonian turbulence, and the dynamical properties differ significantly. The friction scaling observed coincides with the so-called "maximum drag reduction" asymptote, which is exhibited by a wide range of viscoelastic fluids.},
author = {Samanta, Devranjan and Dubief, Yves and Holzner, Markus and Schäfer, Christof and Morozov, Alexander and Wagner, Christian and Hof, Björn},
journal = {PNAS},
number = {26},
pages = {10557 -- 10562},
publisher = {National Academy of Sciences},
title = {{Elasto-inertial turbulence}},
doi = {10.1073/pnas.1219666110},
volume = {110},
year = {2013},
}
@article{2814,
abstract = {We study the problem of generating a test sequence that achieves maximal coverage for a reactive system under test. We formulate the problem as a repeated game between the tester and the system, where the system state space is partitioned according to some coverage criterion and the objective of the tester is to maximize the set of partitions (or coverage goals) visited during the game. We show the complexity of the maximal coverage problem for non-deterministic systems is PSPACE-complete, but is NP-complete for deterministic systems. For the special case of non-deterministic systems with a re-initializing "reset" action, which represent running a new test input on a re-initialized system, we show that the complexity is coNP-complete. Our proof technique for reset games uses randomized testing strategies that circumvent the exponentially large memory requirement of deterministic testing strategies. We also discuss the memory requirement for deterministic strategies and extensions of our results to other models, such as pushdown systems and timed systems.},
author = {Chatterjee, Krishnendu and Alfaro, Luca and Majumdar, Ritankar},
journal = {International Journal of Foundations of Computer Science},
number = {2},
pages = {165 -- 185},
publisher = {World Scientific Publishing},
title = {{The complexity of coverage}},
doi = {10.1142/S0129054113400066},
volume = {24},
year = {2013},
}
@article{2815,
abstract = {The fact that a sum of isotropic Gaussian kernels can have more modes than kernels is surprising. Extra (ghost) modes do not exist in ℝ1 and are generally not well studied in higher dimensions. We study a configuration of n+1 Gaussian kernels for which there are exactly n+2 modes. We show that all modes lie on a finite set of lines, which we call axes, and study the restriction of the Gaussian mixture to these axes in order to discover that there are an exponential number of critical points in this configuration. Although the existence of ghost modes remained unknown due to the difficulty of finding examples in ℝ2, we show that the resilience of ghost modes grows like the square root of the dimension. In addition, we exhibit finite configurations of isotropic Gaussian kernels with superlinearly many modes.},
author = {Edelsbrunner, Herbert and Fasy, Brittany Terese and Rote, Günter},
journal = {Discrete & Computational Geometry},
number = {4},
pages = {797 -- 822},
publisher = {Springer},
title = {{Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions}},
doi = {10.1007/s00454-013-9517-x},
volume = {49},
year = {2013},
}
@article{2816,
abstract = {In solid tumors, targeted treatments can lead to dramatic regressions, but responses are often short-lived because resistant cancer cells arise. The major strategy proposed for overcoming resistance is combination therapy. We present a mathematical model describing the evolutionary dynamics of lesions in response to treatment. We first studied 20 melanoma patients receiving vemurafenib. We then applied our model to an independent set of pancreatic, colorectal, and melanoma cancer patients with metastatic disease. We find that dual therapy results in long-term disease control for most patients, if there are no single mutations that cause cross-resistance to both drugs; in patients with large disease burden, triple therapy is needed. We also find that simultaneous therapy with two drugs is much more effective than sequential therapy. Our results provide realistic expectations for the efficacy of new drug combinations and inform the design of trials for new cancer therapeutics.},
author = {Božić, Ivana and Reiter, Johannes and Allen, Benjamin and Antal, Tibor and Chatterjee, Krishnendu and Shah, Preya and Moon, Yo and Yaqubie, Amin and Kelly, Nicole and Le, Dung and Lipson, Evan and Chapman, Paul and Diaz, Luis and Vogelstein, Bert and Nowak, Martin},
journal = {eLife},
publisher = {eLife Sciences Publications},
title = {{Evolutionary dynamics of cancer in response to targeted combination therapy}},
doi = {10.7554/eLife.00747},
volume = {2},
year = {2013},
}
@article{2817,
abstract = {The basic idea of evolutionary game theory is that payoff determines reproductive rate. Successful individuals have a higher payoff and produce more offspring. But in evolutionary and ecological situations there is not only reproductive rate but also carrying capacity. Individuals may differ in their exposure to density limiting effects. Here we explore an alternative approach to evolutionary game theory by assuming that the payoff from the game determines the carrying capacity of individual phenotypes. Successful strategies are less affected by density limitation (crowding) and reach higher equilibrium abundance. We demonstrate similarities and differences between our framework and the standard replicator equation. Our equation is defined on the positive orthant, instead of the simplex, but has the same equilibrium points as the replicator equation. Linear stability analysis produces the classical conditions for asymptotic stability of pure strategies, but the stability properties of internal equilibria can differ in the two frameworks. For example, in a two-strategy game with an internal equilibrium that is always stable under the replicator equation, the corresponding equilibrium can be unstable in the new framework resulting in a limit cycle.},
author = {Novak, Sebastian and Chatterjee, Krishnendu and Nowak, Martin},
journal = {Journal of Theoretical Biology},
pages = {26 -- 34},
publisher = {Elsevier},
title = {{Density games}},
doi = {10.1016/j.jtbi.2013.05.029},
volume = {334},
year = {2013},
}
@article{2818,
abstract = {Models of neural responses to stimuli with complex spatiotemporal correlation structure often assume that neurons are selective for only a small number of linear projections of a potentially high-dimensional input. In this review, we explore recent modeling approaches where the neural response depends on the quadratic form of the input rather than on its linear projection, that is, the neuron is sensitive to the local covariance structure of the signal preceding the spike. To infer this quadratic dependence in the presence of arbitrary (e.g., naturalistic) stimulus distribution, we review several inference methods, focusing in particular on two information theory–based approaches (maximization of stimulus energy and of noise entropy) and two likelihood-based approaches (Bayesian spike-triggered covariance and extensions of generalized linear models). We analyze the formal relationship between the likelihood-based and information-based approaches to demonstrate how they lead to consistent inference. We demonstrate the practical feasibility of these procedures by using model neurons responding to a flickering variance stimulus.},
author = {Rajan, Kanaka and Marre, Olivier and Tkacik, Gasper},
journal = {Neural Computation},
number = {7},
pages = {1661 -- 1692},
publisher = {MIT Press },
title = {{Learning quadratic receptive fields from neural responses to natural stimuli}},
doi = {10.1162/NECO_a_00463},
volume = {25},
year = {2013},
}
@inproceedings{2819,
abstract = {We introduce quantatitive timed refinement metrics and quantitative timed simulation functions, incorporating zenoness checks, for timed systems. These functions assign positive real numbers between zero and infinity which quantify the timing mismatches between two timed systems, amongst non-zeno runs. We quantify timing mismatches in three ways: (1) the maximum timing mismatch that can arise, (2) the "steady-state" maximum timing mismatches, where initial transient timing mismatches are ignored; and (3) the (long-run) average timing mismatches amongst two systems. These three kinds of mismatches constitute three important types of timing differences. Our event times are the global times, measured from the start of the system execution, not just the time durations of individual steps. We present algorithms over timed automata for computing the three quantitative simulation functions to within any desired degree of accuracy. In order to compute the values of the quantitative simulation functions, we use a game theoretic formulation. We introduce two new kinds of objectives for two player games on finite state game graphs: (1) eventual debit-sum level objectives, and (2) average debit-sum level objectives. We present algorithms for computing the optimal values for these objectives for player 1, and then use these algorithms to compute the values of the quantitative timed simulation functions. },
author = {Chatterjee, Krishnendu and Prabhu, Vinayak},
booktitle = {Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control},
location = {Philadelphia, PA USA},
pages = {273 -- 282},
publisher = {Springer},
title = {{Quantitative timed simulation functions and refinement metrics for real-time systems}},
doi = {10.1145/2461328.2461370},
volume = {1},
year = {2013},
}
@inproceedings{2820,
abstract = {In this paper, we introduce the powerful framework of graph games for the analysis of real-time scheduling with firm deadlines. We introduce a novel instance of a partial-observation game that is suitable for this purpose, and prove decidability of all the involved decision problems. We derive a graph game that allows the automated computation of the competitive ratio (along with an optimal witness algorithm for the competitive ratio) and establish an NP-completeness proof for the graph game problem. For a given on-line algorithm, we present polynomial time solution for computing (i) the worst-case utility; (ii) the worst-case utility ratio w.r.t. a clairvoyant off-line algorithm; and (iii) the competitive ratio. A major strength of the proposed approach lies in its flexibility w.r.t. incorporating additional constraints on the adversary and/or the algorithm, including limited maximum or average load, finiteness of periods of overload, etc., which are easily added by means of additional instances of standard objective functions for graph games. },
author = {Chatterjee, Krishnendu and Kößler, Alexander and Schmid, Ulrich},
booktitle = {Proceedings of the 16th International conference on Hybrid systems: Computation and control},
isbn = {978-1-4503-1567-8 },
location = {Philadelphia, PA, United States},
pages = {163 -- 172},
publisher = {ACM},
title = {{Automated analysis of real-time scheduling using graph games}},
doi = {10.1145/2461328.2461356},
year = {2013},
}
@article{2821,
abstract = {Many key aspects of plant development are regulated by the polarized transport of the phytohormone auxin. Cellular auxin efflux, the rate-limiting step in this process, has been shown to rely on the coordinated action of PIN-formed (PIN) and B-type ATP binding cassette (ABCB) carriers. Here, we report that polar auxin transport in the Arabidopsis thaliana root also requires the action of a Major Facilitator Superfamily (MFS) transporter, Zinc-Induced Facilitator-Like 1 (ZIFL1). Sequencing, promoter-reporter, and fluorescent protein fusion experiments indicate that the full-length ZIFL1.1 protein and a truncated splice isoform, ZIFL1.3, localize to the tonoplast of root cells and the plasma membrane of leaf stomatal guard cells, respectively. Using reverse genetics, we show that the ZIFL1.1 transporter regulates various root auxin-related processes, while the ZIFL1.3 isoform mediates drought tolerance by regulating stomatal closure. Auxin transport and immunolocalization assays demonstrate that ZIFL1.1 indirectly modulates cellular auxin efflux during shootward auxin transport at the root tip, likely by regulating plasma membrane PIN2 abundance. Finally, heterologous expression in yeast revealed that ZIFL1.1 and ZIFL1.3 share H+-coupled K+ transport activity. Thus, by determining the subcellular and tissue distribution of two isoforms, alternative splicing dictates a dual function for the ZIFL1 transporter. We propose that this MFS carrier regulates stomatal movements and polar auxin transport by modulating potassium and proton fluxes in Arabidopsis cells.},
author = {Remy, Estelle and Cabrito, Tânia and Baster, Pawel and Batista, Rita and Teixeira, Miguel and Friml, Jirí and Sá Correia, Isabel and Duque, Paula},
journal = {Plant Cell},
number = {3},
pages = {901 -- 926},
publisher = {American Society of Plant Biologists},
title = {{A major facilitator superfamily transporter plays a dual role in polar auxin transport and drought stress tolerance in Arabidopsis}},
doi = {10.1105/tpc.113.110353},
volume = {25},
year = {2013},
}
@article{2822,
abstract = {Identification of genes that control root system architecture in crop plants requires innovations that enable high-throughput and accurate measurements of root system architecture through time. We demonstrate the ability of a semiautomated 3D in vivo imaging and digital phenotyping pipeline to interrogate the quantitative genetic basis of root system growth in a rice biparental mapping population, Bala x Azucena. We phenotyped >1,400 3D root models and >57,000 2D images for a suite of 25 traits that quantified the distribution, shape, extent of exploration, and the intrinsic size of root networks at days 12, 14, and 16 of growth in a gellan gum medium. From these data we identified 89 quantitative trait loci, some of which correspond to those found previously in soil-grown plants, and provide evidence for genetic tradeoffs in root growth allocations, such as between the extent and thoroughness of exploration. We also developed a multivariate method for generating and mapping central root architecture phenotypes and used it to identify five major quantitative trait loci (r2 = 24-37%), two of which were not identified by our univariate analysis. Our imaging and analytical platform provides a means to identify genes with high potential for improving root traits and agronomic qualities of crops.},
author = {Topp, Christopher and Iyer Pascuzzi, Anjali and Anderson, Jill and Lee, Cheng and Zurek, Paul and Symonova, Olga and Zheng, Ying and Bucksch, Alexander and Mileyko, Yuriy and Galkovskyi, Taras and Moore, Brad and Harer, John and Edelsbrunner, Herbert and Mitchell Olds, Thomas and Weitz, Joshua and Benfey, Philip},
journal = {PNAS},
number = {18},
pages = {E1695 -- E1704},
publisher = {National Academy of Sciences},
title = {{3D phenotyping and quantitative trait locus mapping identify core regions of the rice genome controlling root architecture}},
doi = {10.1073/pnas.1304354110},
volume = {110},
year = {2013},
}
@article{2823,
abstract = {The primary goal of restoration is to create self-sustaining ecological communities that are resilient to periodic disturbance. Currently, little is known about how restored communities respond to disturbance events such as fire and how this response compares to remnant vegetation. Following the 2003 fires in south-eastern Australia we examined the post-fire response of revegetation plantings and compared this to remnant vegetation. Ten burnt and 10 unburnt (control) sites were assessed for each of three types of vegetation (direct seeding revegetation, revegetation using nursery seedlings (tubestock) and remnant woodland). Sixty sampling sites were surveyed 6months after fire to quantify the initial survival of mid- and overstorey plant species in each type of vegetation. Three and 5years after fire all sites were resurveyed to assess vegetation structure, species diversity and vigour, as well as indicators of soil function. Overall, revegetation showed high (>60%) post-fire survival, but this varied among species depending on regeneration strategy (obligate seeder or resprouter). The native ground cover, mid- and overstorey in both types of plantings showed rapid recovery of vegetation structure and cover within 3years of fire. This recovery was similar to the burnt remnant woodlands. Non-native (exotic) ground cover initially increased after fire, but was no different in burnt and unburnt sites 5years after fire. Fire had no effect on species richness, but burnt direct seeding sites had reduced species diversity (Simpson's Diversity Index) while diversity was higher in burnt remnant woodlands. Indices of soil function in all types of vegetation had recovered to levels found in unburnt sites 5years after fire. These results indicate that even young revegetation (stands <10years old) showed substantial recovery from disturbance by fire. This suggests that revegetation can provide an important basis for restoring woodland communities in the fire-prone Australian environment.},
author = {Pickup, Melinda and Wilson, Susie and Freudenberger, David and Nicholls, Nick and Gould, Lori and Hnatiuk, Sarah and Delandre, Jeni},
journal = {Austral Ecology},
number = {3},
pages = {300 -- 312},
publisher = {Wiley-Blackwell},
title = {{Post-fire recovery of revegetated woodland communities in south-eastern Australia}},
doi = {10.1111/j.1442-9993.2012.02404.x},
volume = {38},
year = {2013},
}
@article{2824,
abstract = {We study synthesis of controllers for real-time systems, where the objective is to stay in a given safe set. The problem is solved by obtaining winning strategies in the setting of concurrent two player timed automaton games with safety objectives. To prevent a player from winning by blocking time, we restrict each player to strategies that ensure that the player cannot be responsible for causing a Zeno run. We construct winning strategies for the controller which require access only to (1) the system clocks (thus, controllers which require their own internal infinitely precise clocks are not necessary), and (2) a logarithmic (in the number of clocks) number of memory bits (i.e. a linear number of memory states). Precisely, we show that for safety objectives, a memory of size (3 + lg (| C | + 1)) bits suffices for winning controller strategies, where C is the set of clocks of the timed automaton game, significantly improving the previous known exponential memory states bound. We also settle the open question of whether winning region-based strategies require memory for safety objectives by showing with an example the necessity of memory for such strategies to win for safety objectives. Finally, we show that the decision problem of determining if there exists a receptive player-1 winning strategy for safety objectives is EXPTIME-complete over timed automaton games.},
author = {Chatterjee, Krishnendu and Prabhu, Vinayak},
journal = {Information and Computation},
pages = {83--119},
publisher = {Elsevier},
title = {{Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems}},
doi = {10.1016/j.ic.2013.04.003},
volume = {228-229},
year = {2013},
}
@article{2827,
abstract = {Removal of cargos from the cell surface via endocytosis is an efficient mechanism to regulate activities of plasma membrane (PM)-resident proteins, such as receptors or transporters. Salicylic acid (SA) is an important plant hormone that is traditionally associated with pathogen defense. Here, we describe an unanticipated effect of SA on subcellular endocytic cycling of proteins. Both exogenous treatments and endogenously enhanced SA levels repressed endocytosis of different PM proteins. The SA effect on endocytosis did not involve transcription or known components of the SA signaling pathway for transcriptional regulation. SA likely targets an endocytic mechanism that involves the coat protein clathrin, because SA interfered with the clathrin incidence at the PM and clathrin-deficient mutants were less sensitive to the impact of SA on the auxin distribution and root bending during the gravitropic response. By contrast, SA did not affect the ligand-induced endocytosis of the FLAGELLIN SENSING2 (FLS2) receptor during pathogen responses. Our data suggest that the established SA impact on transcription in plant immunity and the nontranscriptional effect of SA on clathrin-mediated endocytosis are independent mechanisms by which SA regulates distinct aspects of plant physiology.},
author = {Du, Yunlong and Tejos, Ricardo and Beck, Martina and Himschoot, Ellie and Li, Hongjiang and Robatzek, Silke and Vanneste, Steffen and Friml, Jirí},
journal = {PNAS},
number = {19},
pages = {7946 -- 7951},
publisher = {National Academy of Sciences},
title = {{Salicylic acid interferes with clathrin-mediated endocytic protein trafficking}},
doi = {10.1073/pnas.1220205110},
volume = {110},
year = {2013},
}
@article{2828,
abstract = {We study the complexity of valued constraint satisfaction problems (VCSPs) parametrized by a constraint language, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from the language and the goal is to minimize the sum. Under the unique games conjecture, the approximability of finite-valued VCSPs is well understood, see Raghavendra [2008]. However, there is no characterization of finite-valued VCSPs, let alone general-valued VCSPs, that can be solved exactly in polynomial time, thus giving insights from a combinatorial optimization perspective. We consider the case of languages containing all possible unary cost functions. In the case of languages consisting of only {0, ∞}-valued cost functions (i.e., relations), such languages have been called conservative and studied by Bulatov [2003, 2011] and recently by Barto [2011]. Since we study valued languages, we call a language conservative if it contains all finite-valued unary cost functions. The computational complexity of conservative valued languages has been studied by Cohen et al. [2006] for languages over Boolean domains, by Deineko et al. [2008] for {0, 1}-valued languages (a.k.a Max-CSP), and by Takhanov [2010a] for {0, ∞}-valued languages containing all finite-valued unary cost functions (a.k.a. Min-Cost-Hom). We prove a Schaefer-like dichotomy theorem for conservative valued languages: if all cost functions in the language satisfy a certain condition (specified by a complementary combination of STP and MJN multimor-phisms), then any instance can be solved in polynomial time (via a new algorithm developed in this article), otherwise the language is NP-hard. This is the first complete complexity classification of general-valued constraint languages over non-Boolean domains. It is a common phenomenon that complexity classifications of problems over non-Boolean domains are significantly harder than the Boolean cases. The polynomial-time algorithm we present for the tractable cases is a generalization of the submodular minimization problem and a result of Cohen et al. [2008]. Our results generalize previous results by Takhanov [2010a] and (a subset of results) by Cohen et al. [2006] and Deineko et al. [2008]. Moreover, our results do not rely on any computer-assisted search as in Deineko et al. [2008], and provide a powerful tool for proving hardness of finite-valued and general-valued languages.},
author = {Kolmogorov, Vladimir and Živný, Stanislav},
journal = {Journal of the ACM},
number = {2},
publisher = {ACM},
title = {{The complexity of conservative valued CSPs}},
doi = {10.1145/2450142.2450146},
volume = {60},
year = {2013},
}
@article{2829,
abstract = {Laminar-turbulent intermittency is intrinsic to the transitional regime of a wide range of fluid flows including pipe, channel, boundary layer, and Couette flow. In the latter turbulent spots can grow and form continuous stripes, yet in the stripe-normal direction they remain interspersed by laminar fluid. We carry out direct numerical simulations in a long narrow domain and observe that individual turbulent stripes are transient. In agreement with recent observations in pipe flow, we find that turbulence becomes sustained at a distinct critical point once the spatial proliferation outweighs the inherent decaying process. By resolving the asymptotic size distributions close to criticality we can for the first time demonstrate scale invariance at the onset of turbulence.},
author = {Shi, Liang and Avila, Marc and Hof, Björn},
journal = {Physical Review Letters},
number = {20},
publisher = {American Physical Society},
title = {{Scale invariance at the onset of turbulence in couette flow}},
doi = {10.1103/PhysRevLett.110.204502},
volume = {110},
year = {2013},
}
@article{2830,
author = {Moussion, Christine and Sixt, Michael K},
journal = {Immunity},
number = {5},
pages = {853 -- 854},
publisher = {Cell Press},
title = {{A conduit to amplify innate immunity}},
doi = {10.1016/j.immuni.2013.05.005},
volume = {38},
year = {2013},
}
@article{2831,
abstract = {We consider Markov decision processes (MDPs) with Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with Büchi objectives; our algorithm takes O(n · √ m) symbolic steps as compared to the previous known algorithm that takes O(n 2) symbolic steps, where n is the number of states and m is the number of edges of the MDP. In practice MDPs have constant out-degree, and then our symbolic algorithm takes O(n · √ n) symbolic steps, as compared to the previous known O(n 2) symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination; and (b) requires O(n · √ K) symbolic steps, where K is the maximal number of edges of strongly connected components (scc's) of the MDP. The win-lose algorithm requires symbolic computation of scc's. Third, we improve the algorithm for symbolic scc computation; the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5×n symbolic steps, whereas our new algorithm takes 4×n symbolic steps.},
author = {Chatterjee, Krishnendu and Henzinger, Monika and Joglekar, Manas and Shah, Nisarg},
journal = {Formal Methods in System Design},
number = {3},
pages = {301 -- 327},
publisher = {Springer},
title = {{Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives}},
doi = {10.1007/s10703-012-0180-2},
volume = {42},
year = {2013},
}
@article{2832,
abstract = {PIN-FORMED (PIN) proteins localize asymmetrically at the plasma membrane and mediate intercellular polar transport of the plant hormone auxin that is crucial for a multitude of developmental processes in plants. PIN localization is under extensive control by environmental or developmental cues, but mechanisms regulating PIN localization are not fully understood. Here we show that early endosomal components ARF GEF BEN1 and newly identified Sec1/Munc18 family protein BEN2 are involved in distinct steps of early endosomal trafficking. BEN1 and BEN2 are collectively required for polar PIN localization, for their dynamic repolarization, and consequently for auxin activity gradient formation and auxin-related developmental processes including embryonic patterning, organogenesis, and vasculature venation patterning. These results show that early endosomal trafficking is crucial for cell polarity and auxin-dependent regulation of plant architecture.},
author = {Tanaka, Hirokazu and Kitakura, Saeko and Rakusová, Hana and Uemura, Tomohiro and Feraru, Mugurel and De Rycke, Riet and Robert, Stéphanie and Kakimoto, Tatsuo and Friml, Jirí},
journal = {PLoS Genetics},
number = {5},
publisher = {Public Library of Science},
title = {{Cell polarity and patterning by PIN trafficking through early endosomal compartments in arabidopsis thaliana}},
doi = {10.1371/journal.pgen.1003540},
volume = {9},
year = {2013},
}
@article{2833,
abstract = {During development, mechanical forces cause changes in size, shape, number, position, and gene expression of cells. They are therefore integral to any morphogenetic processes. Force generation by actin-myosin networks and force transmission through adhesive complexes are two self-organizing phenomena driving tissue morphogenesis. Coordination and integration of forces by long-range force transmission and mechanosensing of cells within tissues produce large-scale tissue shape changes. Extrinsic mechanical forces also control tissue patterning by modulating cell fate specification and differentiation. Thus, the interplay between tissue mechanics and biochemical signaling orchestrates tissue morphogenesis and patterning in development.},
author = {Heisenberg, Carl-Philipp J and Bellaïche, Yohanns},
journal = {Cell},
number = {5},
pages = {948 -- 962},
publisher = {Cell Press},
title = {{Forces in tissue morphogenesis and patterning}},
doi = {10.1016/j.cell.2013.05.008},
volume = {153},
year = {2013},
}
@article{2834,
abstract = {Although the equations governing fluid flow are well known, there are no analytical expressions that describe the complexity of turbulent motion. A recent proposition is that in analogy to low dimensional chaotic systems, turbulence is organized around unstable solutions of the governing equations which provide the building blocks of the disordered dynamics. We report the discovery of periodic solutions which just like intermittent turbulence are spatially localized and show that turbulent transients arise from one such solution branch.},
author = {Avila, Marc and Mellibovsky, Fernando and Roland, Nicolas and Hof, Björn},
journal = {Physical Review Letters},
number = {22},
publisher = {American Physical Society},
title = {{Streamwise-localized solutions at the onset of turbulence in pipe flow}},
doi = {10.1103/PhysRevLett.110.224502},
volume = {110},
year = {2013},
}
@article{2835,
abstract = {The phytohormone auxin regulates virtually every aspect of plant development. To identify new genes involved in auxin activity, a genetic screen was performed for Arabidopsis (Arabidopsis thaliana) mutants with altered expression of the auxin-responsive reporter DR5rev:GFP. One of the mutants recovered in the screen, designated as weak auxin response3 (wxr3), exhibits much lower DR5rev:GFP expression when treated with the synthetic auxin 2,4-dichlorophenoxyacetic acid and displays severe defects in root development. The wxr3 mutant decreases polar auxin transport and results in a disruption of the asymmetric auxin distribution. The levels of the auxin transporters AUXIN1 and PIN-FORMED are dramatically reduced in the wxr3 root tip. Molecular analyses demonstrate that WXR3 is ROOT ULTRAVIOLET B-SENSITIVE1 (RUS1), a member of the conserved Domain of Unknown Function647 protein family found in diverse eukaryotic organisms. Our data suggest that RUS1/WXR3 plays an essential role in the regulation of polar auxin transport by maintaining the proper level of auxin transporters on the plasma membrane.},
author = {Yu, Hong and Karampelias, Michael and Robert, Stéphanie and Peer, Wendy and Swarup, Ranjan and Ye, Songqing and Ge, Lei and Cohen, Jerry and Murphy, Angus and Friml, Jirí and Estelle, Mark},
journal = {Plant Physiology},
number = {2},
pages = {965 -- 976},
publisher = {American Society of Plant Biologists},
title = {{Root ultraviolet b-sensitive1/weak auxin response3 is essential for polar auxin transport in arabidopsis}},
doi = {10.1104/pp.113.217018},
volume = {162},
year = {2013},
}
@article{2836,
abstract = {We study the automatic synthesis of fair non-repudiation protocols, a class of fair exchange protocols, used for digital contract signing. First, we show how to specify the objectives of the participating agents and the trusted third party as path formulas in linear temporal logic and prove that the satisfaction of these objectives imply fairness; a property required of fair exchange protocols. We then show that weak (co-operative) co-synthesis and classical (strictly competitive) co-synthesis fail, whereas assume-guarantee synthesis (AGS) succeeds. We demonstrate the success of AGS as follows: (a) any solution of AGS is attack-free; no subset of participants can violate the objectives of the other participants; (b) the Asokan-Shoup-Waidner certified mail protocol that has known vulnerabilities is not a solution of AGS; (c) the Kremer-Markowitch non-repudiation protocol is a solution of AGS; and (d) AGS presents a new and symmetric fair non-repudiation protocol that is attack-free. To our knowledge this is the first application of synthesis to fair non-repudiation protocols, and our results show how synthesis can both automatically discover vulnerabilities in protocols and generate correct protocols. The solution to AGS can be computed efficiently as the secure equilibrium solution of three-player graph games. },
author = {Chatterjee, Krishnendu and Raman, Vishwanath},
journal = {Formal Aspects of Computing},
number = {4},
pages = {825 -- 859},
publisher = {Springer},
title = {{Assume-guarantee synthesis for digital contract signing}},
doi = {10.1007/s00165-013-0283-6},
volume = {26},
year = {2013},
}
@article{2837,
abstract = {We consider a general class of N × N random matrices whose entries hij are independent up to a symmetry constraint, but not necessarily identically distributed. Our main result is a local semicircle law which improves previous results [17] both in the bulk and at the edge. The error bounds are given in terms of the basic small parameter of the model, maxi,j E|hij|2. As a consequence, we prove the universality of the local n-point correlation functions in the bulk spectrum for a class of matrices whose entries do not have comparable variances, including random band matrices with band width W ≫N1-εn with some εn > 0 and with a negligible mean-field component. In addition, we provide a coherent and pedagogical proof of the local semicircle law, streamlining and strengthening previous arguments from [17, 19, 6].},
author = {Erdös, László and Knowles, Antti and Yau, Horng and Yin, Jun},
journal = {Electronic Journal of Probability},
number = {59},
pages = {1--58},
publisher = {Institute of Mathematical Statistics},
title = {{The local semicircle law for a general class of random matrices}},
doi = {10.1214/EJP.v18-2473},
volume = {18},
year = {2013},
}
@article{2838,
abstract = {Individuals with Down syndrome (DS) present important motor deficits that derive from altered motor development of infants and young children. DYRK1A, a candidate gene for DS abnormalities has been implicated in motor function due to its expression in motor nuclei in the adult brain, and its overexpression in DS mouse models leads to hyperactivity and altered motor learning. However, its precise role in the adult motor system, or its possible involvement in postnatal locomotor development has not yet been clarified. During the postnatal period we observed time-specific expression of Dyrk1A in discrete subsets of brainstem nuclei and spinal cord motor neurons. Interestingly, we describe for the first time the presence of Dyrk1A in the presynaptic terminal of the neuromuscular junctions and its axonal transport from the facial nucleus, suggesting a function for Dyrk1A in these structures. Relevant to DS, Dyrk1A overexpression in transgenic mice (TgDyrk1A) produces motor developmental alterations possibly contributing to DS motor phenotypes and modifies the numbers of motor cholinergic neurons, suggesting that the kinase may have a role in the development of the brainstem and spinal cord motor system.},
author = {Arquè Fuste, Gloria and Casanovas, Anna and Dierssen, Mara},
journal = {PLoS One},
number = {1},
publisher = {Public Library of Science},
title = {{Dyrk1A is dynamically expressed on subsets of motor neurons and in the neuromuscular junction: Possible role in Down syndrome}},
doi = {10.1371/journal.pone.0054285},
volume = {8},
year = {2013},
}
@article{2839,
abstract = {Directional guidance of cells via gradients of chemokines is considered crucial for embryonic development, cancer dissemination, and immune responses. Nevertheless, the concept still lacks direct experimental confirmation in vivo. Here, we identify endogenous gradients of the chemokine CCL21 within mouse skin and show that they guide dendritic cells toward lymphatic vessels. Quantitative imaging reveals depots of CCL21 within lymphatic endothelial cells and steeply decaying gradients within the perilymphatic interstitium. These gradients match the migratory patterns of the dendritic cells, which directionally approach vessels from a distance of up to 90-micrometers. Interstitial CCL21 is immobilized to heparan sulfates, and its experimental delocalization or swamping the endogenous gradients abolishes directed migration. These findings functionally establish the concept of haptotaxis, directed migration along immobilized gradients, in tissues.},
author = {Weber, Michele and Hauschild, Robert and Schwarz, Jan and Moussion, Christine and De Vries, Ingrid and Legler, Daniel and Luther, Sanjiv and Bollenbach, Mark Tobias and Sixt, Michael K},
journal = {Science},
number = {6117},
pages = {328 -- 332},
publisher = {American Association for the Advancement of Science},
title = {{Interstitial dendritic cell guidance by haptotactic chemokine gradients}},
doi = {10.1126/science.1228456},
volume = {339},
year = {2013},
}
@article{2840,
abstract = {It is known that the entorhinal cortex plays a crucial role in spatial cognition in rodents. Neuroanatomical and electrophysiological data suggest that there is a functional distinction between 2 subregions within the entorhinal cortex, the medial entorhinal cortex (MEC), and the lateral entorhinal cortex (LEC). Rats with MEC or LEC lesions were trained in 2 navigation tasks requiring allothetic (water maze task) or idiothetic (path integration) information processing and 2-object exploration tasks allowing testing of spatial and nonspatial processing of intramaze objects. MEC lesions mildly affected place navigation in the water maze and produced a path integration deficit. They also altered the processing of spatial information in both exploration tasks while sparing the processing of nonspatial information. LEC lesions did not affect navigation abilities in both the water maze and the path integration tasks. They altered spatial and nonspatial processing in the object exploration task but not in the one-trial recognition task. Overall, these results indicate that the MEC is important for spatial processing and path integration. The LEC has some influence on both spatial and nonspatial processes, suggesting that the 2 kinds of information interact at the level of the EC.},
author = {Van Cauter, Tiffany and Camon, Jeremy and Alvernhe, Alice and Elduayen, Coralie and Sargolini, Francesca and Save, Étienne},
journal = {Cerebral Cortex},
number = {2},
pages = {451 -- 459},
publisher = {Oxford University Press},
title = {{Distinct roles of medial and lateral entorhinal cortex in spatial cognition}},
doi = {10.1093/cercor/bhs033},
volume = {23},
year = {2013},
}
@article{2841,
abstract = {In zebrafish early development, blastoderm cells undergo extensive radial intercalations, triggering the spreading of the blastoderm over the yolk cell and thereby initiating embryonic body axis formation. Now reporting in Developmental Cell, Song et al. (2013) demonstrate a critical function for EGF-dependent E-cadherin endocytosis in promoting blastoderm cell intercalations.},
author = {Morita, Hitoshi and Heisenberg, Carl-Philipp J},
journal = {Developmental Cell},
number = {6},
pages = {567 -- 569},
publisher = {Cell Press},
title = {{Holding on and letting go: Cadherin turnover in cell intercalation}},
doi = {10.1016/j.devcel.2013.03.007},
volume = {24},
year = {2013},
}