### Harnessing the Multicores: Nested Data Parallelism in Haskell

Simon Peyton Jones, Roman Leshchinskiy, Gabriele Keller & Manuel M T Chakravarty
If you want to program a parallel computer, a purely functional language like Haskell is a promising starting point. Since the language is pure, it is by-default safe for parallel evaluation, whereas imperative languages are by-default unsafe. But that doesn\'t make it easy! Indeed it has proved quite difficult to get robust, scalable performance increases through parallel functional programming, especially as the number of processors increases. A particularly promising and well-studied approach to employing large...

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

### Lower Bounds for Multi-Pass Processing of Multiple Data Streams

Nicole Schweikardt
This paper gives a brief overview of computation models for data stream processing, and it introduces a new model for multi-pass processing of multiple streams, the so-called \emph{mp2s-automata}. Two algorithms for solving the set disjointness problem with these automata are presented. The main technical contribution of this paper is the proof of a lower bound on the size of memory and the number of heads that are required for solving the set disjointness problem with...

### Sound Lemma Generation for Proving Inductive Validity of Equations

Takahito Aoto
In many automated methods for proving inductive theorems, finding a suitable generalization of a conjecture is a key for the success of proof attempts. On the other hand, an obtained generalized conjecture may not be a theorem, and in this case hopeless proof attempts for the incorrect conjecture are made, which is against the success and efficiency of theorem proving. Urso and Kounalis (2004) proposed a generalization method for proving inductive validity of equations, called...

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

### On the Memory Consumption of Probabilistic Pushdown Automata

Tomas Brazdil, Javier Esparza & Stefan Kiefer
We investigate the problem of evaluating memory consumption for systems modelled by probabilistic pushdown automata (pPDA). The space needed by a runof a pPDA is the maximal height reached by the stack during the run. Theproblem is motivated by the investigation of depth-first computations that playan important role for space-efficient schedulings of multithreaded programs. We study the computation of both the distribution of the memory consumption and its expectation. For the distribution, we show that...

### Kernels for Feedback Arc Set In Tournaments

Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh & Stéphan Thomassé
A tournament $T = (V,A)$ is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on $n$ vertices and an integer parameter $k$, the {\sc Feedback Arc Set} problem asks whether thegiven digraph has a set of $k$ arcs whose removal results in an acyclicdigraph. The {\sc Feedback Arc Set} problem restricted to tournaments is knownas the {\sc $k$-Feedback Arc Set in Tournaments ($k$-FAST)} problem....

### Pruning 2-Connected Graphs

Chandra Chekuri & Nitish Korula
Given an edge-weighted undirected graph $G$ with a specified set of terminals, let the \emph{density} of any subgraph be the ratio of its weight/cost to the number of terminals it contains. If $G$ is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of $G$? We answer this question in the affirmative by giving an algorithm to \emph{prune} $G$ and find such subgraphs of any desired size, at the cost of only...

### Verification and Refutation of Probabilistic Specifications via Games

Mark Kattenbelt & Michael Huth
We develop an abstraction-based framework to check probabilistic specifications of Markov Decision Processes (MDPs) using the stochastic two-player game abstractions (\ie games'') developed by Kwiatkowska et al.\ as a foundation. We define an abstraction preorder for these game abstractions which enables us to identify many new game abstractions for each MDP --- ranging from compact and imprecise to complex and precise. This added ability to trade precision for efficiency is crucial for scalable software model...

### Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves

Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh & Yngve Villanger
The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least $k$ leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms. Here, we take a kernelization based approach to the {\sc $k$-Leaf-Out-Branching} problem. We give the first polynomial kernel for {\sc Rooted $k$-Leaf-Out-Branching}, a variant of {\sc $k$-Leaf-Out-Branching} where the root of the tree searched for is...

### On Estimation Algorithms vs Approximation Algorithms

Uriel Feige
In a combinatorial optimization problem, when given an input instance, one seeks a feasible solution that optimizes the value of the objective function. Many combinatorial optimization problems are NP-hard. A way of coping with NP-hardness is by considering approximation algorithms. These algorithms run in polynomial time, and their performance is measured by their approximation ratio: the worst case ratio between the value of the solution produced and the value of the (unknown) optimal solution. In...

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

### A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints

Kenya Ueno
We introduce a new technique proving formula size lower bounds based on the linear programming bound originally introduced by Karchmer, Kushilevitz and Nisan (1995) and the theory of stable set polytope. We apply it to majority functions and prove their formula size lower bounds improved from the classical result of Khrapchenko (1971). Moreover, we introduce a notion of unbalanced recursive ternary majority functions motivated by a decomposition theory of monotone self-dual functions and give integrally...

### Preface -- 26th International Symposium on Theoretical Aspects of Computer Science

Susanne Albers & Jean-Yves Marion
The interest in STACS has remained at a high level over the past years. The STACS 2009 call for papers led to over 280 submissions from 41 countries. Each paper was assigned to three program committee members. The program committee held a two-week electronic meeting at the beginning of November and selected 54 papers. As co-chairs of the program committee, we would like to sincerely thank its members and the many external referees for their...

### On the Power of Imperfect Information

Dietmar Berwanger & Laurent Doyen
We present a polynomial-time reduction from parity games with imperfect information to safety games with imperfect information. Similar reductions for games with perfect information typically increase the game size exponentially. Our construction avoids such a blow-up by using imperfect information to realise succinct counters which cover a range exponentially larger than their size. In particular, the reduction shows that the problem of solving imperfect-information games with safety conditions is \EXPTIME-complete.

### Nonclairvoyant Speed Scaling for Flow and Energy

Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela & Kirk Pruhs
We study online nonclairvoyant speed scaling to minimize total flow time plus energy. We first consider the traditional model where the power function is $P(s)=s^\alpha$. We give a nonclairvoyant algorithm that is shown to be $O(\alpha^3)$-competitive. We then show an $\Omega( \alpha^{1/3-\epsilon} )$ lower bound on the competitive ratio of any nonclairvoyant algorithm. We also show that there are power functions for which no nonclairvoyant algorithm can be $O(1)$-competitive.

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

### About models of security protocols

Hubert Comon-Lundh
In this paper, mostly consisting of definitions, we revisit the models of security protocols: we show that the symbolic and the computational models (as well as others) are instances of a same generic model. Our definitions are also parametrized by the security primitives, the notion of attacker and, to some extent, the process calculus.

### Bounded Size Graph Clustering with Applications to Stream Processing

Rohit Khandekar, Kirsten Hildrum, Sujay Parekh, Deepak Rajan, Jay Sethuraman & Joel Wolf
We introduce a graph clustering problem motivated by a stream processing application. Input to our problem is an undirected graph with vertex and edge weights. A cluster is a subset of the vertices. The {\em size} of a cluster is defined as the total vertex weight in the subset plus the total edge weight at the boundary of the cluster. The bounded size graph clustering problem ($\GC$) is to partition the vertices into clusters of...

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

### Ambiguity and Communication

Juraj Hromkovic & Georg Schnitger
The ambiguity of a nondeterministic finite automaton (NFA) $N$ for input size $n$ is the maximal number of accepting computations of $N$ for an input of size $n$. For all $k,r \in \mathbb{N}$ we construct languages $L_{r,k}$ which can be recognized by NFA's with size $k \cdot$poly$(r)$ and ambiguity $O(n^k)$, but $L_{r,k}$ has only NFA's with exponential size, if ambiguity $o(n^k)$ is required. In particular, a hierarchy for polynomial ambiguity is obtained, solving a long...

### On the Tightening of the Standard SDP for Vertex Cover with $ell_1$ Inequalities

Konstantinos Georgiou, Avner Magen & Iannis Tourlakis
We show that the integrality gap of the standard SDP for \vc~on instances of $n$ vertices remains $2-o(1)$ even after the addition of \emph{all} hypermetric inequalities. Our lower bound requires new insights into the structure of SDP solutions behaving like $\ell_1$ metric spaces when one point is removed. We also show that the addition of all $\ell_1$ inequalities eliminates any solutions that are not convex combination of integral solutions. Consequently, we provide the strongest possible...

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

### Weak MSO with the Unbounding Quantifier

Mikolaj Bojanczyk
A new class of languages of infinite words is introduced, called the \emph{max-regular languages}, extending the class of $\omega$-regular languages. The class has two equivalent descriptions: in terms of automata (a type of deterministic counter automaton), and in terms of logic (weak monadic second-order logic with a bounding quantifier). Effective translations between the logic and automata are given.

### Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence

Marius Zimand
An infinite binary sequence has randomness rate at least $\sigma$ if, for almost every $n$, the Kolmogorov complexity of its prefix of length $n$ is at least $\sigma n$. It is known that for every rational $\sigma \in (0,1)$, on one hand, there exists sequences with randomness rate $\sigma$ that can not be effectively transformed into a sequence with randomness rate higher than $\sigma$ and, on the other hand, any two independent sequences with randomness...

• 2009
134

• Text
134