### Test DOI: No longer exists

This does was a test DOI and no longer exists.

### A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression

Danny Hermelin, Gad M. Landau, Shir Landau & Oren Weimann
The edit distance problem is a classical fundamental problem in computer science in general, and in combinatorial pattern matching in particular. The standard dynamic-programming solution for this problem computes the edit-distance between a pair of strings of total length $O(N)$ in $O(N^2)$ time. To this date, this quadratic upper-bound has never been substantially improved for general strings. However, there are known techniques for breaking this bound in case the strings are known to compress well...

### Tractable Structures for Constraint Satisfaction with Truth Tables

Daniel Marx
The way the graph structure of the constraints influences the complexity of constraint satisfaction problems (CSP) is well understood for bounded-arity constraints. The situation is less clear if there is no bound on the arities. In this case the answer depends also on how the constraints are represented in the input. We study this question for the truth table representation of constraints. We introduce a new hypergraph measure {\em adaptive width} and show that CSP...

### Hardness and Algorithms for Rainbow Connectivity

Sourav Chakraborty, Eldar Fischer, Arie Matsliah & Raphael Yuster
An edge-colored graph $G$ is {\em rainbow connected} if any two vertices are connected by a path whose edges have distinct colors. The {\em rainbow connectivity} of a connected graph $G$, denoted $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In addition to being a natural combinatorial problem, the rainbow connectivity problem is motivated by applications in cellular networks. In this paper we give the first...

### Analyzing the Implicit Computational Complexity of object-oriented programs

Jean-Yves Marion & Romain Pechoux
A sup-interpretation is a tool which provides upper bounds on the size of the values computed by the function symbols of a program. Sup-interpretations have shown their interest to deal with the complexity of first order functional programs. This paper is an attempt to adapt the framework of sup-interpretations to a fragment of object-oriented programs, including loop and while constructs and methods with side effects. We give a criterion, called brotherly criterion, which uses the...

### Average-Time Games

Marcin Jurdzinski & Ashutosh Trivedi
An average-time game is played on the infinite graph of configurations of a finite timed automaton. The two players, Min and Max, construct an infinite run of the automaton by taking turns to perform a timed transition. Player Min wants to minimize the average time per transition and player Max wants to maximize it. A solution of average-time games is presented using a reduction to average-price game on a finite graph. A direct consequence is...

### 2008 Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Ramesh Hariharan, Madhavan Mukund & V Vinay
This volume contains the proceedings of the 28th international conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008), organized under the auspices of the Indian Association for Research in Computing Science (IARCS). This year's conference attracted 117 submissions. Each submission was reviewed by at least three independent referees. The final selection of the papers making up the programme was done through an electronic discussion on EasyChair, spanning two weeks, without a...

### Boolean algebras of unambiguous context-free languages

Didier Caucal
Several recent works have studied subfamilies of deterministic context-free languages with good closure properties, for instance the families of input-driven or visibly pushdown languages, or more generally families of languages accepted by pushdown automata whose stack height can be uniquely determined by the input word read so far. These ideas can be described as a notion of synchronization. In this paper we present an extension of synchronization to all context-free languages using graph grammars. This...

### Increasing the power of the verifier in Quantum Zero Knowledge

Andre Chailloux & Iordanis Kerenidis
In quantum zero knowledge, the assumption was made that the verifier is only using unitary operations. Under this assumption, many nice properties have been shown about quantum zero knowledge, including the fact that Honest-Verifier Quantum Statistical Zero Knowledge ($HVQSZK$) is equal to Cheating-Verifier Quantum Statistical Zero Knowledge ($QSZK$) (see ~\cite{Wat02,Wat06}). In this paper, we study what happens when we allow an honest verifier to flip some coins in addition to using unitary operations. Flipping a...

### A new upper bound for 3-SAT

Josep Diaz, Lefteris Kirousis, Dieter Mitsche & Xavier Perez-Gimenez
We show that a randomly chosen $3$-CNF formula over $n$ variables with clauses-to-variables ratio at least $4.4898$ is asymptotically almost surely unsatisfiable. The previous best such bound, due to Dubois in 1999, was $4.506$. The first such bound, independently discovered by many groups of researchers since 1983, was $5.19$. Several decreasing values between $5.19$ and $4.506$ were published in the years between. The probabilistic techniques we use for the proof are, we believe, of independent...

### Abstraction Refinement for Games with Incomplete Information

Rayna Dimitrova & Bernd Finkbeiner
Counterexample-guided abstraction refinement (CEGAR) is used in automated software analysis to find suitable finite-state abstractions of infinite-state systems. In this paper, we extend CEGAR to games with incomplete information, as they commonly occur in controller synthesis and modular verification. The challenge is that, under incomplete information, one must carefully account for the knowledge available to the player: the strategy must not depend on information the player cannot see. We propose an abstraction mechanism for games...

### Some Sieving Algorithms for Lattice Problems

V. Arvind & Pushkar S. Joglekar
We study the algorithmic complexity of lattice problems based on the sieving technique due to Ajtai, Kumar, and Sivakumar~\cite{aks}. Given a $k$-dimensional subspace $M\subseteq \R^n$ and a full rank integer lattice $\L\subseteq \Q^n$, the \emph{subspace avoiding problem} SAP, defined by Bl\"omer and Naewe \cite{blomer}, is to find a shortest vector in $\L\setminus M$. We first give a $2^{O(n+k \log k)}$ time algorithm to solve \emph{the subspace avoiding problem}. Applying this algorithm we obtain the following...

### Profinite Methods in Automata Theory

Jean-Eric Pin
This survey paper presents the success story of the topological approach to automata theory. It is based on profinite topologies, which are built from finite topogical spaces. The survey includes several concrete applications to automata theory.

### Deterministic Automata and Extensions of Weak MSO

Mikolaj Bojanczyk & Szymon Torunczyk
We introduce a new class of automata on infinite words, called min-automata. We prove that min-automata have the same expressive power as weak monadic second-order logic (weak MSO) extended with a new quantifier, the recurrence quantifier. These results are dual to a framework presented in \cite{max-automata}, where max-automata were proved equivalent to weak MSO extended with an unbounding quantifier. We also present a general framework, which tries to explain which types of automata on infinite...

### 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...

### Efficient Isomorphism Testing for a Class of Group Extensions

Francois Le Gall
The group isomorphism problem asks whether two given groups are isomorphic or not. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. In this paper we study this problem for a class of groups corresponding to one of the simplest ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an...

### 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 Approximation Algorithm for l_infinity Fitting Robinson Structures to Distances

Victor Chepoi & Morgan Seston
In this paper, we present a factor 16 approximation algorithm for the following NP-hard distance fitting problem: given a finite set $X$ and a distance $d$ on $X$, find a Robinsonian distance $d_R$ on $X$ minimizing the $l_{\infty}$-error $||d-d_R||_{\infty}=\mbox{max}_{x,y\in X}\{ |d(x,y)-d_R(x,y)|\}.$ A distance $d_R$ on a finite set $X$ is Robinsonian if its matrix can be symmetrically permuted so that its elements do not decrease when moving away from the main diagonalalong any row or...

### 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...

### Undecidable Properties of Limit Set Dynamics of Cellular Automata

Pietro Di Lena & Luciano Margara
Cellular Automata (CA) are discrete dynamical systems and an abstract model of parallel computation. The limit set of a cellular automaton is its maximal topological attractor. A well know result, due to Kari, says that all nontrivial properties of limit sets are undecidable. In this paper we consider properties of limit set dynamics, i.e. properties of the dynamics of Cellular Automata restricted to their limit sets. There can be no equivalent of Kari's Theorem for...

### Reverse Engineering Prefix Tables

Julien Clement, Maxime Crochemore & Giuseppina Rindone
The Prefix table of a string reports for each position the maximal length of its prefixes starting here. The Prefix table and its dual Suffix table are basic tools used in the design of the most efficient string-matching and pattern extraction algorithms. These tables can be computed in linear time independently of the alphabet size. We give an algorithmic characterisation of a Prefix table (it can be adapted to a Suffix table). Namely, the algorithm...

### Economical Caching

Matthias Englert, Heiko Röglin, Jacob Spönemann & Berthold Vöcking
We study the management of buffers and storages in environments with unpredictably varying prices in a competitive analysis. In the economical caching problem, there is a storage with a certain capacity. For each time step, an online algorithm is given a price from the interval $[1,\alpha]$, a consumption, and possibly a buying limit. The online algorithm has to decide the amount to purchase from some commodity, knowing the parameter $\alpha$ but without knowing how the...

### 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...

### 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...

• 2009
29,442

• Text
29,442

#### Affiliations

• Norsar
2
• University of Oslo
1
• United States Geological Survey
1
• University of Stuttgart
1