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

### A Complexity Dichotomy for Partition Functions with Mixed Signs

Leslie Ann Goldberg, Martin Grohe, Mark Jerrum & Marc Thurley
\emph{Partition functions}, also known as \emph{homomorphism functions}, form a rich family of graph invariants that contain combinatorial invariants such as the number of $k$-colourings or the number of independent sets of a graph and also the partition functions of certain spin glass'' models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill (2000) and Bulatov and Grohe (2005), we completely classify the computational complexity of partition functions. Our...

### Knowledge Infusion: In Pursuit of Robustness in Artificial Intelligence

Leslie G Valiant
Endowing computers with the ability to apply commonsense knowledge with human-level performance is a primary challenge for computer science, comparable in importance to past great challenges in other fields of science such as the sequencing of the human genome. The right approach to this problem is still under debate. Here we shall discuss and attempt to justify one approach, that of {\it knowledge infusion}. This approach is based on the view that the fundamental objective...

### Algorithms for Message Ferrying on Mobile ad hoc Networks

Mostafa Ammar, Deeparnab Chakrabarty, Atish Das Sarma, Subrahmanyam Kalyanasundaram & Richard J. Lipton
Message Ferrying is a mobility assisted technique for working around the disconnectedness and sparsity of Mobile ad hoc networks. One of the importantquestions which arise in this context is to determine the routing of the ferry,so as to minimize the buffers used to store data at the nodes in thenetwork. We introduce a simple model to capture the ferry routingproblem. We characterize {\em stable} solutions of the system andprovide efficient approximation algorithms for the {\sc...

### Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness

Andre Gronemeier
Here we prove an asymptotically optimal lower bound on the information complexity of the $k$-party disjointness function with the unique intersection promise, an important special case of the well known disjointness problem, and the AND$_k$-function in the number in the hand model. Our $\Omega(n/k)$ bound for disjointness improves on an earlier $\Omega(n/(k \log k))$ bound by Chakrabarti {\it et al.}~(2003), who obtained an asymptotically tight lower bound for one-way protocols, but failed to do so...

### The Covering and Boundedness Problems for Branching Vector Addition Systems

Stéphane Demri, Marcin Jurdzinski, Oded Lachish & Ranko Lazic
The covering and boundedness problems for branching vector addition systems are shown complete for doubly-exponential time.

### Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP

Stefan Kratsch
The relation of constant-factor approximability to fixed-parameter tractability and kernelization is a long-standing open question. We prove that two large classes of constant-factor approximable problems, namely~$\textsc{MIN F}^+\Pi_1$ and~$\textsc{MAX NP}$, including the well-known subclass~$\textsc{MAX SNP}$, admit polynomial kernelizations for their natural decision versions. This extends results of Cai and Chen (JCSS 1997), stating that the standard parameterizations of problems in~$\textsc{MAX SNP}$ and~$\textsc{MIN F}^+\Pi_1$ are fixed-parameter tractable, and complements recent research on problems that do not admit...

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

### On the Borel Inseparability of Game Tree Languages

Szczepan Hummel, Henryk Michalewski & Damian Niwinski
The game tree languages can be viewed as an automata-theoretic counterpart of parity games on graphs. They witness the strictness of the index hierarchy of alternating tree automata, as well as the fixed-point hierarchy over binary trees. We consider a game tree language of the first non-trivial level, where Eve can force that 0 repeats from some moment on, and its dual, where Adam can force that 1 repeats from some moment on. Both these...

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

### On Timed Alternating Simulation for Concurrent Timed Games

Laura Bozzelli, Axel Legay & Sophie Pinchinat
We address the problem of alternating simulation refinement for concurrent timed games (\TG). We show that checking timed alternating simulation between\TG is \EXPTIME-complete, and provide a logical characterization of thispreorder in terms of a meaningful fragment of a new logic, \TAMTLSTAR.\TAMTLSTAR is an action-based timed extension of standard alternating-timetemporal logic \ATLSTAR, which allows to quantify on strategies where thedesignated player is not responsible for blocking time. While for full \TAMTLSTAR, model-checking \TG is undecidable, we...

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

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

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

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

### Complexity Analysis of Term Rewriting Based on Matrix and Context Dependent Interpretations

Georg Moser, Andreas Schnabl & Johannes Waldmann
For a given (terminating) term rewriting system one can often estimate its \emph{derivational complexity} indirectly by looking at the proof method that established termination. In this spirit we investigate two instances of the interpretation method: \emph{matrix interpretations} and \emph{context dependent interpretations}. We introduce a subclass of matrix interpretations, denoted as \emph{triangular matrix interpretations}, which induce polynomial derivational complexity and establish tight correspondence results between a subclass of context dependent interpretations and restricted triangular matrix interpretations....

### Iterative Methods in Combinatorial Optimization

R. Ravi
We describe a simple iterative method for proving a variety of results in combinatorial optimization. It is inspired by Jain's iterative rounding method (FOCS 1998) for designing approximation algorithms for survivable network design problems, and augmented with a relaxation idea in the work of Lau, Naor, Salvatipour and Singh (STOC 2007) on designing an approximation algorithm for its degree bounded version. At the heart of the method is a counting argument that redistributes tokens from...

### Preface -- IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Ravi Kannan & K. Narayan Kumar
This volume contains the proceedings of the 29th international conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), organized under the auspices of the Indian Association for Research in Computing Science (IARCS) at the Indian Institute of Technology, Kanpur, India.

### Fighting bit Rot with Types (Experience Report: Scala Collections)

We report on our experiences in redesigning Scala's collection libraries, focussing on the role that type systems play in keeping software architectures coherent over time. Type systems can make software architecture more explicit but, if they are too weak, can also cause code duplication. We show that code duplication can be avoided using two of Scala's type constructions: higher-kinded types and implicit parameters and conversions.

### Randomness extractors -- applications and constructions

Avi Wigderson
Randomness extractors are efficient algorithms which convert weak random sources into nearly perfect ones. While such purification of randomness was the original motivation for constructing extractors, these constructions turn out to have strong pseudorandom properties which found applications in diverse areas of computer science and combinatorics. We will highlight some of the applications, as well as recent constructions achieving near-optimal extraction.

### Priced Timed Automata: Theory and Tools

Kim G. Larsen
Priced timed automata are emerging as useful formalisms for modeling and analysing a broad range of resource allocation problems. In this extended abstract, we highlight recent (un)deci\-dability results related to priced timed automata as well as point to a number of open problems.

### Recurrence and Transience for Probabilistic Automata

Mathieu Tracol, Christel Baier & Marcus Grösser
In a context of $\omega$-regular specifications for infinite execution sequences, the classical B\"uchi condition, or repeated liveness condition, asks that an accepting state is visited infinitely often. In this paper, we show that in a probabilistic context it is relevant to strengthen this infinitely often condition. An execution path is now accepting if the \emph{proportion} of time spent on an accepting state does not go to zero as the length of the path goes to...

### Structure and Specification as Sources of Complexity

Anuj Dawar
If computational complexity is the study of what makes certain computational problems inherently difficult to solve, an important contribution of descriptive complexity in this regard is the separation it provides between the specification of a decision problem and the structure against which this specification is checked. The formalisation of these two aspects leads to tools for studying them as sources of complexity, and on the one hand leads to results in the characterisation of complexity...

### Modelchecking counting properties of 1-safe nets with buffers in paraPSPACE

M. Praveen & Kamal Lodaya
We consider concurrent systems that can be modelled as $1$-safe Petri nets communicating through a fixed set of buffers (modelled as unbounded places). We identify a parameter $\ben$, which we call benefit depth'', formed from the communication graph between the buffers. We show that for our system model, the coverability and boundedness problems can be solved in polynomial space assuming $\ben$ to be a fixed parameter, that is, the space requirement is $f(\ben)p(n)$, where $f$...

• 2009
134

• Text
134

• Dagstuhl
134