### Random Fruits on the Zielonka Tree

Florian Horn
Stochastic games are a natural model for the synthesis of controllers confronted to adversarial and/or random actions. In particular, $\omega$-regular games of infinite length can represent reactive systems which are not expected to reach a correct state, but rather to handle a continuous stream of events. One critical resource in such applications is the memory used by the controller. In this paper, we study the amount of memory that can be saved through the use...

### More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries

Roberto Grossi, Alessio Orlandi, Rajeev Raman & S. Srinivasa Rao
We consider the problem of representing, in a compressed format, a bit-vector~$S$ of $m$ bits with $n$ $\mathbf{1}$s, supporting the following operations, where $b \in \{ \mathbf{0}, \mathbf{1} \}$: \begin{itemize} \item $\mathtt{rank}_b(S,i)$ returns the number of occurrences of bit $b$ in the prefix $S\left[1..i\right]$; \item $\mathtt{select}_b(S,i)$ returns the position of the $i$th occurrence of bit $b$ in $S$. \end{itemize} Such a data structure is called \emph{fully indexable dictionary (\textsc{fid})} [Raman, Raman, and Rao, 2007], and...

### Cover Time and Broadcast Time

Robert Elsässer & Thomas Sauerwald
We introduce a new technique for bounding the cover time of random walks by relating it to the runtime of randomized broadcast. In particular, we strongly confirm for dense graphs the intuition of Chandra et al. (1997) that the cover time of the graph is an appropriate metric for the performance of certain kinds of randomized broadcast algorithms''. In more detail, our results are as follows: \begin{itemize} \item For any graph $G=(V,E)$ of size $n$...

### Improved Approximations for Guarding 1.5-Dimensional Terrains

Khaled Elbassioni, Erik Krohn, Domagoj Matijevic, Julian Mestre & Domagoj Severdija
We present a 4-approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the currently best approximation factor of 5 (J. King, 2006). Unlike most of the previous techniques, our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on...

### Semi-Online Preemptive Scheduling: One Algorithm for All Variants

Tomas Ebenlendr & Jiri Sgall
We present a unified optimal semi-online algorithm for preemptive scheduling on uniformly related machines with the objective to minimize the makespan. This algorithm works for all types of semi-online restrictions, including the ones studied before, like sorted (decreasing) jobs, known sum of processing times, known maximal processing time, their combinations, and so on. Based on the analysis of this algorithm, we derive some global relations between various semi-online restrictions and tight bounds on the approximation...

### Forward Analysis for WSTS, Part I: Completions

Alain Finkel & Jean Goubault-Larrecq
Well-structured transition systems provide the right foundation to compute a finite basis of the set of predecessors of the upward closure of a state. The dual problem, to compute a finite representation of the set of successors of the downward closure of a state, is harder: Until now, the theoretical framework for manipulating downward-closed sets was missing. We answer this problem, using insights from domain theory (dcpos and ideal completions), from topology (sobrifications), and shed...

### Enumerating Homomorphisms

Andrei A. Bulatov, Victor Dalmau, Martin Grohe & Daniel Marx
The homomorphism problem for relational structures is an abstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision version of the homomorphism problem received a lot of attention in literature; in particular, the way the graph-theoretical structure of the variables and constraints influences the complexity of the problem is intensively studied. Here we study the problem of enumerating all the solutions with polynomial delay from a similar point of...

### The Price of Anarchy in Cooperative Network Creation Games

We analyze the structure of equilibria and the price of anarchy in the family of network creation games considered extensively in the past few years, which attempt to unify the network design and network routing problems by modeling both creation and usage costs. In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost~$\alpha$. Together the agents create...

### Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs

Glencora Borradaile, Erik D. Demaine & Siamak Tazari
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity survivable-network design, and subset TSP. The schemes run in $O(n \log n)$ time for graphs embedded on both orientable and non-orientable surfaces. This work generalizes the PTAS frameworks of Borradaile, Klein, and Mathieu (2007 and 2006) from planar graphs to bounded-genus graphs: any future problems shown to admit the required structure theorem for...

### On Local Symmetries and Universality in Cellular Automata

Laurent Boyer & Guillaume Theyssier
Cellular automata (CA) are dynamical systems defined by a finite local rule but they are studied for their global dynamics. They can exhibit a wide range of complex behaviours and a celebrated result is the existence of (intrinsically) universal CA, that is CA able to fully simulate any other CA. In this paper, we show that the asymptotic density of universal cellular automata is 1 in several families of CA defined by local symmetries. We...

### Qualitative Reachability in Stochastic BPA Games

Tomas Brazdil, Vaclav Brozek, Antonin Kucera & Jan Obdrzalek
We consider a class of infinite-state stochastic games generated by stateless pushdown automata (or, equivalently, 1-exit recursive state machines), where the winning objective is specified by a regular set of target configurations and a qualitative probability constraint ${>}0$' or ${=}1$'. The goal of one player is to maximize the probability of reaching the target set so that the constraint is satisfied, while the other player aims at the opposite. We show that the winner in...

### Shortest Paths Avoiding Forbidden Subpaths

Mustaq Ahmed & Anna Lubiw
In this paper we study a variant of the shortest path problem in graphs: given a weighted graph $G$ and vertices $s$ and $t$, and given a set $X$ of forbidden paths in $G$, find a shortest $s$-$t$ path $P$ such that no path in $X$ is a subpath of $P$. Path $P$ is allowed to repeat vertices and edges. We call each path in $X$ an \emph{exception}, and our desired path a \emph{shortest exception...

### Generating Shorter Bases for Hard Random Lattices

Joel Alwen & Chris Peikert
We revisit the problem of generating a hard'' random lattice together with a basis of relatively short vectors. This problem has gained in importance lately due to new cryptographic schemes that use such a procedure for generating public/secret key pairs. In these applications, a shorter basis directly corresponds to milder underlying complexity assumptions and smaller key sizes. The contributions of this work are twofold. First, using the \emph{Hermite normal form} as an organizing principle, we...

### An Order on Sets of Tilings Corresponding to an Order on Languages

Nathalie Aubrun & Mathieu Sablik
Traditionally a tiling is defined with a finite number of finite forbidden patterns. We can generalize this notion considering any set of patterns. Generalized tilings defined in this way can be studied with a dynamical point of view, leading to the notion of subshift. In this article we establish a correspondence between an order on subshifts based on dynamical transformations on them and an order on languages of forbidden patterns based on computability properties.

### The Dynamic Complexity of Formal Languages

Wouter Gelade, Marcel Marquardt & Thomas Schwentick
The paper investigates the power of the dynamic complexity classes DynFO, DynQF and DynPROP over string languages. The latter two classes contain problems that can be maintained using quantifier-free first-order updates, with and without auxiliary functions, respectively. It is shown that the languages maintainable in DynPROP exactly are the regular languages, even when allowing arbitrary precomputation. This enables lower bounds for DynPROP and separates DynPROP from DynQF and DynFO. Further, it is shown that any...

### Computing Graph Roots Without Short Cycles

Babak Farzad, Lap Chi Lau, Van Bang Le & Nguyen Ngoc Tuy
Graph $G$ is the square of graph $H$ if two vertices $x,y$ have an edge in $G$ if and only if $x,y$ are of distance at most two in $H$. Given $H$ it is easy to compute its square $H^2$, however Motwani and Sudan proved that it is NP-complete to determine if a given graph $G$ is the square of some graph $H$ (of girth $3$). In this paper we consider the characterization and recognition...

### Randomness on Computable Probability Spaces - A Dynamical Point of View

Peter Gacs, Mathieu Hoyrup & Cristobal Rojas
We extend the notion of randomness (in the version introduced by Schnorr) to computable Probability Spaces and compare it to a \emph{dynamical} notion of randomness: typicality. Roughly, a point is \emph{typical} for some dynamic, if it follows the statistical behavior of the system (Birkhoff's pointwise ergodic theorem). We prove that a point is Schnorr random if and only if it is typical for every \emph{mixing} computable dynamics. To prove the result we develop some tools...

### Testing Linear-Invariant Non-Linear Properties

Arnab Bhattacharyya, Victor Chen, Madhu Sudan & Ning Xie
We consider the task of testing properties of Boolean functions that are invariant under linear transformations of the Boolean cube. Previous work in property testing, including the linearity test and the test for Reed-Muller codes, has mostly focused on such tasks for linear properties. The one exception is a test due to Green for {}triangle freeness'': A function $f:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$ satisfies this property if $f(x),f(y),f(x+y)$ do not all equal $1$, for any pair $x,y\in\mathbb{F}_{2}^{n}$. Here we...

### A Polynomial Kernel for Multicut in Trees

Nicolas Bousquet, Jean Daligault, Stephan Thomasse & Anders Yeo
The {\sc Multicut In Trees} problem consists in deciding, given a tree, a set of requests (i.e. paths in the tree) and an integer $k$, whether there exists a set of $k$ edges cutting all the requests. This problem was shown to be FPT by Guo and Niedermeyer (2005). They also provided an exponential kernel. They asked whether this problem has a polynomial kernel. This question was also raised by Fellows (2006). We show that...

### On the Average Complexity of Moore's State Minimization Algorithm

Frederique Bassino, Julien David & Cyril Nicaud
We prove that, for any arbitrary finite alphabet and for the uniform distribution over deterministic and accessible automata with $n$ states, the average complexity of Moore's state minimization algorithm is in $\mathcal{O}(n \log n)$. Moreover this bound is tight in the case of unary automata.

### A Generalization of Nemhauser and Trotter's Local Optimization Theorem

Michael R. Fellows, Jiong Guo, Hannes Moser & Rolf Niedermeier
The Nemhauser-Trotter local optimization theorem applies to the NP-hard \textsc{Vertex Cover} problem and has applications in approximation as well as parameterized algorithmics. We present a framework that generalizes Nemhauser and Trotter's result to vertex deletion and graph packing problems, introducing novel algorithmic strategies based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). We exhibit our framework using a generalization of \textsc{Vertex Cover}, called \textrm{\sc Bounded-Degree Deletion}, that has...

### Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties

Mahdi Cheraghchi & Amin Shokrollahi
We consider the problem of uniform sampling of points on an algebraic variety. Specifically, we develop a randomized algorithm that, given a small set of multivariate polynomials over a sufficiently large finite field, produces a common zero of the polynomials almost uniformly at random. The statistical distance between the output distribution of the algorithm and the uniform distribution on the set of common zeros is polynomially small in the field size, and the running time...

### Fragments of First-Order Logic over Infinite Words

Volker Diekert & Manfred Kufleitner

• 2009
134

• Text
134