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

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

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

### Synthesis of Finite-state and Definable Winning Strategies

Alexander Rabinovich
Church's Problem asks for the construction of a procedure which, given a logical specification $\varphi$ on sequence pairs, realizes for any input sequence $I$ an output sequence $O$ such that $(I,O)$ satisfies $\varphi$. McNaughton reduced Church's Problem to a problem about two-player$\omega$-games. B\"uchi and Landweber gave a solution for Monadic Second-Order Logic of Order ($\MLO$) specifications in terms of finite-state strategies. We consider two natural generalizations of the Church problem to countable ordinals: the first...

### Nash Equilibrium in Generalised Muller Games

Soumya Paul & Sunil Simon
We suggest that extending Muller games with preference ordering for players is a natural way to reason about unbounded duration games. In this context, we look at the standard solution concept of Nash equilibrium for non-zero sum games. We show that Nash equilibria always exists for such generalised Muller games on finite graphs and present a procedure to compute an equilibrium strategy profile. We also give a procedure to compute a subgame perfect equilibrium when...

### The Power of Depth 2 Circuits over Algebras

Chandan Saha, Ramprasad Saptharishi & Nitin Saxena
We study the problem of polynomial identity testing (PIT) for depth $2$ arithmetic circuits over matrix algebra. We show that identity testing of depth $3$ ($\Sigma \Pi \Sigma$) arithmetic circuits over a field $\F$ is polynomial time equivalent to identity testing of depth $2$ ($\Pi \Sigma$) arithmetic circuits over $\mathsf{U}_2(\mathbb{F})$, the algebra of upper-triangular $2\times 2$ matrices with entries from $\F$. Such a connection is a bit surprising since we also show that, as computational...

### Deductive Verification of Continuous Dynamical Systems

Ankur Taly & Ashish Tiwari
We define the notion of inductive invariants for continuous dynamical systems and use it to present inference rules for safety verification of polynomial continuous dynamical systems. We present two different sound and complete inference rules, but neither of these rules can be effectively applied. We then present several simpler and practical inference rules that are sound and relatively complete for different classes of inductive invariants. The simpler inference rules can be effectively checked when all...

### A Fine-grained Analysis of a Simple Independent Set Algorithm

Joachim Kneis, Alexander Langer & Peter Rossmanith
We present a simple exact algorithm for the \is\ problem with a runtime bounded by $O(\rt^n \poly(n))$. This bound is obtained by, firstly, applying a new branching rule and, secondly, by a distinct, computer-aided case analysis. The new branching rule uses the concept of satellites and has previously only been used in an algorithm for sparse graphs. The computer-aided case analysis allows us to capture the behavior of our algorithm in more detail than in...

### Using Elimination Theory to construct Rigid Matrices

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar & Jayalal Sarma M. N.
The rigidity of a matrix $A$ for target rank $r$ is the minimum number of entries of $A$ that must be changed to ensure that the rank of the altered matrix is at most $r$. Since its introduction by Valiant \cite{Val77}, rigidity and similar rank-robustness functions of matrices have found numerous applications in circuit complexity, communication complexity, and learning complexity. Almost all $\nbyn$ matrices over an infinite field have a rigidity of $(n-r)^2$. It is...

• 2009
134

• Text
134