@inproceedings{14206, abstract = {Greedy optimization methods such as Matching Pursuit (MP) and Frank-Wolfe (FW) algorithms regained popularity in recent years due to their simplicity, effectiveness and theoretical guarantees. MP and FW address optimization over the linear span and the convex hull of a set of atoms, respectively. In this paper, we consider the intermediate case of optimization over the convex cone, parametrized as the conic hull of a generic atom set, leading to the first principled definitions of non-negative MP algorithms for which we give explicit convergence rates and demonstrate excellent empirical performance. In particular, we derive sublinear (O(1/t)) convergence on general smooth and convex objectives, and linear convergence (O(e−t)) on strongly convex objectives, in both cases for general sets of atoms. Furthermore, we establish a clear correspondence of our algorithms to known algorithms from the MP and FW literature. Our novel algorithms and analyses target general atom sets and general objective functions, and hence are directly applicable to a large variety of learning settings.}, author = {Locatello, Francesco and Tschannen, Michael and Rätsch, Gunnar and Jaggi, Martin}, booktitle = {Advances in Neural Information Processing Systems}, isbn = {9781510860964}, location = {Long Beach, CA, United States}, title = {{Greedy algorithms for cone constrained optimization with convergence guarantees}}, year = {2017}, } @article{14286, abstract = {The bacteriophage M13 has found frequent applications in nanobiotechnology due to its chemically and genetically tunable protein surface and its ability to self-assemble into colloidal membranes. Additionally, its single-stranded (ss) genome is commonly used as scaffold for DNA origami. Despite the manifold uses of M13, upstream production methods for phage and scaffold ssDNA are underexamined with respect to future industrial usage. Here, the high-cell-density phage production with Escherichia coli as host organism was studied in respect of medium composition, infection time, multiplicity of infection, and specific growth rate. The specific growth rate and the multiplicity of infection were identified as the crucial state variables that influence phage amplification rate on one hand and the concentration of produced ssDNA on the other hand. Using a growth rate of 0.15 h−1 and a multiplicity of infection of 0.05 pfu cfu−1 in the fed-batch production process, the concentration of pure isolated M13 ssDNA usable for scaffolded DNA origami could be enhanced by 54% to 590 mg L−1. Thus, our results help enabling M13 production for industrial uses in nanobiotechnology. Biotechnol. Bioeng. 2017;114: 777–784.}, author = {Kick, Benjamin and Hensler, Samantha and Praetorius, Florian M and Dietz, Hendrik and Weuster-Botz, Dirk}, issn = {0006-3592}, journal = {Biotechnology and Bioengineering}, keywords = {Applied Microbiology and Biotechnology, Bioengineering, Biotechnology}, number = {4}, pages = {777--784}, publisher = {Wiley}, title = {{Specific growth rate and multiplicity of infection affect high-cell-density fermentation with bacteriophage M13 for ssDNA production}}, doi = {10.1002/bit.26200}, volume = {114}, year = {2017}, } @article{14287, abstract = {We describe an approach to bottom-up fabrication that allows integration of the functional diversity of proteins into designed three-dimensional structural frameworks. A set of custom staple proteins based on transcription activator–like effector proteins folds a double-stranded DNA template into a user-defined shape. Each staple protein is designed to recognize and closely link two distinct double-helical DNA sequences at separate positions on the template. We present design rules for constructing megadalton-scale DNA-protein hybrid shapes; introduce various structural motifs, such as custom curvature, corners, and vertices; and describe principles for creating multilayer DNA-protein objects with enhanced rigidity. We demonstrate self-assembly of our hybrid nanostructures in one-pot mixtures that include the genetic information for the designed proteins, the template DNA, RNA polymerase, ribosomes, and cofactors for transcription and translation.}, author = {Praetorius, Florian M and Dietz, Hendrik}, issn = {1095-9203}, journal = {Science}, number = {6331}, publisher = {American Association for the Advancement of Science}, title = {{Self-assembly of genetically encoded DNA-protein hybrid nanoscale shapes}}, doi = {10.1126/science.aam5488}, volume = {355}, year = {2017}, } @article{14290, abstract = {DNA nanotechnology, in particular DNA origami, enables the bottom-up self-assembly of micrometre-scale, three-dimensional structures with nanometre-precise features1,2,3,4,5,6,7,8,9,10,11,12. These structures are customizable in that they can be site-specifically functionalized13 or constructed to exhibit machine-like14,15 or logic-gating behaviour16. Their use has been limited to applications that require only small amounts of material (of the order of micrograms), owing to the limitations of current production methods. But many proposed applications, for example as therapeutic agents or in complex materials3,16,17,18,19,20,21,22, could be realized if more material could be used. In DNA origami, a nanostructure is assembled from a very long single-stranded scaffold molecule held in place by many short single-stranded staple oligonucleotides. Only the bacteriophage-derived scaffold molecules are amenable to scalable and efficient mass production23; the shorter staple strands are obtained through costly solid-phase synthesis24 or enzymatic processes25. Here we show that single strands of DNA of virtually arbitrary length and with virtually arbitrary sequences can be produced in a scalable and cost-efficient manner by using bacteriophages to generate single-stranded precursor DNA that contains target strand sequences interleaved with self-excising ‘cassettes’, with each cassette comprising two Zn2+-dependent DNA-cleaving DNA enzymes. We produce all of the necessary single strands of DNA for several DNA origami using shaker-flask cultures, and demonstrate end-to-end production of macroscopic amounts of a DNA origami nanorod in a litre-scale stirred-tank bioreactor. Our method is compatible with existing DNA origami design frameworks and retains the modularity and addressability of DNA origami objects that are necessary for implementing custom modifications using functional groups. With all of the production and purification steps amenable to scaling, we expect that our method will expand the scope of DNA nanotechnology in many areas of science and technology.}, author = {Praetorius, Florian M and Kick, Benjamin and Behler, Karl L. and Honemann, Maximilian N. and Weuster-Botz, Dirk and Dietz, Hendrik}, issn = {1476-4687}, journal = {Nature}, number = {7683}, pages = {84--87}, publisher = {Springer Nature}, title = {{Biotechnological mass production of DNA origami}}, doi = {10.1038/nature24650}, volume = {552}, year = {2017}, } @article{14308, abstract = {Here we describe an approach to bottom-up fabrication with nanometer-precision that allows integrating the functional diversity of proteins in designed three-dimensional structural frameworks. We reimagined the successful DNA origami design principle using a set of custom staple proteins to fold a double-stranded DNA template into a user-defined shape. Each staple protein recognizes two distinct double-helical DNA sequences and can carry additional functionalities. The staple proteins we present here are based on the transcription activator-like (TAL) effector proteins. Due to their repetitive structure these proteins offer a unique programmability that enables us to construct numerous staple proteins targeting any desired DNA sequence. Our approach is general, meaning that many different objects may be created using the same set of rules, and it is modular, because components can be modified or exchanged individually. We present rules for constructing megadalton-scale DNA-protein hybrid nanostructures; introduce important structural motifs, such as curvature, corners, and vertices; describe principles for creating multi-layer DNA-protein objects with enhanced rigidity; and demonstrate the possibility to combine our DNA-protein hybrid origami with conventional DNA nanotechnology. Since all components can be encoded genetically, our structures should be amenable to biotechnological mass-production. Moreover, since the target objects can self-assemble at room temperature in near-physiological buffer, our hybrid origami may also provide an attractive method to realize positioning and scaffolding tasks in vivo. We expect our method to find application both in scaffolding protein functionalities and in manipulating the spatial arrangement of genomic DNA.}, author = {Praetorius, Florian M and Dietz, Hendrik}, issn = {0006-3495}, journal = {Biophysical Journal}, keywords = {Biophysics}, number = {3}, publisher = {Elsevier}, title = {{Genetically encoded DNA-protein hybrid origami}}, doi = {10.1016/j.bpj.2016.11.171}, volume = {112}, year = {2017}, } @article{14309, abstract = {Establishing precise control over the shape and the interactions of the microscopic building blocks is essential for design of macroscopic soft materials with novel structural, optical and mechanical properties. Here, we demonstrate robust assembly of DNA origami filaments into cholesteric liquid crystals, one-dimensional supramolecular twisted ribbons and two-dimensional colloidal membranes. The exquisite control afforded by the DNA origami technology establishes a quantitative relationship between the microscopic filament structure and the macroscopic cholesteric pitch. Furthermore, it also enables robust assembly of one-dimensional twisted ribbons, which behave as effective supramolecular polymers whose structure and elastic properties can be precisely tuned by controlling the geometry of the elemental building blocks. Our results demonstrate the potential synergy between DNA origami technology and colloidal science, in which the former allows for rapid and robust synthesis of complex particles, and the latter can be used to assemble such particles into bulk materials.}, author = {Siavashpouri, M and Wachauf, CH and Zakhary, MJ and Praetorius, Florian M and Dietz, H and Dogic, Z}, issn = {1476-4660}, journal = {Nature Materials}, number = {8}, pages = {849--856}, publisher = {Springer Nature}, title = {{Molecular engineering of chiral colloidal liquid crystals using DNA origami}}, doi = {10.1038/nmat4909}, volume = {16}, year = {2017}, } @inproceedings{14310, author = {Siavashpouri, Mahsa and Wachauf, Christian and Zakhary, Mark and Praetorius, Florian M and Dietz, Hendrik and Dogic, Zvonimir}, booktitle = {APS March Meeting 2017}, publisher = {APS}, title = {{Molecular engineering of colloidal liquid crystals using DNA origami}}, year = {2017}, } @article{1433, abstract = {Phat is an open-source C. ++ library for the computation of persistent homology by matrix reduction, targeted towards developers of software for topological data analysis. We aim for a simple generic design that decouples algorithms from data structures without sacrificing efficiency or user-friendliness. We provide numerous different reduction strategies as well as data types to store and manipulate the boundary matrix. We compare the different combinations through extensive experimental evaluation and identify optimization techniques that work well in practical situations. We also compare our software with various other publicly available libraries for persistent homology.}, author = {Bauer, Ulrich and Kerber, Michael and Reininghaus, Jan and Wagner, Hubert}, issn = { 07477171}, journal = {Journal of Symbolic Computation}, pages = {76 -- 90}, publisher = {Academic Press}, title = {{Phat - Persistent homology algorithms toolbox}}, doi = {10.1016/j.jsc.2016.03.008}, volume = {78}, year = {2017}, } @article{540, abstract = {RNA-dependent RNA polymerases (RdRps) play a key role in the life cycle of RNA viruses and impact their immunobiology. The arenavirus lymphocytic choriomeningitis virus (LCMV) strain Clone 13 provides a benchmark model for studying chronic infection. A major genetic determinant for its ability to persist maps to a single amino acid exchange in the viral L protein, which exhibits RdRp activity, yet its functional consequences remain elusive. To unravel the L protein interactions with the host proteome, we engineered infectious L protein-tagged LCMV virions by reverse genetics. A subsequent mass-spectrometric analysis of L protein pulldowns from infected human cells revealed a comprehensive network of interacting host proteins. The obtained LCMV L protein interactome was bioinformatically integrated with known host protein interactors of RdRps from other RNA viruses, emphasizing interconnected modules of human proteins. Functional characterization of selected interactors highlighted proviral (DDX3X) as well as antiviral (NKRF, TRIM21) host factors. To corroborate these findings, we infected Trim21-/-mice with LCMV and found impaired virus control in chronic infection. These results provide insights into the complex interactions of the arenavirus LCMV and other viral RdRps with the host proteome and contribute to a better molecular understanding of how chronic viruses interact with their host.}, author = {Khamina, Kseniya and Lercher, Alexander and Caldera, Michael and Schliehe, Christopher and Vilagos, Bojan and Sahin, Mehmet and Kosack, Lindsay and Bhattacharya, Anannya and Májek, Peter and Stukalov, Alexey and Sacco, Roberto and James, Leo and Pinschewer, Daniel and Bennett, Keiryn and Menche, Jörg and Bergthaler, Andreas}, issn = {15537366}, journal = {PLoS Pathogens}, number = {12}, publisher = {Public Library of Science}, title = {{Characterization of host proteins interacting with the lymphocytic choriomeningitis virus L protein}}, doi = {10.1371/journal.ppat.1006758}, volume = {13}, year = {2017}, } @article{541, abstract = {While we have good understanding of bacterial metabolism at the population level, we know little about the metabolic behavior of individual cells: do single cells in clonal populations sometimes specialize on different metabolic pathways? Such metabolic specialization could be driven by stochastic gene expression and could provide individual cells with growth benefits of specialization. We measured the degree of phenotypic specialization in two parallel metabolic pathways, the assimilation of glucose and arabinose. We grew Escherichia coli in chemostats, and used isotope-labeled sugars in combination with nanometer-scale secondary ion mass spectrometry and mathematical modeling to quantify sugar assimilation at the single-cell level. We found large variation in metabolic activities between single cells, both in absolute assimilation and in the degree to which individual cells specialize in the assimilation of different sugars. Analysis of transcriptional reporters indicated that this variation was at least partially based on cell-to-cell variation in gene expression. Metabolic differences between cells in clonal populations could potentially reduce metabolic incompatibilities between different pathways, and increase the rate at which parallel reactions can be performed.}, author = {Nikolic, Nela and Schreiber, Frank and Dal Co, Alma and Kiviet, Daniel and Bergmiller, Tobias and Littmann, Sten and Kuypers, Marcel and Ackermann, Martin}, issn = {15537390}, journal = {PLoS Genetics}, number = {12}, publisher = {Public Library of Science}, title = {{Cell-to-cell variation and specialization in sugar metabolism in clonal bacterial populations}}, doi = {10.1371/journal.pgen.1007122}, volume = {13}, year = {2017}, } @inbook{545, abstract = {Development of vascular tissue is a remarkable example of intercellular communication and coordinated development involving hormonal signaling and tissue polarity. Thus far, studies on vascular patterning and regeneration have been conducted mainly in trees—woody plants—with a well-developed layer of vascular cambium and secondary tissues. Trees are difficult to use as genetic models, i.e., due to long generation time, unstable environmental conditions, and lack of available mutants and transgenic lines. Therefore, the use of the main genetic model plant Arabidopsis thaliana (L.) Heynh., with a wealth of available marker and transgenic lines, provides a unique opportunity to address molecular mechanism of vascular tissue formation and regeneration. With specific treatments, the tiny weed Arabidopsis can serve as a model to understand the growth of mighty trees and interconnect a tree physiology with molecular genetics and cell biology of Arabidopsis.}, author = {Mazur, Ewa and Friml, Jirí}, booktitle = {Plant Engineering}, editor = {Jurić, Snježana}, pages = {113 -- 140}, publisher = {InTech}, title = {{Vascular tissue development and regeneration in the model plant arabidopsis}}, doi = {10.5772/intechopen.69712}, year = {2017}, } @techreport{5450, abstract = {In this report the implementation of the institutional data repository IST DataRep at IST Austria will be covered: Starting with the research phase when requirements for a repository were established, the procedure of choosing a repository-software and its customization based on the results of user-testings will be discussed. Followed by reflections on the marketing strategies in regard of impact, and at the end sharing some experiences of one year operating IST DataRep.}, author = {Barbara Petritsch}, publisher = {IST Austria}, title = {{Implementing the institutional data repository IST DataRep}}, year = {2017}, } @misc{5455, abstract = {A fundamental algorithmic problem at the heart of static analysis is Dyck reachability. The input is a graphwhere the edges are labeled with different types of opening and closing parentheses, and the reachabilityinformation is computed via paths whose parentheses are properly matched. We present new results for Dyckreachability problems with applications to alias analysis and data-dependence analysis. Our main contributions,that include improved upper bounds as well as lower bounds that establish optimality guarantees, are asfollows:First, we consider Dyck reachability on bidirected graphs, which is the standard way of performing field-sensitive points-to analysis. Given a bidirected graph withnnodes andmedges, we present: (i) an algorithmwith worst-case running timeO(m+n·α(n)), whereα(n)is the inverse Ackermann function, improving thepreviously knownO(n2)time bound; (ii) a matching lower bound that shows that our algorithm is optimalwrt to worst-case complexity; and (iii) an optimal average-case upper bound ofO(m)time, improving thepreviously knownO(m·logn)bound.Second, we consider the problem of context-sensitive data-dependence analysis, where the task is to obtainanalysis summaries of library code in the presence of callbacks. Our algorithm preprocesses libraries in almostlinear time, after which the contribution of the library in the complexity of the client analysis is only linear,and only wrt the number of call sites.Third, we prove that combinatorial algorithms for Dyck reachability on general graphs with truly sub-cubic bounds cannot be obtained without obtaining sub-cubic combinatorial algorithms for Boolean MatrixMultiplication, which is a long-standing open problem. Thus we establish that the existing combinatorialalgorithms for Dyck reachability are (conditionally) optimal for general graphs. We also show that the samehardness holds for graphs of constant treewidth.Finally, we provide a prototype implementation of our algorithms for both alias analysis and data-dependenceanalysis. Our experimental evaluation demonstrates that the new algorithms significantly outperform allexisting methods on the two problems, over real-world benchmarks.}, author = {Chatterjee, Krishnendu and Choudhary, Bhavya and Pavlogiannis, Andreas}, issn = {2664-1690}, pages = {37}, publisher = {IST Austria}, title = {{Optimal Dyck reachability for data-dependence and alias analysis}}, doi = {10.15479/AT:IST-2017-870-v1-1}, year = {2017}, } @misc{5456, abstract = {We present a new dynamic partial-order reduction method for stateless model checking of concurrent programs. A common approach for exploring program behaviors relies on enumerating the traces of the program, without storing the visited states (aka stateless exploration). As the number of distinct traces grows exponentially, dynamic partial-order reduction (DPOR) techniques have been successfully used to partition the space of traces into equivalence classes (Mazurkiewicz partitioning), with the goal of exploring only few representative traces from each class. We introduce a new equivalence on traces under sequential consistency semantics, which we call the observation equivalence. Two traces are observationally equivalent if every read event observes the same write event in both traces. While the traditional Mazurkiewicz equivalence is control-centric, our new definition is data-centric. We show that our observation equivalence is coarser than the Mazurkiewicz equivalence, and in many cases even exponentially coarser. We devise a DPOR exploration of the trace space, called data-centric DPOR, based on the observation equivalence. 1. For acyclic architectures, our algorithm is guaranteed to explore exactly one representative trace from each observation class, while spending polynomial time per class. Hence, our algorithm is optimal wrt the observation equivalence, and in several cases explores exponentially fewer traces than any enumerative method based on the Mazurkiewicz equivalence. 2. For cyclic architectures, we consider an equivalence between traces which is finer than the observation equivalence; but coarser than the Mazurkiewicz equivalence, and in some cases is exponentially coarser. Our data-centric DPOR algorithm remains optimal under this trace equivalence. Finally, we perform a basic experimental comparison between the existing Mazurkiewicz-based DPOR and our data-centric DPOR on a set of academic benchmarks. Our results show a significant reduction in both running time and the number of explored equivalence classes.}, author = {Chalupa, Marek and Chatterjee, Krishnendu and Pavlogiannis, Andreas and Sinha, Nishant and Vaidya, Kapil}, issn = {2664-1690}, pages = {36}, publisher = {IST Austria}, title = {{Data-centric dynamic partial order reduction}}, doi = {10.15479/AT:IST-2017-872-v1-1}, year = {2017}, } @article{548, abstract = {In this work maximum entropy distributions in the space of steady states of metabolic networks are considered upon constraining the first and second moments of the growth rate. Coexistence of fast and slow phenotypes, with bimodal flux distributions, emerges upon considering control on the average growth (optimization) and its fluctuations (heterogeneity). This is applied to the carbon catabolic core of Escherichia coli where it quantifies the metabolic activity of slow growing phenotypes and it provides a quantitative map with metabolic fluxes, opening the possibility to detect coexistence from flux data. A preliminary analysis on data for E. coli cultures in standard conditions shows degeneracy for the inferred parameters that extend in the coexistence region.}, author = {De Martino, Daniele}, issn = {2470-0045}, journal = {Physical Review E}, number = {6}, publisher = {American Physical Society}, title = {{Maximum entropy modeling of metabolic networks by constraining growth-rate moments predicts coexistence of phenotypes}}, doi = {10.1103/PhysRevE.96.060401}, volume = {96}, year = {2017}, } @inproceedings{549, abstract = {Model checking is usually based on a comprehensive traversal of the state space. Causality-based model checking is a radically different approach that instead analyzes the cause-effect relationships in a program. We give an overview on a new class of model checking algorithms that capture the causal relationships in a special data structure called concurrent traces. Concurrent traces identify key events in an execution history and link them through their cause-effect relationships. The model checker builds a tableau of concurrent traces, where the case splits represent different causal explanations of a hypothetical error. Causality-based model checking has been implemented in the ARCTOR tool, and applied to previously intractable multi-threaded benchmarks.}, author = {Finkbeiner, Bernd and Kupriyanov, Andrey}, booktitle = {Electronic Proceedings in Theoretical Computer Science}, issn = {2075-2180}, location = {Uppsala, Sweden}, pages = {31 -- 38}, publisher = {Open Publishing Association}, title = {{Causality-based model checking}}, doi = {10.4204/EPTCS.259.3}, volume = {259}, year = {2017}, } @article{550, abstract = {For large random matrices X with independent, centered entries but not necessarily identical variances, the eigenvalue density of XX* is well-approximated by a deterministic measure on ℝ. We show that the density of this measure has only square and cubic-root singularities away from zero. We also extend the bulk local law in [5] to the vicinity of these singularities.}, author = {Alt, Johannes}, issn = {1083589X}, journal = {Electronic Communications in Probability}, publisher = {Institute of Mathematical Statistics}, title = {{Singularities of the density of states of random Gram matrices}}, doi = {10.1214/17-ECP97}, volume = {22}, year = {2017}, } @inproceedings{551, abstract = {Evolutionary graph theory studies the evolutionary dynamics in a population structure given as a connected graph. Each node of the graph represents an individual of the population, and edges determine how offspring are placed. We consider the classical birth-death Moran process where there are two types of individuals, namely, the residents with fitness 1 and mutants with fitness r. The fitness indicates the reproductive strength. The evolutionary dynamics happens as follows: in the initial step, in a population of all resident individuals a mutant is introduced, and then at each step, an individual is chosen proportional to the fitness of its type to reproduce, and the offspring replaces a neighbor uniformly at random. The process stops when all individuals are either residents or mutants. The probability that all individuals in the end are mutants is called the fixation probability, which is a key factor in the rate of evolution. We consider the problem of approximating the fixation probability. The class of algorithms that is extremely relevant for approximation of the fixation probabilities is the Monte-Carlo simulation of the process. Previous results present a polynomial-time Monte-Carlo algorithm for undirected graphs when r is given in unary. First, we present a simple modification: instead of simulating each step, we discard ineffective steps, where no node changes type (i.e., either residents replace residents, or mutants replace mutants). Using the above simple modification and our result that the number of effective steps is concentrated around the expected number of effective steps, we present faster polynomial-time Monte-Carlo algorithms for undirected graphs. Our algorithms are always at least a factor O(n2/ log n) faster as compared to the previous algorithms, where n is the number of nodes, and is polynomial even if r is given in binary. We also present lower bounds showing that the upper bound on the expected number of effective steps we present is asymptotically tight for undirected graphs. }, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Nowak, Martin}, booktitle = {Leibniz International Proceedings in Informatics}, isbn = {978-395977046-0}, location = {Aalborg, Denmark}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Faster Monte Carlo algorithms for fixation probability of the Moran process on undirected graphs}}, doi = {10.4230/LIPIcs.MFCS.2017.61}, volume = {83}, year = {2017}, } @inproceedings{552, abstract = {Graph games provide the foundation for modeling and synthesis of reactive processes. Such games are played over graphs where the vertices are controlled by two adversarial players. We consider graph games where the objective of the first player is the conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a meanpayoff condition). There are two variants of the problem, namely, the threshold problem where the quantitative goal is to ensure that the mean-payoff value is above a threshold, and the value problem where the quantitative goal is to ensure the optimal mean-payoff value; in both cases ensuring the qualitative parity objective. The previous best-known algorithms for game graphs with n vertices, m edges, parity objectives with d priorities, and maximal absolute reward value W for mean-payoff objectives, are as follows: O(nd+1 . m . w) for the threshold problem, and O(nd+2 · m · W) for the value problem. Our main contributions are faster algorithms, and the running times of our algorithms are as follows: O(nd-1 · m ·W) for the threshold problem, and O(nd · m · W · log(n · W)) for the value problem. For mean-payoff parity objectives with two priorities, our algorithms match the best-known bounds of the algorithms for mean-payoff games (without conjunction with parity objectives). Our results are relevant in synthesis of reactive systems with both functional requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective).}, author = {Chatterjee, Krishnendu and Henzinger, Monika H and Svozil, Alexander}, booktitle = {Leibniz International Proceedings in Informatics}, isbn = {978-395977046-0}, location = {Aalborg, Denmark}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Faster algorithms for mean-payoff parity games}}, doi = {10.4230/LIPIcs.MFCS.2017.39}, volume = {83}, year = {2017}, } @inproceedings{553, abstract = {We consider two player, zero-sum, finite-state concurrent reachability games, played 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. Player 1 wins iff a designated goal state is eventually 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: (i) the optimal bound on the patience of optimal and -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. }, author = {Chatterjee, Krishnendu and Hansen, Kristofer and Ibsen-Jensen, Rasmus}, booktitle = {Leibniz International Proceedings in Informatics}, isbn = {978-395977046-0}, location = {Aalborg, Denmark}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Strategy complexity of concurrent safety games}}, doi = {10.4230/LIPIcs.MFCS.2017.55}, volume = {83}, year = {2017}, }