@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}, } @article{10417, 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.}, author = {Chalupa, Marek and Chatterjee, Krishnendu and Pavlogiannis, Andreas and Sinha, Nishant and Vaidya, Kapil}, issn = {2475-1421}, journal = {Proceedings of the ACM on Programming Languages}, location = {Los Angeles, CA, United States}, number = {POPL}, publisher = {Association for Computing Machinery}, title = {{Data-centric dynamic partial order reduction}}, doi = {10.1145/3158119}, volume = {2}, 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}, } @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}, } @article{560, abstract = {In a recent article (Jentzen et al. 2016 Commun. Math. Sci. 14, 1477–1500 (doi:10.4310/CMS.2016.v14. n6.a1)), it has been established that, for every arbitrarily slow convergence speed and every natural number d ? {4, 5, . . .}, there exist d-dimensional stochastic differential equations with infinitely often differentiable and globally bounded coefficients such that no approximation method based on finitely many observations of the driving Brownian motion can converge in absolute mean to the solution faster than the given speed of convergence. In this paper, we strengthen the above result by proving that this slow convergence phenomenon also arises in two (d = 2) and three (d = 3) space dimensions.}, author = {Gerencser, Mate and Jentzen, Arnulf and Salimova, Diyora}, issn = {13645021}, journal = {Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences}, number = {2207}, publisher = {Royal Society of London}, title = {{On stochastic differential equations with arbitrarily slow convergence rates for strong approximation in two space dimensions}}, doi = {10.1098/rspa.2017.0104}, volume = {473}, year = {2017}, } @book{567, abstract = {This book is a concise and self-contained introduction of recent techniques to prove local spectral universality for large random matrices. Random matrix theory is a fast expanding research area, and this book mainly focuses on the methods that the authors participated in developing over the past few years. Many other interesting topics are not included, and neither are several new developments within the framework of these methods. The authors have chosen instead to present key concepts that they believe are the core of these methods and should be relevant for future applications. They keep technicalities to a minimum to make the book accessible to graduate students. With this in mind, they include in this book the basic notions and tools for high-dimensional analysis, such as large deviation, entropy, Dirichlet form, and the logarithmic Sobolev inequality. }, author = {Erdös, László and Yau, Horng}, isbn = {9-781-4704-3648-3}, pages = {226}, publisher = {American Mathematical Society}, title = {{A Dynamical Approach to Random Matrix Theory}}, doi = {10.1090/cln/028}, volume = {28}, year = {2017}, } @article{568, abstract = {We study robust properties of zero sets of continuous maps f: X → ℝn. Formally, we analyze the family Z< r(f) := (g-1(0): ||g - f|| < r) of all zero sets of all continuous maps g closer to f than r in the max-norm. All of these sets are outside A := (x: |f(x)| ≥ r) and we claim that Z< r(f) is fully determined by A and an element of a certain cohomotopy group which (by a recent result) is computable whenever the dimension of X is at most 2n - 3. By considering all r > 0 simultaneously, the pointed cohomotopy groups form a persistence module-a structure leading to persistence diagrams as in the case of persistent homology or well groups. Eventually, we get a descriptor of persistent robust properties of zero sets that has better descriptive power (Theorem A) and better computability status (Theorem B) than the established well diagrams. Moreover, if we endow every point of each zero set with gradients of the perturbation, the robust description of the zero sets by elements of cohomotopy groups is in some sense the best possible (Theorem C).}, author = {Franek, Peter and Krcál, Marek}, issn = {15320073}, journal = {Homology, Homotopy and Applications}, number = {2}, pages = {313 -- 342}, publisher = {International Press}, title = {{Persistence of zero sets}}, doi = {10.4310/HHA.2017.v19.n2.a16}, volume = {19}, year = {2017}, } @article{570, abstract = {Most phenotypes are determined by molecular systems composed of specifically interacting molecules. However, unlike for individual components, little is known about the distributions of mutational effects of molecular systems as a whole. We ask how the distribution of mutational effects of a transcriptional regulatory system differs from the distributions of its components, by first independently, and then simultaneously, mutating a transcription factor and the associated promoter it represses. We find that the system distribution exhibits increased phenotypic variation compared to individual component distributions - an effect arising from intermolecular epistasis between the transcription factor and its DNA-binding site. In large part, this epistasis can be qualitatively attributed to the structure of the transcriptional regulatory system and could therefore be a common feature in prokaryotes. Counter-intuitively, intermolecular epistasis can alleviate the constraints of individual components, thereby increasing phenotypic variation that selection could act on and facilitating adaptive evolution. }, author = {Lagator, Mato and Sarikas, Srdjan and Acar, Hande and Bollback, Jonathan P and Guet, Calin C}, issn = {2050084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{Regulatory network structure determines patterns of intermolecular epistasis}}, doi = {10.7554/eLife.28921}, volume = {6}, year = {2017}, } @article{569, abstract = {The actomyosin ring generates force to ingress the cytokinetic cleavage furrow in animal cells, yet its filament organization and the mechanism of contractility is not well understood. We quantified actin filament order in human cells using fluorescence polarization microscopy and found that cleavage furrow ingression initiates by contraction of an equatorial actin network with randomly oriented filaments. The network subsequently gradually reoriented actin filaments along the cell equator. This strictly depended on myosin II activity, suggesting local network reorganization by mechanical forces. Cortical laser microsurgery revealed that during cytokinesis progression, mechanical tension increased substantially along the direction of the cell equator, while the network contracted laterally along the pole-to-pole axis without a detectable increase in tension. Our data suggest that an asymmetric increase in cortical tension promotes filament reorientation along the cytokinetic cleavage furrow, which might have implications for diverse other biological processes involving actomyosin rings.}, author = {Spira, Felix and Cuylen Haering, Sara and Mehta, Shalin and Samwer, Matthias and Reversat, Anne and Verma, Amitabh and Oldenbourg, Rudolf and Sixt, Michael K and Gerlich, Daniel}, issn = {2050084X}, journal = {eLife}, publisher = {eLife Sciences Publications}, title = {{Cytokinesis in vertebrate cells initiates by contraction of an equatorial actomyosin network composed of randomly oriented filaments}}, doi = {10.7554/eLife.30867}, volume = {6}, year = {2017}, } @article{571, abstract = {Blood platelets are critical for hemostasis and thrombosis and play diverse roles during immune responses. Despite these versatile tasks in mammalian biology, their skills on a cellular level are deemed limited, mainly consisting in rolling, adhesion, and aggregate formation. Here, we identify an unappreciated asset of platelets and show that adherent platelets use adhesion receptors to mechanically probe the adhesive substrate in their local microenvironment. When actomyosin-dependent traction forces overcome substrate resistance, platelets migrate and pile up the adhesive substrate together with any bound particulate material. They use this ability to act as cellular scavengers, scanning the vascular surface for potential invaders and collecting deposited bacteria. Microbe collection by migrating platelets boosts the activity of professional phagocytes, exacerbating inflammatory tissue injury in sepsis. This assigns platelets a central role in innate immune responses and identifies them as potential targets to dampen inflammatory tissue damage in clinical scenarios of severe systemic infection. In addition to their role in thrombosis and hemostasis, platelets can also migrate to sites of infection to help trap bacteria and clear the vascular surface.}, author = {Gärtner, Florian R and Ahmad, Zerkah and Rosenberger, Gerhild and Fan, Shuxia and Nicolai, Leo and Busch, Benjamin and Yavuz, Gökce and Luckner, Manja and Ishikawa Ankerhold, Hellen and Hennel, Roman and Benechet, Alexandre and Lorenz, Michael and Chandraratne, Sue and Schubert, Irene and Helmer, Sebastian and Striednig, Bianca and Stark, Konstantin and Janko, Marek and Böttcher, Ralph and Verschoor, Admar and Leon, Catherine and Gachet, Christian and Gudermann, Thomas and Mederos Y Schnitzler, Michael and Pincus, Zachary and Iannacone, Matteo and Haas, Rainer and Wanner, Gerhard and Lauber, Kirsten and Sixt, Michael K and Massberg, Steffen}, issn = {00928674}, journal = {Cell Press}, number = {6}, pages = {1368 -- 1382}, publisher = {Cell Press}, title = {{Migrating platelets are mechano scavengers that collect and bundle bacteria}}, doi = {10.1016/j.cell.2017.11.001}, volume = {171}, year = {2017}, } @article{572, abstract = {In this review, we summarize the different biosynthesis-related pathways that contribute to the regulation of endogenous auxin in plants. We demonstrate that all known genes involved in auxin biosynthesis also have a role in root formation, from the initiation of a root meristem during embryogenesis to the generation of a functional root system with a primary root, secondary lateral root branches and adventitious roots. Furthermore, the versatile adaptation of root development in response to environmental challenges is mediated by both local and distant control of auxin biosynthesis. In conclusion, auxin homeostasis mediated by spatial and temporal regulation of auxin biosynthesis plays a central role in determining root architecture.}, author = {Olatunji, Damilola and Geelen, Danny and Verstraeten, Inge}, journal = {International Journal of Molecular Sciences}, number = {12}, publisher = {MDPI}, title = {{Control of endogenous auxin levels in plant root development}}, doi = {10.3390/ijms18122587}, volume = {18}, year = {2017}, } @article{5800, abstract = {This paper presents a novel study on the functional gradation of coordinate planes in connection with the thinnest and tunnel-free (i.e., naive) discretization of sphere in the integer space. For each of the 48-symmetric quadraginta octants of naive sphere with integer radius and integer center, we show that the corresponding voxel set forms a bijection with its projected pixel set on a unique coordinate plane, which thereby serves as its functional plane. We use this fundamental property to prove several other theoretical results for naive sphere. First, the quadraginta octants form symmetry groups and subgroups with certain equivalent topological properties. Second, a naive sphere is always unique and consists of fewest voxels. Third, it is efficiently constructible from its functional-plane projection. And finally, a special class of 4-symmetric discrete 3D circles can be constructed on a naive sphere based on back projection from the functional plane.}, author = {Biswas, Ranita and Bhowmick, Partha}, issn = {09249907}, journal = {Journal of Mathematical Imaging and Vision}, number = {1}, pages = {69--83}, publisher = {Springer Nature}, title = {{On the functionality and usefulness of Quadraginta octants of naive sphere}}, doi = {10.1007/s10851-017-0718-4}, volume = {59}, year = {2017}, } @article{5799, abstract = {We construct a polyhedral surface called a graceful surface, which provides best possible approximation to a given sphere regarding certain criteria. In digital geometry terms, the graceful surface is uniquely characterized by its minimality while guaranteeing the connectivity of certain discrete (polyhedral) curves defined on it. The notion of “gracefulness” was first proposed in Brimkov and Barneva (1999) and shown to be useful for triangular mesh discretization through graceful planes and graceful lines. In this paper we extend the considerations to a nonlinear object such as a sphere. In particular, we investigate the properties of a discrete geodesic path between two voxels and show that discrete 3D circles, circular arcs, and Mobius triangles are all constructible on a graceful sphere, with guaranteed minimum thickness and the desired connectivity in the discrete topological space.}, author = {Biswas, Ranita and Bhowmick, Partha and Brimkov, Valentin E.}, issn = {0166-218X}, journal = {Discrete Applied Mathematics}, pages = {362--375}, publisher = {Elsevier}, title = {{On the polyhedra of graceful spheres and circular geodesics}}, doi = {10.1016/j.dam.2015.11.017}, volume = {216}, year = {2017}, } @inproceedings{5801, abstract = {Space filling circles and spheres have various applications in mathematical imaging and physical modeling. In this paper, we first show how the thinnest (i.e., 2-minimal) model of digital sphere can be augmented to a space filling model by fixing certain “simple voxels” and “filler voxels” associated with it. Based on elementary number-theoretic properties of such voxels, we design an efficient incremental algorithm for generation of these space filling spheres with successively increasing radius. The novelty of the proposed technique is established further through circular space filling on 3D digital plane. As evident from a preliminary set of experimental result, this can particularly be useful for parallel computing of 3D Voronoi diagrams in the digital space.}, author = {Dwivedi, Shivam and Gupta, Aniket and Roy, Siddhant and Biswas, Ranita and Bhowmick, Partha}, booktitle = {20th IAPR International Conference}, isbn = {978-3-319-66271-8}, issn = {1611-3349}, location = {Vienna, Austria}, pages = {347--359}, publisher = {Springer Nature}, title = {{Fast and Efficient Incremental Algorithms for Circular and Spherical Propagation in Integer Space}}, doi = {10.1007/978-3-319-66272-5_28}, volume = {10502}, year = {2017}, } @inbook{5803, abstract = {Different distance metrics produce Voronoi diagrams with different properties. It is a well-known that on the (real) 2D plane or even on any 3D plane, a Voronoi diagram (VD) based on the Euclidean distance metric produces convex Voronoi regions. In this paper, we first show that this metric produces a persistent VD on the 2D digital plane, as it comprises digitally convex Voronoi regions and hence correctly approximates the corresponding VD on the 2D real plane. Next, we show that on a 3D digital plane D, the Euclidean metric spanning over its voxel set does not guarantee a digital VD which is persistent with the real-space VD. As a solution, we introduce a novel concept of functional-plane-convexity, which is ensured by the Euclidean metric spanning over the pedal set of D. Necessary proofs and some visual result have been provided to adjudge the merit and usefulness of the proposed concept.}, author = {Biswas, Ranita and Bhowmick, Partha}, booktitle = {Combinatorial image analysis}, isbn = {978-3-319-59107-0}, issn = {0302-9743}, location = {Plovdiv, Bulgaria}, pages = {93--104}, publisher = {Springer Nature}, title = {{Construction of persistent Voronoi diagram on 3D digital plane}}, doi = {10.1007/978-3-319-59108-7_8}, volume = {10256}, year = {2017}, } @inproceedings{5802, abstract = {This papers introduces a definition of digital primitives based on focal points and weighted distances (with positive weights). The proposed definition is applicable to general dimensions and covers in its gamut various regular curves and surfaces like circles, ellipses, digital spheres and hyperspheres, ellipsoids and k-ellipsoids, Cartesian k-ovals, etc. Several interesting properties are presented for this class of digital primitives such as space partitioning, topological separation, and connectivity properties. To demonstrate further the potential of this new way of defining digital primitives, we propose, as extension, another class of digital conics defined by focus-directrix combination.}, author = {Andres, Eric and Biswas, Ranita and Bhowmick, Partha}, booktitle = {20th IAPR International Conference}, isbn = {978-3-319-66271-8}, issn = {1611-3349}, location = {Vienna, Austria}, pages = {388--398}, publisher = {Springer Nature}, title = {{Digital primitives defined by weighted focal set}}, doi = {10.1007/978-3-319-66272-5_31}, volume = {10502}, year = {2017}, } @article{593, abstract = {Bell correlations, indicating nonlocality in composite quantum systems, were until recently only seen in small systems. Here, we demonstrate Bell correlations in squeezed states of 5×105 Rb87 atoms. The correlations are inferred using collective measurements as witnesses and are statistically significant to 124 standard deviations. The states are both generated and characterized using optical-cavity aided measurements.}, author = {Engelsen, Nils and Krishnakumar, Rajiv and Hosten, Onur and Kasevich, Mark}, journal = {Physical Review Letters}, number = {14}, publisher = {American Physical Society}, title = {{Bell correlations in spin-squeezed states of 500 000 atoms}}, doi = {10.1103/PhysRevLett.118.140401}, volume = {118}, year = {2017}, } @article{600, abstract = {Transcription initiation at the ribosomal RNA promoter requires RNA polymerase (Pol) I and the initiation factors Rrn3 and core factor (CF). Here, we combine X-ray crystallography and cryo-electron microscopy (cryo-EM) to obtain a molecular model for basal Pol I initiation. The three-subunit CF binds upstream promoter DNA, docks to the Pol I-Rrn3 complex, and loads DNA into the expanded active center cleft of the polymerase. DNA unwinding between the Pol I protrusion and clamp domains enables cleft contraction, resulting in an active Pol I conformation and RNA synthesis. Comparison with the Pol II system suggests that promoter specificity relies on a distinct “bendability” and “meltability” of the promoter sequence that enables contacts between initiation factors, DNA, and polymerase.}, author = {Engel, Christoph and Gubbey, Tobias and Neyer, Simon and Sainsbury, Sarah and Oberthuer, Christiane and Baejen, Carlo and Bernecky, Carrie A and Cramer, Patrick}, issn = {00928674}, journal = {Cell}, number = {1}, pages = {120 -- 131.e22}, publisher = {Cell Press}, title = {{Structural basis of RNA polymerase I transcription initiation}}, doi = {10.1016/j.cell.2017.03.003}, volume = {169}, year = {2017}, }