@article{2034,
abstract = {Opacity is a generic security property, that has been defined on (non-probabilistic) transition systems and later on Markov chains with labels. For a secret predicate, given as a subset of runs, and a function describing the view of an external observer, the value of interest for opacity is a measure of the set of runs disclosing the secret. We extend this definition to the richer framework of Markov decision processes, where non-deterministicchoice is combined with probabilistic transitions, and we study related decidability problems with partial or complete observation hypotheses for the schedulers. We prove that all questions are decidable with complete observation and ω-regular secrets. With partial observation, we prove that all quantitative questions are undecidable but the question whether a system is almost surely non-opaquebecomes decidable for a restricted class of ω-regular secrets, as well as for all ω-regular secrets under finite-memory schedulers.},
author = {Bérard, Béatrice and Chatterjee, Krishnendu and Sznajder, Nathalie},
journal = { Information Processing Letters},
number = {1},
pages = {52 -- 59},
publisher = {Elsevier},
title = {{Probabilistic opacity for Markov decision processes}},
doi = {10.1016/j.ipl.2014.09.001},
volume = {115},
year = {2015},
}
@article{2035,
abstract = {Considering a continuous self-map and the induced endomorphism on homology, we study the eigenvalues and eigenspaces of the latter. Taking a filtration of representations, we define the persistence of the eigenspaces, effectively introducing a hierarchical organization of the map. The algorithm that computes this information for a finite sample is proved to be stable, and to give the correct answer for a sufficiently dense sample. Results computed with an implementation of the algorithm provide evidence of its practical utility.
},
author = {Edelsbrunner, Herbert and Jablonski, Grzegorz and Mrozek, Marian},
journal = {Foundations of Computational Mathematics},
number = {5},
pages = {1213 -- 1244},
publisher = {Springer},
title = {{The persistent homology of a self-map}},
doi = {10.1007/s10208-014-9223-y},
volume = {15},
year = {2015},
}
@article{2085,
abstract = {We study the spectrum of a large system of N identical bosons interacting via a two-body potential with strength 1/N. In this mean-field regime, Bogoliubov's theory predicts that the spectrum of the N-particle Hamiltonian can be approximated by that of an effective quadratic Hamiltonian acting on Fock space, which describes the fluctuations around a condensed state. Recently, Bogoliubov's theory has been justified rigorously in the case that the low-energy eigenvectors of the N-particle Hamiltonian display complete condensation in the unique minimizer of the corresponding Hartree functional. In this paper, we shall justify Bogoliubov's theory for the high-energy part of the spectrum of the N-particle Hamiltonian corresponding to (non-linear) excited states of the Hartree functional. Moreover, we shall extend the existing results on the excitation spectrum to the case of non-uniqueness and/or degeneracy of the Hartree minimizer. In particular, the latter covers the case of rotating Bose gases, when the rotation speed is large enough to break the symmetry and to produce multiple quantized vortices in the Hartree minimizer. },
author = {Nam, Phan and Seiringer, Robert},
journal = {Archive for Rational Mechanics and Analysis},
number = {2},
pages = {381 -- 417},
publisher = {Springer},
title = {{Collective excitations of Bose gases in the mean-field regime}},
doi = {10.1007/s00205-014-0781-6},
volume = {215},
year = {2015},
}
@article{2166,
abstract = {We consider the spectral statistics of large random band matrices on mesoscopic energy scales. We show that the correlation function of the local eigenvalue density exhibits a universal power law behaviour that differs from the Wigner-Dyson- Mehta statistics. This law had been predicted in the physics literature by Altshuler and Shklovskii in (Zh Eksp Teor Fiz (Sov Phys JETP) 91(64):220(127), 1986); it describes the correlations of the eigenvalue density in general metallic sampleswith weak disorder. Our result rigorously establishes the Altshuler-Shklovskii formulas for band matrices. In two dimensions, where the leading term vanishes owing to an algebraic cancellation, we identify the first non-vanishing term and show that it differs substantially from the prediction of Kravtsov and Lerner in (Phys Rev Lett 74:2563-2566, 1995). The proof is given in the current paper and its companion (Ann. H. Poincaré. arXiv:1309.5107, 2014). },
author = {Erdös, László and Knowles, Antti},
journal = {Communications in Mathematical Physics},
number = {3},
pages = {1365 -- 1416},
publisher = {Springer},
title = {{The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case}},
doi = {10.1007/s00220-014-2119-5},
volume = {333},
year = {2015},
}
@article{473,
abstract = {We prove that nonlinear Gibbs measures can be obtained from the corresponding many-body, grand-canonical, quantum Gibbs states, in a mean-field limit where the temperature T diverges and the interaction strength behaves as 1/T. We proceed by characterizing the interacting Gibbs state as minimizing a functional counting the free-energy relatively to the non-interacting case. We then perform an infinite-dimensional analogue of phase-space semiclassical analysis, using fine properties of the quantum relative entropy, the link between quantum de Finetti measures and upper/lower symbols in a coherent state basis, as well as Berezin-Lieb type inequalities. Our results cover the measure built on the defocusing nonlinear Schrödinger functional on a finite interval, as well as smoother interactions in dimensions d 2.},
author = {Lewin, Mathieu and Phan Thanh, Nam and Rougerie, Nicolas},
journal = {Journal de l'Ecole Polytechnique - Mathematiques},
pages = {65 -- 115},
publisher = {Ecole Polytechnique},
title = {{Derivation of nonlinear gibbs measures from many-body quantum mechanics}},
doi = {10.5802/jep.18},
volume = {2},
year = {2015},
}
@article{477,
abstract = {Dendritic cells are potent antigen-presenting cells endowed with the unique ability to initiate adaptive immune responses upon inflammation. Inflammatory processes are often associated with an increased production of serotonin, which operates by activating specific receptors. However, the functional role of serotonin receptors in regulation of dendritic cell functions is poorly understood. Here, we demonstrate that expression of serotonin receptor 5-HT7 (5-HT7TR) as well as its downstream effector Cdc42 is upregulated in dendritic cells upon maturation. Although dendritic cell maturation was independent of 5-HT7TR, receptor stimulation affected dendritic cell morphology through Cdc42-mediated signaling. In addition, basal activity of 5-HT7TR was required for the proper expression of the chemokine receptor CCR7, which is a key factor that controls dendritic cell migration. Consistent with this, we observed that 5-HT7TR enhances chemotactic motility of dendritic cells in vitro by modulating their directionality and migration velocity. Accordingly, migration of dendritic cells in murine colon explants was abolished after pharmacological receptor inhibition. Our results indicate that there is a crucial role for 5-HT7TR-Cdc42-mediated signaling in the regulation of dendritic cell morphology and motility, suggesting that 5-HT7TR could be a new target for treatment of a variety of inflammatory and immune disorders.},
author = {Holst, Katrin and Guseva, Daria and Schindler, Susann and Sixt, Michael K and Braun, Armin and Chopra, Himpriya and Pabst, Oliver and Ponimaskin, Evgeni},
journal = {Journal of Cell Science},
number = {15},
pages = {2866 -- 2880},
publisher = {Company of Biologists},
title = {{The serotonin receptor 5-HT7R regulates the morphology and migratory properties of dendritic cells}},
doi = {10.1242/jcs.167999},
volume = {128},
year = {2015},
}
@article{523,
abstract = {We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window.},
author = {Chatterjee, Krishnendu and Doyen, Laurent and Randour, Mickael and Raskin, Jean},
journal = {Information and Computation},
number = {6},
pages = {25 -- 52},
publisher = {Elsevier},
title = {{Looking at mean-payoff and total-payoff through windows}},
doi = {10.1016/j.ic.2015.03.010},
volume = {242},
year = {2015},
}
@article{524,
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 each 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 of 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 that 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 turn-based deterministic mean-payoff games) that is not known to be solvable in polynomial time.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus},
journal = {Information and Computation},
number = {6},
pages = {2 -- 24},
publisher = {Elsevier},
title = {{Qualitative analysis of concurrent mean payoff games}},
doi = {10.1016/j.ic.2015.03.009},
volume = {242},
year = {2015},
}
@article{532,
abstract = {Ethylene is a gaseous phytohormone that plays vital roles in plant growth and development. Previous studies uncovered EIN2 as an essential signal transducer linking ethylene perception on ER to transcriptional regulation in the nucleus through a “cleave and shuttle” model. In this study, we report another mechanism of EIN2-mediated ethylene signaling, whereby EIN2 imposes the translational repression of EBF1 and EBF2 mRNA. We find that the EBF1/2 3′ UTRs mediate EIN2-directed translational repression and identify multiple poly-uridylates (PolyU) motifs as functional cis elements of 3′ UTRs. Furthermore, we demonstrate that ethylene induces EIN2 to associate with 3′ UTRs and target EBF1/2 mRNA to cytoplasmic processing-body (P-body) through interacting with multiple P-body factors, including EIN5 and PABs. Our study illustrates translational regulation as a key step in ethylene signaling and presents mRNA 3′ UTR functioning as a “signal transducer” to sense and relay cellular signaling in plants.},
author = {Li, Wenyang and Ma, Mengdi and Feng, Ying and Li, Hongjiang and Wang, Yichuan and Ma, Yutong and Li, Mingzhe and An, Fengying and Guo, Hongwei},
journal = {Cell},
number = {3},
pages = {670 -- 683},
publisher = {Cell Press},
title = {{EIN2-directed translational regulation of ethylene signaling in arabidopsis}},
doi = {10.1016/j.cell.2015.09.037},
volume = {163},
year = {2015},
}
@misc{5429,
abstract = {We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives.
There have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector.
We consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics.
Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).
Our main results are algorithms for the decision problem which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions.
Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.},
author = {Chatterjee, Krishnendu and Komarkova, Zuzana and Kretinsky, Jan},
issn = {2664-1690},
pages = {41},
publisher = {IST Austria},
title = {{Unifying two views on multiple mean-payoff objectives in Markov decision processes}},
doi = {10.15479/AT:IST-2015-318-v1-1},
year = {2015},
}
@misc{5430,
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 mul- tiplicative 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 · n | )) = O ( n · log( n · W )) , when the output is a b , as compared to the previously best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O ( n 2 · m ) time and the associated decision problem can be solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n · W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O ( n · log n ) time, improving the previous known O ( n 4 · 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},
issn = {2664-1690},
pages = {31},
publisher = {IST Austria},
title = {{Faster algorithms for quantitative verification in constant treewidth graphs}},
doi = {10.15479/AT:IST-2015-319-v1-1},
year = {2015},
}
@misc{5431,
abstract = {We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. We consider reachability objectives that given a target set of states require that some state in the target set is visited, and the dual safety objectives that given a target set require that only states in the target set are visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed.
Our main results are as follows: We show that in two-player zero-sum concurrent stochastic games (with reachability objective for one player and the complementary safety objective for the other player): (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. In general we study the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that if there is at least one player with reachability objective, then doubly-exponential patience is needed in general for epsilon-Nash equilibrium strategies, whereas in contrast if all players have safety objectives, then the optimal bound on patience for epsilon-Nash equilibrium strategies is only exponential.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Hansen, Kristoffer},
issn = {2664-1690},
pages = {25},
publisher = {IST Austria},
title = {{The patience of concurrent stochastic games with safety and reachability objectives}},
doi = {10.15479/AT:IST-2015-322-v1-1},
year = {2015},
}
@misc{5432,
abstract = {Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution.The replacement graph specifies who competes with whom for reproduction.
The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability.
Our main results are:
(1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure).
(2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time.
},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Nowak, Martin},
issn = {2664-1690},
pages = {29},
publisher = {IST Austria},
title = {{The complexity of evolutionary games on graphs}},
doi = {10.15479/AT:IST-2015-323-v1-1},
year = {2015},
}
@misc{5434,
abstract = {DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new method to solve the problem that extends methods for finite-horizon DEC- POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show our approach presents promising results.},
author = {Anonymous, 1 and Anonymous, 2},
issn = {2664-1690},
pages = {16},
publisher = {IST Austria},
title = {{Optimal cost indefinite-horizon reachability in goal DEC-POMDPs}},
year = {2015},
}
@misc{5435,
abstract = {We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives.
There have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector.
We consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).
Our main results are algorithms for the decision problem which are always polynomial in the size of the MDP.
We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.},
author = {Chatterjee, Krishnendu and Komarkova, Zuzana and Kretinsky, Jan},
issn = {2664-1690},
pages = {51},
publisher = {IST Austria},
title = {{Unifying two views on multiple mean-payoff objectives in Markov decision processes}},
doi = {10.15479/AT:IST-2015-318-v2-1},
year = {2015},
}
@misc{5436,
abstract = {Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time.
In nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.},
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan},
issn = {2664-1690},
pages = {29},
publisher = {IST Austria},
title = {{Nested weighted automata}},
doi = {10.15479/AT:IST-2015-170-v2-2},
year = {2015},
}
@misc{5437,
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 $\epsilon$ in time $O(n \cdot \log (n/\epsilon))$ 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 \cdot \log (|a\cdot b|))=O(n\cdot\log (n\cdot W))$, when the output is $\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \cdot \log (n\cdot W))$. Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in $O(n^2\cdot m)$ time and the associated decision problem can be solved in $O(n\cdot m)$ time, improving the previous known $O(n^3\cdot m\cdot \log (n\cdot W))$ and $O(n^2 \cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs we present an algorithm that requires $O(n\cdot \log n)$ time, improving the previous known $O(n^4 \cdot \log (n \cdot 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},
issn = {2664-1690},
pages = {27},
publisher = {IST Austria},
title = {{Faster algorithms for quantitative verification in constant treewidth graphs}},
doi = {10.15479/AT:IST-2015-330-v2-1},
year = {2015},
}
@misc{5438,
abstract = {The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses.
The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k. },
author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Ibsen-Jensen, Rasmus and Otop, Jan},
issn = {2664-1690},
pages = {15},
publisher = {IST Austria},
title = {{Edit distance for pushdown automata}},
doi = {10.15479/AT:IST-2015-334-v1-1},
year = {2015},
}
@misc{5439,
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},
issn = {2664-1690},
pages = {20},
publisher = {IST Austria},
title = {{The target discounted-sum problem}},
doi = {10.15479/AT:IST-2015-335-v1-1},
year = {2015},
}
@misc{5440,
abstract = {Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom for payoff in the context of evolution. The replacement graph specifies who competes with whom for reproduction. The vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. The fitness (or the reproductive rate) is a non-negative number, and depends on the payoff. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. Our main results are as follows: First, we consider a special case of the general problem, where the residents do not reproduce. We show that the qualitative question is NP-complete, and the quantitative approximation question is #P-complete, and the hardness results hold even in the special case where the interaction and the replacement graphs coincide. Second, we show that in general both the qualitative and the quantitative approximation questions are PSPACE-complete. The PSPACE-hardness result for quantitative approximation holds even when the fitness is always positive.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Nowak, Martin},
issn = {2664-1690},
pages = {18},
publisher = {IST Austria},
title = {{The complexity of evolutionary games on graphs}},
doi = {10.15479/AT:IST-2015-323-v2-2},
year = {2015},
}
@misc{5441,
abstract = {We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural problems that arise in program analysis. We consider that each component of the concurrent system is a graph with constant treewidth, a property satisfied by the controlflow graphs of most programs. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis. The study of multiple queries allows us to consider the tradeoff between the resource usage of the one-time preprocessing and for each individual query. The traditional approach constructs the product graph of all components and applies the best-known graph algorithm on the product. In this approach, even the answer to a single query requires the transitive closure (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time. Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time, each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results showing that the worst-case running time of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (i.e., improving the worst-case bound for the shortest path problem in general graphs). Preliminary experimental results show that our algorithms perform favorably on several benchmarks.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Goharshady, Amir and Pavlogiannis, Andreas},
issn = {2664-1690},
pages = {24},
publisher = {IST Austria},
title = {{Algorithms for algebraic path properties in concurrent systems of constant treewidth components}},
doi = {10.15479/AT:IST-2015-340-v1-1},
year = {2015},
}
@misc{5442,
abstract = {We study algorithmic questions for concurrent systems where the transitions are labeled from a complete, closed semiring, and path properties are algebraic with semiring operations. The algebraic path properties can model dataflow analysis problems, the shortest path problem, and many other natural properties that arise in program analysis.
We consider that each component of the concurrent system is a graph with constant treewidth, and it is known that the controlflow graphs of most programs have constant treewidth. We allow for multiple possible queries, which arise naturally in demand driven dataflow analysis problems (e.g., alias analysis). The study of multiple queries allows us to consider the tradeoff between the resource usage of the \emph{one-time} preprocessing and for \emph{each individual} query. The traditional approaches construct the product graph of all components and apply the best-known graph algorithm on the product. In the traditional approach, even the answer to a single query requires the transitive closure computation (i.e., the results of all possible queries), which provides no room for tradeoff between preprocessing and query time.
Our main contributions are algorithms that significantly improve the worst-case running time of the traditional approach, and provide various tradeoffs depending on the number of queries. For example, in a concurrent system of two components, the traditional approach requires hexic time in the worst case for answering one query as well as computing the transitive closure, whereas we show that with one-time preprocessing in almost cubic time,
each subsequent query can be answered in at most linear time, and even the transitive closure can be computed in almost quartic time. Furthermore, we establish conditional optimality results that show that the worst-case running times of our algorithms cannot be improved without achieving major breakthroughs in graph algorithms (such as improving
the worst-case bounds for the shortest path problem in general graphs whose current best-known bound has not been improved in five decades). Finally, we provide a prototype implementation of our algorithms which significantly outperforms the existing algorithmic methods on several benchmarks.},
author = {Anonymous, 1 and Anonymous, 2 and Anonymous, 3 and Anonymous, 4},
issn = {2664-1690},
pages = {22},
publisher = {IST Austria},
title = {{Algorithms for algebraic path properties in concurrent systems of constant treewidth components}},
year = {2015},
}
@misc{5443,
abstract = {POMDPs are standard models for probabilistic planning problems, where an agent interacts with an uncertain environment. We study the problem of almost-sure reachability, where given a set of target states, the question is to decide whether there is a policy to ensure that the target set is reached with probability 1 (almost-surely). While in general the problem is EXPTIME-complete, in many practical cases policies with a small amount of memory suffice. Moreover, the existing solution to the problem is explicit, which first requires to construct explicitly an exponential reduction to a belief-support MDP. In this work, we first study the existence of observation-stationary strategies, which is NP-complete, and then small-memory strategies. We present a symbolic algorithm by an efficient encoding to SAT and using a SAT solver for the problem. We report experimental results demonstrating the scalability of our symbolic (SAT-based) approach.},
author = {Chatterjee, Krishnendu and Chmelik, Martin and Davies, Jessica},
issn = {2664-1690},
pages = {23},
publisher = {IST Austria},
title = {{A symbolic SAT-based algorithm for almost-sure reachability with small strategies in POMDPs}},
doi = {10.15479/AT:IST-2015-325-v2-1},
year = {2015},
}
@misc{5444,
abstract = {A comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal.},
author = {Reiter, Johannes and Makohon-Moore, Alvin and Gerold, Jeffrey and Bozic, Ivana and Chatterjee, Krishnendu and Iacobuzio-Donahue, Christine and Vogelstein, Bert and Nowak, Martin},
issn = {2664-1690},
pages = {25},
publisher = {IST Austria},
title = {{Reconstructing robust phylogenies of metastatic cancers}},
doi = {10.15479/AT:IST-2015-399-v1-1},
year = {2015},
}
@misc{5549,
abstract = {This repository contains the experimental part of the CAV 2015 publication Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.
We extended the probabilistic model checker PRISM to represent strategies of Markov Decision Processes as Decision Trees.
The archive contains a java executable version of the extended tool (prism_dectree.jar) together with a few examples of the PRISM benchmark library.
To execute the program, please have a look at the README.txt, which provides instructions and further information on the archive.
The archive contains scripts that (if run often enough) reproduces the data presented in the publication.},
author = {Fellner, Andreas},
keywords = {Markov Decision Process, Decision Tree, Probabilistic Verification, Counterexample Explanation},
publisher = {IST Austria},
title = {{Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes}},
doi = {10.15479/AT:ISTA:28},
year = {2015},
}
@article{1383,
abstract = {In plants, vacuolar H+-ATPase (V-ATPase) activity acidifies both the trans-Golgi network/early endosome (TGN/EE) and the vacuole. This dual V-ATPase function has impeded our understanding of how the pH homeostasis within the plant TGN/EE controls exo- and endocytosis. Here, we show that the weak V-ATPase mutant deetiolated3 (det3) displayed a pH increase in the TGN/EE, but not in the vacuole, strongly impairing secretion and recycling of the brassinosteroid receptor and the cellulose synthase complexes to the plasma membrane, in contrast to mutants lacking tonoplast-localized V-ATPase activity only. The brassinosteroid insensitivity and the cellulose deficiency defects in det3 were tightly correlated with reduced Golgi and TGN/EE motility. Thus, our results provide strong evidence that acidification of the TGN/EE, but not of the vacuole, is indispensable for functional secretion and recycling in plants.},
author = {Yu, Luo and Scholl, Stefan and Doering, Anett and Yi, Zhang and Irani, Niloufer and Di Rubbo, Simone and Neumetzler, Lutz and Krishnamoorthy, Praveen and Van Houtte, Isabelle and Mylle, Evelien and Bischoff, Volker and Vernhettes, Samantha and Winne, Johan and Friml, Jirí and Stierhof, York and Schumacher, Karin and Persson, Staffan and Russinova, Eugenia},
journal = {Nature Plants},
number = {7},
publisher = {Nature Publishing Group},
title = {{V-ATPase activity in the TGN/EE is required for exocytosis and recycling in Arabidopsis}},
doi = {10.1038/nplants.2015.94},
volume = {1},
year = {2015},
}
@phdthesis{1399,
abstract = {This thesis is concerned with the computation and approximation of intrinsic volumes. Given a smooth body M and a certain digital approximation of it, we develop algorithms to approximate various intrinsic volumes of M using only measurements taken from its digital approximations. The crucial idea behind our novel algorithms is to link the recent theory of persistent homology to the theory of intrinsic volumes via the Crofton formula from integral geometry and, in particular, via Euler characteristic computations. Our main contributions are a multigrid convergent digital algorithm to compute the first intrinsic volume of a solid body in R^n as well as an appropriate integration pipeline to approximate integral-geometric integrals defined over the Grassmannian manifold.},
author = {Pausinger, Florian},
pages = {144},
publisher = {IST Austria},
title = {{On the approximation of intrinsic volumes}},
year = {2015},
}
@phdthesis{1400,
abstract = {Cancer results from an uncontrolled growth of abnormal cells. Sequentially accumulated genetic and epigenetic alterations decrease cell death and increase cell replication. We used mathematical models to quantify the effect of driver gene mutations. The recently developed targeted therapies can lead to dramatic regressions. However, in solid cancers, clinical responses are often short-lived because resistant cancer cells evolve. We estimated that approximately 50 different mutations can confer resistance to a typical targeted therapeutic agent. We find that resistant cells are likely to be present in expanded subclones before the start of the treatment. The dominant strategy to prevent the evolution of resistance is combination therapy. Our analytical results suggest that in most patients, dual therapy, but not monotherapy, can result in long-term disease control. However, long-term control can only occur if there are no possible mutations in the genome that can cause cross-resistance to both drugs. Furthermore, we showed that simultaneous therapy with two drugs is much more likely to result in long-term disease control than sequential therapy with the same drugs. To improve our understanding of the underlying subclonal evolution we reconstruct the evolutionary history of a patient's cancer from next-generation sequencing data of spatially-distinct DNA samples. Using a quantitative measure of genetic relatedness, we found that pancreatic cancers and their metastases demonstrated a higher level of relatedness than that expected for any two cells randomly taken from a normal tissue. This minimal amount of genetic divergence among advanced lesions indicates that genetic heterogeneity, when quantitatively defined, is not a fundamental feature of the natural history of untreated pancreatic cancers. Our newly developed, phylogenomic tool Treeomics finds evidence for seeding patterns of metastases and can directly be used to discover rules governing the evolution of solid malignancies to transform cancer into a more predictable disease.},
author = {Reiter, Johannes},
pages = {183},
publisher = {IST Austria},
title = {{The subclonal evolution of cancer}},
year = {2015},
}
@inproceedings{1424,
abstract = {We consider the problem of statistical computations with persistence diagrams, a summary representation of topological features in data. These diagrams encode persistent homology, a widely used invariant in topological data analysis. While several avenues towards a statistical treatment of the diagrams have been explored recently, we follow an alternative route that is motivated by the success of methods based on the embedding of probability measures into reproducing kernel Hilbert spaces. In fact, a positive definite kernel on persistence diagrams has recently been proposed, connecting persistent homology to popular kernel-based learning techniques such as support vector machines. However, important properties of that kernel enabling a principled use in the context of probability measure embeddings remain to be explored. Our contribution is to close this gap by proving universality of a variant of the original kernel, and to demonstrate its effective use in twosample hypothesis testing on synthetic as well as real-world data.},
author = {Kwitt, Roland and Huber, Stefan and Niethammer, Marc and Lin, Weili and Bauer, Ulrich},
location = {Montreal, Canada},
pages = {3070 -- 3078},
publisher = {Neural Information Processing Systems},
title = {{Statistical topological data analysis-A kernel perspective}},
volume = {28},
year = {2015},
}
@inproceedings{1425,
abstract = {In this work we aim at extending the theoretical foundations of lifelong learning. Previous work analyzing this scenario is based on the assumption that learning tasks are sampled i.i.d. from a task environment or limited to strongly constrained data distributions. Instead, we study two scenarios when lifelong learning is possible, even though the observed tasks do not form an i.i.d. sample: first, when they are sampled from the same environment, but possibly with dependencies, and second, when the task environment is allowed to change over time in a consistent way. In the first case we prove a PAC-Bayesian theorem that can be seen as a direct generalization of the analogous previous result for the i.i.d. case. For the second scenario we propose to learn an inductive bias in form of a transfer procedure. We present a generalization bound and show on a toy example how it can be used to identify a beneficial transfer algorithm.},
author = {Pentina, Anastasia and Lampert, Christoph},
location = {Montreal, Canada},
pages = {1540 -- 1548},
publisher = {Neural Information Processing Systems},
title = {{Lifelong learning with non-i.i.d. tasks}},
volume = {2015},
year = {2015},
}
@inproceedings{1430,
abstract = {Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse their runtime on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrence of new mutations is much longer than the time it takes for a new beneficial mutation to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a (1+1)-type process where the probability of accepting a new genotype (improvements or worsenings) depends on the change in fitness. We present an initial runtime analysis of SSWM, quantifying its performance for various parameters and investigating differences to the (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient.},
author = {Paixao, Tiago and Sudholt, Dirk and Heredia, Jorge and Trubenova, Barbora},
booktitle = {Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation},
location = {Madrid, Spain},
pages = {1455 -- 1462},
publisher = {ACM},
title = {{First steps towards a runtime comparison of natural and artificial evolution}},
doi = {10.1145/2739480.2754758},
year = {2015},
}
@inproceedings{1474,
abstract = {Cryptographic access control offers selective access to encrypted data via a combination of key management and functionality-rich cryptographic schemes, such as attribute-based encryption. Using this approach, publicly available meta-data may inadvertently leak information on the access policy that is enforced by cryptography, which renders cryptographic access control unusable in settings where this information is highly sensitive. We begin to address this problem by presenting rigorous definitions for policy privacy in cryptographic access control. For concreteness we set our results in the model of Role-Based Access Control (RBAC), where we identify and formalize several different flavors of privacy, however, our framework should serve as inspiration for other models of access control. Based on our insights we propose a new system which significantly improves on the privacy properties of state-of-the-art constructions. Our design is based on a novel type of privacy-preserving attribute-based encryption, which we introduce and show how to instantiate. We present our results in the context of a cryptographic RBAC system by Ferrara et al. (CSF'13), which uses cryptography to control read access to files, while write access is still delegated to trusted monitors. We give an extension of the construction that permits cryptographic control over write access. Our construction assumes that key management uses out-of-band channels between the policy enforcer and the users but eliminates completely the need for monitoring read/write access to the data.},
author = {Ferrara, Anna and Fuchsbauer, Georg and Liu, Bin and Warinschi, Bogdan},
location = {Verona, Italy},
pages = {46--60},
publisher = {IEEE},
title = {{Policy privacy in cryptographic access control}},
doi = {10.1109/CSF.2015.11},
year = {2015},
}
@inproceedings{1481,
abstract = {Simple board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in the development of mathematical and logical skills, but also in the 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. We present an approach that 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. The presence of such states for standard game variants like 4×4 Tic-Tac-Toe opens up new games to be played that have never been played as the default start state is heavily biased. },
author = {Ahmed, Umair and Chatterjee, Krishnendu and Gulwani, Sumit},
booktitle = {Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence},
location = {Austin, TX, USA},
pages = {745 -- 752},
publisher = {AAAI Press},
title = {{Automatic generation of alternative starting positions for simple traditional board games}},
volume = {2},
year = {2015},
}
@inproceedings{1483,
abstract = {Topological data analysis offers a rich source of valuable information to study vision problems. Yet, so far we lack a theoretically sound connection to popular kernel-based learning techniques, such as kernel SVMs or kernel PCA. In this work, we establish such a connection by designing a multi-scale kernel for persistence diagrams, a stable summary representation of topological features in data. We show that this kernel is positive definite and prove its stability with respect to the 1-Wasserstein distance. Experiments on two benchmark datasets for 3D shape classification/retrieval and texture recognition show considerable performance gains of the proposed method compared to an alternative approach that is based on the recently introduced persistence landscapes.},
author = {Reininghaus, Jan and Huber, Stefan and Bauer, Ulrich and Kwitt, Roland},
location = {Boston, MA, USA},
pages = {4741 -- 4748},
publisher = {IEEE},
title = {{A stable multi-scale kernel for topological machine learning}},
doi = {10.1109/CVPR.2015.7299106},
year = {2015},
}
@inproceedings{1495,
abstract = {Motivated by biological questions, we study configurations of equal-sized disks in the Euclidean plane that neither pack nor cover. Measuring the quality by the probability that a random point lies in exactly one disk, we show that the regular hexagonal grid gives the maximum among lattice configurations. },
author = {Edelsbrunner, Herbert and Iglesias Ham, Mabel and Kurlin, Vitaliy},
booktitle = {Proceedings of the 27th Canadian Conference on Computational Geometry},
location = {Ontario, Canada},
pages = {128--135},
publisher = {Queen's University},
title = {{Relaxed disk packing}},
volume = {2015-August},
year = {2015},
}
@article{1497,
abstract = {Detecting allelic biases from high-throughput sequencing data requires an approach that maximises sensitivity while minimizing false positives. Here, we present Allelome.PRO, an automated user-friendly bioinformatics pipeline, which uses high-throughput sequencing data from reciprocal crosses of two genetically distinct mouse strains to detect allele-specific expression and chromatin modifications. Allelome.PRO extends approaches used in previous studies that exclusively analyzed imprinted expression to give a complete picture of the ‘allelome’ by automatically categorising the allelic expression of all genes in a given cell type into imprinted, strain-biased, biallelic or non-informative. Allelome.PRO offers increased sensitivity to analyze lowly expressed transcripts, together with a robust false discovery rate empirically calculated from variation in the sequencing data. We used RNA-seq data from mouse embryonic fibroblasts from F1 reciprocal crosses to determine a biologically relevant allelic ratio cutoff, and define for the first time an entire allelome. Furthermore, we show that Allelome.PRO detects differential enrichment of H3K4me3 over promoters from ChIP-seq data validating the RNA-seq results. This approach can be easily extended to analyze histone marks of active enhancers, or transcription factor binding sites and therefore provides a powerful tool to identify candidate cis regulatory elements genome wide.},
author = {Andergassen, Daniel and Dotter, Christoph and Kulinski, Tomasz and Guenzl, Philipp and Bammer, Philipp and Barlow, Denise and Pauler, Florian and Hudson, Quanah},
journal = {Nucleic Acids Research},
number = {21},
publisher = {Oxford University Press},
title = {{Allelome.PRO, a pipeline to define allele-specific genomic features from high-throughput sequencing data}},
doi = {10.1093/nar/gkv727},
volume = {43},
year = {2015},
}
@inproceedings{1498,
abstract = {Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. Nonetheless there is surprisingly little language and verification support to build distributed systems based on fault-tolerant algorithms. In this paper, we present some of the challenges that a designer has to overcome to implement a fault-tolerant distributed system. Then we review different models that have been proposed to reason about distributed algorithms and sketch how such a model can form the basis for a domain-specific programming language. Adopting a high-level programming model can simplify the programmer's life and make the code amenable to automated verification, while still compiling to efficiently executable code. We conclude by summarizing the current status of an ongoing language design and implementation project that is based on this idea.},
author = {Dragoi, Cezara and Henzinger, Thomas A and Zufferey, Damien},
isbn = {978-3-939897-80-4 },
location = {Asilomar, CA, United States},
pages = {90 -- 102},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{The need for language support for fault-tolerant distributed systems}},
doi = {10.4230/LIPIcs.SNAPL.2015.90},
volume = {32},
year = {2015},
}
@inproceedings{1499,
abstract = {We consider weighted automata with both positive and negative integer weights on edges and
study the problem of synchronization using adaptive strategies that may only observe whether
the current weight-level is negative or nonnegative. We show that the synchronization problem is decidable in polynomial time for deterministic weighted automata.},
author = {Kretinsky, Jan and Larsen, Kim and Laursen, Simon and Srba, Jiří},
location = {Madrid, Spain},
pages = {142 -- 154},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Polynomial time decidability of weighted synchronization under partial observability}},
doi = {10.4230/LIPIcs.CONCUR.2015.142},
volume = {42},
year = {2015},
}
@article{1501,
abstract = {We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph algorithms with quadratic complexity to compute the simulation relation. We present an automated technique for assume-guarantee style reasoning for compositional analysis of two-player games by giving a counterexample guided abstraction-refinement approach to compute our new simulation relation. We show a tight link between two-player games and MDPs, and as a consequence the results for games are lifted to MDPs with qualitative properties. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. },
author = {Chatterjee, Krishnendu and Chmelik, Martin and Daca, Przemyslaw},
journal = {Formal Methods in System Design},
number = {2},
pages = {230 -- 264},
publisher = {Springer},
title = {{CEGAR for compositional analysis of qualitative properties in Markov decision processes}},
doi = {10.1007/s10703-015-0235-2},
volume = {47},
year = {2015},
}
@inproceedings{1502,
abstract = {We extend the theory of input-output conformance with operators for merge and quotient. The former is useful when testing against multiple requirements or views. The latter can be used to generate tests for patches of an already tested system. Both operators can combine systems with different action alphabets, which is usually the case when constructing complex systems and specifications from parts, for instance different views as well as newly defined functionality of a~previous version of the system.},
author = {Beneš, Nikola and Daca, Przemyslaw and Henzinger, Thomas A and Kretinsky, Jan and Nickovic, Dejan},
isbn = {978-1-4503-3471-6},
location = {Montreal, QC, Canada},
pages = {101 -- 110},
publisher = {ACM},
title = {{Complete composition operators for IOCO-testing theory}},
doi = {10.1145/2737166.2737175},
year = {2015},
}
@article{1505,
abstract = {This paper is aimed at deriving the universality of the largest eigenvalue of a class of high-dimensional real or complex sample covariance matrices of the form W N =Σ 1/2XX∗Σ 1/2 . Here, X = (xij )M,N is an M× N random matrix with independent entries xij , 1 ≤ i M,≤ 1 ≤ j ≤ N such that Exij = 0, E|xij |2 = 1/N . On dimensionality, we assume that M = M(N) and N/M → d ε (0, ∞) as N ∞→. For a class of general deterministic positive-definite M × M matrices Σ , under some additional assumptions on the distribution of xij 's, we show that the limiting behavior of the largest eigenvalue of W N is universal, via pursuing a Green function comparison strategy raised in [Probab. Theory Related Fields 154 (2012) 341-407, Adv. Math. 229 (2012) 1435-1515] by Erd″os, Yau and Yin for Wigner matrices and extended by Pillai and Yin [Ann. Appl. Probab. 24 (2014) 935-1001] to sample covariance matrices in the null case (&Epsi = I ). Consequently, in the standard complex case (Ex2 ij = 0), combing this universality property and the results known for Gaussian matrices obtained by El Karoui in [Ann. Probab. 35 (2007) 663-714] (nonsingular case) and Onatski in [Ann. Appl. Probab. 18 (2008) 470-490] (singular case), we show that after an appropriate normalization the largest eigenvalue of W N converges weakly to the type 2 Tracy-Widom distribution TW2 . Moreover, in the real case, we show that whenΣ is spiked with a fixed number of subcritical spikes, the type 1 Tracy-Widom limit TW1 holds for the normalized largest eigenvalue of W N , which extends a result of Féral and Péché in [J. Math. Phys. 50 (2009) 073302] to the scenario of nondiagonal Σ and more generally distributed X . In summary, we establish the Tracy-Widom type universality for the largest eigenvalue of generally distributed sample covariance matrices under quite light assumptions on &Sigma . Applications of these limiting results to statistical signal detection and structure recognition of separable covariance matrices are also discussed.},
author = {Bao, Zhigang and Pan, Guangming and Zhou, Wang},
journal = {Annals of Statistics},
number = {1},
pages = {382 -- 421},
publisher = {Institute of Mathematical Statistics},
title = {{Universality for the largest eigenvalue of sample covariance matrices with general population}},
doi = {10.1214/14-AOS1281},
volume = {43},
year = {2015},
}
@article{1506,
abstract = {Consider the square random matrix An = (aij)n,n, where {aij:= a(n)ij , i, j = 1, . . . , n} is a collection of independent real random variables with means zero and variances one. Under the additional moment condition supn max1≤i,j ≤n Ea4ij <∞, we prove Girko's logarithmic law of det An in the sense that as n→∞ log | detAn| ? (1/2) log(n-1)! d/→√(1/2) log n N(0, 1).},
author = {Bao, Zhigang and Pan, Guangming and Zhou, Wang},
journal = {Bernoulli},
number = {3},
pages = {1600 -- 1628},
publisher = {Bernoulli Society for Mathematical Statistics and Probability},
title = {{The logarithmic law of random determinant}},
doi = {10.3150/14-BEJ615},
volume = {21},
year = {2015},
}
@article{1508,
abstract = {We consider generalized Wigner ensembles and general β-ensembles with analytic potentials for any β ≥ 1. The recent universality results in particular assert that the local averages of consecutive eigenvalue gaps in the bulk of the spectrum are universal in the sense that they coincide with those of the corresponding Gaussian β-ensembles. In this article, we show that local averaging is not necessary for this result, i.e. we prove that the single gap distributions in the bulk are universal. In fact, with an additional step, our result can be extended to any C4(ℝ) potential.},
author = {Erdös, László and Yau, Horng},
journal = {Journal of the European Mathematical Society},
number = {8},
pages = {1927 -- 2036},
publisher = {European Mathematical Society},
title = {{Gap universality of generalized Wigner and β ensembles}},
doi = {10.4171/JEMS/548},
volume = {17},
year = {2015},
}
@article{1509,
abstract = {The Auxin Binding Protein1 (ABP1) has been identified based on its ability to bind auxin with high affinity and studied for a long time as a prime candidate for the extracellular auxin receptor responsible for mediating in particular the fast non-transcriptional auxin responses. However, the contradiction between the embryo-lethal phenotypes of the originally described Arabidopsis T-DNA insertional knock-out alleles (abp1-1 and abp1-1s) and the wild type-like phenotypes of other recently described loss-of-function alleles (abp1-c1 and abp1-TD1) questions the biological importance of ABP1 and relevance of the previous genetic studies. Here we show that there is no hidden copy of the ABP1 gene in the Arabidopsis genome but the embryo-lethal phenotypes of abp1-1 and abp1-1s alleles are very similar to the knock-out phenotypes of the neighboring gene, BELAYA SMERT (BSM). Furthermore, the allelic complementation test between bsm and abp1 alleles shows that the embryo-lethality in the abp1-1 and abp1-1s alleles is caused by the off-target disruption of the BSM locus by the T-DNA insertions. This clarifies the controversy of different phenotypes among published abp1 knock-out alleles and asks for reflections on the developmental role of ABP1.},
author = {Michalko, Jaroslav and Dravecka, Marta and Bollenbach, Tobias and Friml, Jirí},
journal = {F1000 Research },
publisher = {F1000 Research Ltd. },
title = {{Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene}},
doi = {10.12688/f1000research.7143.1},
volume = {4},
year = {2015},
}
@inproceedings{1510,
abstract = {The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r > 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K < 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status. },
author = {Franek, Peter and Krcál, Marek},
location = {Eindhoven, Netherlands},
pages = {842 -- 856},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{On computability and triviality of well groups}},
doi = {10.4230/LIPIcs.SOCG.2015.842},
volume = {34},
year = {2015},
}
@inproceedings{1511,
abstract = {The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2. Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem. In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.},
author = {Goaoc, Xavier and Mabillard, Isaac and Paták, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli},
location = {Eindhoven, Netherlands},
pages = {476 -- 490},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result}},
doi = {10.4230/LIPIcs.SOCG.2015.476},
volume = {34 },
year = {2015},
}
@inproceedings{1512,
abstract = {We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest.},
author = {Goaoc, Xavier and Paták, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli},
location = {Eindhoven, Netherlands},
pages = {507 -- 521},
publisher = {ACM},
title = {{Bounding Helly numbers via Betti numbers}},
doi = {10.4230/LIPIcs.SOCG.2015.507},
volume = {34},
year = {2015},
}
@article{1513,
abstract = {Insects of the order Hemiptera (true bugs) use a wide range of mechanisms of sex determination, including genetic sex determination, paternal genome elimination, and haplodiploidy. Genetic sex determination, the prevalent mode, is generally controlled by a pair of XY sex chromosomes or by an XX/X0 system, but different configurations that include additional sex chromosomes are also present. Although this diversity of sex determining systems has been extensively studied at the cytogenetic level, only the X chromosome of the model pea aphid Acyrthosiphon pisum has been analyzed at the genomic level, and little is known about X chromosome biology in the rest of the order.
In this study, we take advantage of published DNA- and RNA-seq data from three additional Hemiptera species to perform a comparative analysis of the gene content and expression of the X chromosome throughout this clade. We find that, despite showing evidence of dosage compensation, the X chromosomes of these species show female-biased expression, and a deficit of male-biased genes, in direct contrast to the pea aphid X. We further detect an excess of shared gene content between these very distant species, suggesting that despite the diversity of sex determining systems, the same chromosomal element is used as the X throughout a large portion of the order. },
author = {Pal, Arka and Vicoso, Beatriz},
journal = {Genome Biology and Evolution},
number = {12},
pages = {3259 -- 3268},
publisher = {Oxford University Press},
title = {{The X chromosome of hemipteran insects: Conservation, dosage compensation and sex-biased expression}},
doi = {10.1093/gbe/evv215},
volume = {7},
year = {2015},
}
@article{1517,
abstract = {We study the large deviation rate functional for the empirical distribution of independent Brownian particles with drift. In one dimension, it has been shown by Adams, Dirr, Peletier and Zimmer that this functional is asymptotically equivalent (in the sense of Γ-convergence) to the Jordan-Kinderlehrer-Otto functional arising in the Wasserstein gradient flow structure of the Fokker-Planck equation. In higher dimensions, part of this statement (the lower bound) has been recently proved by Duong, Laschos and Renger, but the upper bound remained open, since the proof of Duong et al relies on regularity properties of optimal transport maps that are restricted to one dimension. In this note we present a new proof of the upper bound, thereby generalising the result of Adams et al to arbitrary dimensions.
},
author = {Erbar, Matthias and Maas, Jan and Renger, Michiel},
journal = {Electronic Communications in Probability},
publisher = {Institute of Mathematical Statistics},
title = {{From large deviations to Wasserstein gradient flows in multiple dimensions}},
doi = {10.1214/ECP.v20-4315},
volume = {20},
year = {2015},
}
@article{1519,
abstract = {Evolutionary biologists have an array of powerful theoretical techniques that can accurately predict changes in the genetic composition of populations. Changes in gene frequencies and genetic associations between loci can be tracked as they respond to a wide variety of evolutionary forces. However, it is often less clear how to decompose these various forces into components that accurately reflect the underlying biology. Here, we present several issues that arise in the definition and interpretation of selection and selection coefficients, focusing on insights gained through the examination of selection coefficients in multilocus notation. Using this notation, we discuss how its flexibility-which allows different biological units to be identified as targets of selection-is reflected in the interpretation of the coefficients that the notation generates. In many situations, it can be difficult to agree on whether loci can be considered to be under "direct" versus "indirect" selection, or to quantify this selection. We present arguments for what the terms direct and indirect selection might best encompass, considering a range of issues, from viability and sexual selection to kin selection. We show how multilocus notation can discriminate between direct and indirect selection, and describe when it can do so.},
author = {Barton, Nicholas H and Servedio, Maria},
journal = {Evolution},
number = {5},
pages = {1101 -- 1112},
publisher = {Wiley},
title = {{The interpretation of selection coefficients}},
doi = {10.1111/evo.12641},
volume = {69},
year = {2015},
}