134 Works

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

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

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

Non-Local Box Complexity and Secure Function Evaluation

Marc Kaplan, Iordanis Kerenidis, Sophie Laplante & Jérémie Roland
A non-local box is an abstract device into which Alice and Bob input bits $x$ and $y$ respectively and receive outputs $a$ and $b$ respectively, where $a,b$ are uniformly distributed and $a \oplus b = x \wedge y$. Such boxes have been central to the study of quantum or generalized non-locality as well as the simulation of non-signaling distributions. In this paper, we start by studying how many non-local boxes Alice and Bob need in...

Functionally Private Approximations of Negligibly-Biased Estimators

André Madeira & S. Muthukrishnan
We study functionally private approximations. An approximation function $g$ is {\em functionally private} with respect to $f$ if, for any input $x$, $g(x)$ reveals no more information about $x$ than $f(x)$. Our main result states that a function $f$ admits an efficiently-computable functionally private approximation $g$ if there exists an efficiently-computable and negligibly-biased estimator for $f$. Contrary to previous generic results, our theorem is more general and has a wider application reach.We provide two distinct...

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

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

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

Martin Odersky & Adriaan Moors
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.

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.

Runtime Monitoring of Metric First-order Temporal Properties

David Basin, Felix Klaedtke, Samuel Müller & Birgit Pfitzmann
We introduce a novel approach to the runtime monitoring of complex system properties. In particular, we present an online algorithm for a safety fragment of metric first-order temporal logic that is considerably more expressive than the logics supported by prior monitoring methods. Our approach, based on automatic structures, allows the unrestricted use of negation, universal and existential quantification over infinite domains, and the arbitrary nesting of both past and bounded future operators. Moreover, we show...

All-Norms and All-L_p-Norms Approximation Algorithms

Daniel Golovin, Anupam Gupta, Amit Kumar & Kanat Tangwongsan
In many optimization problems, a solution can be viewed as ascribing a ``cost\'\' to each client, and the goal is to optimize some aggregation of the per-client costs. We often optimize some $L_p$-norm (or some other symmetric convex function or norm) of the vector of costs---though different applications may suggest different norms to use. Ideally, we could obtain a solution that optimizes several norms simultaneously. In this paper, we examine approximation algorithms that simultaneously perform...

Leaf languages and string compression

Markus Lohrey
Tight connections between leafs languages and strings compressed via straight-line programs (SLPs) are established. It is shown that the compressed membership problem for a language $L$ is complete for the leaf language class defined by $L$ via logspace machines. A more difficult variant of the compressed membership problem for $L$ is shown to be complete for the leaf language class defined by $L$ via polynomial time machines. As a corollary, a fixed linear visibly pushdown...

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

Banach-Mazur Games on Graphs

Erich Graedel
We survey determinacy, definability, and complexity issues of Banach-Mazur games on finite and infinite graphs. Infinite games where two players take turns to move a token through a directed graph, thus tracing out an infinite path, have numerous applications in different branches of mathematics and computer science. In the usual format, the possible moves of the players are given by the edges of the graph; in each move a player takes the token from its...

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

Locally Decodable Quantum Codes

Jop Briet & Ronald De Wolf
We study a quantum analogue of locally decodable error-correcting codes. A $q$-query \emph{locally decodable quantum code} encodes $n$ classical bits in an $m$-qubit state, in such a way that each of the encoded bits can be recovered with high probability by a measurement on at most $q$ qubits of the quantum code, even if a constant fraction of its qubits have been corrupted adversarially. We show that such a quantum code can be transformed into...

Compressed Representations of Permutations, and Applications

Jeremy Barbay & Gonzalo Navarro
We explore various techniques to compress a permutation $\pi$ over $n$ integers, taking advantage of ordered subsequences in $\pi$, while supporting its application $\pi(i)$ and the application of its inverse $\pi^{-1}(i)$ in small time. Our compression schemes yield several interesting byproducts, in many cases matching, improving or extending the best existing results on applications such as the encoding of a permutation in order to support iterated applications $\pi^{k}(i)$ of it, of integer functions, and of...

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

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

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

Büchi Complementation Made Tight

Sven Schewe
The precise complexity of complementing B\"uchi\ automata is an intriguing and long standing problem. While optimal complementation techniques for finite automata are simple -- it suffices to determinize them using a simple subset construction and to dualize the acceptance condition of the resulting automaton -- B\"uchi\ complementation is more involved. Indeed, the construction of an EXPTIME complementation procedure took a quarter of a century from the introduction of B\"uchi\ automata in the early $60$s, and...

Strong Completeness of Coalgebraic Modal Logics

Lutz Schröder & Dirk Pattinson
Canonical models are of central importance in modal logic, in particular as they witness strong completeness and hence compactness. While the canonical model construction is well understood for Kripke semantics, non-normal modal logics often present subtle difficulties - up to the point that canonical models may fail to exist, as is the case e.g. in most probabilistic logics. Here, we present a generic canonical model construction in the semantic framework of coalgebraic modal logic, which...

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

Registration Year

  • 2009

Resource Types

  • Text