134 Works

On Nondeterministic Unranked Tree Automata with Sibling Constraints

Christof Löding & Karianto Wong
We continue the study of bottom-up unranked tree automata with equality and disequality constraints between direct subtrees. In particular, we show that the emptiness problem for the nondeterministic automata is decidable. In addition, we show that the universality problem, in contrast, is undecidable.

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

Kolmogorov Complexity in Randomness Extraction

John M. Hitchcock, Aduri Pavan & N. V. Vinodchandran
We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction and randomness extraction. We present a distribution ${\cal M}_k$ based on Kolmogorov complexity that is complete for randomness extraction in the sense that a computable...

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

Donation Center Location Problem

Chien-Chung Huang & Zoya Svitkina
We introduce and study the {\em donation center location} problem, which has an additional application in network testing and may also be of independent interest as a general graph-theoreticproblem.Given a set of agents and a set of centers, where agents have preferences over centers and centers have capacities, the goal is to open a subset of centers and to assign a maximum-sized subset of agents to their most-preferred open centers, while respecting the capacity constraints....

Approximating Fault-Tolerant Group-Steiner Problems

Rohit Khandekar, Guy Kortsarz & Zeev Nutov
In this paper, we initiate the study of designing approximation algorithms for {\sf Fault-Tolerant Group-Steiner} ({\sf FTGS}) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In {\sf Fault-Tolerant Group-Steiner} problems, we are given a graph with edge- (or vertex-) costs, a root vertex, and a collection of subsets of vertices called groups. The objective is to find a minimum-cost subgraph that has two edge- (or vertex-) disjoint paths...

Simulation based security in the applied pi calculus

Stéphanie Delaune, Steve Kremer & Olivier Pereira
We present a symbolic framework for refinement and composition of security protocols. The framework uses the notion of ideal functionalities. These are abstract systems which are secure by construction and which can be combined into larger systems. They can be separately refined in order to obtain concrete protocols implementing them. Our work builds on ideas from the ``trusted party paradigm'' used in computational cryptography models. The underlying language we use is the applied pi calculus...

Subexponential Algorithms for Partial Cover Problems

Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman & Saket Saurabh
Partial Cover problems are optimization versions of fundamental and well studied problems like {\sc Vertex Cover} and {\sc Dominating Set}. Here one is interested in covering (or dominating) the maximum number of edges (or vertices) using a given number ($k$) of vertices, rather than covering all edges (or vertices). In general graphs, these problems are hard for parameterized complexity classes when parameterized by $k$. It was recently shown by Amini et. al. [{\em FSTTCS 08}\,]...

Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf & Fabian Wagner
Graph isomorphism is an important and widely studied computational problem with a yet unsettled complexity. However, the exact complexity is known for isomorphism of various classes of graphs. Recently, \cite{DLNTW09} proved that planar isomorphism is complete for log-space. We extend this result %of \cite{DLNTW09} further to the classes of graphs which exclude $K_{3,3}$ or $K_5$ as a minor, and give a log-space algorithm. Our algorithm decomposes $K_{3,3}$ minor-free graphs into biconnected and those further into...

The Wadge Hierarchy of Max-Regular Languages

Jérémie Cabessa, Jacques Duparc, Alessandro Facchini & Filip Murlak
Recently, Miko{\l}aj Boja{\'n}czyk introduced a class of max-regular languages, an extension of regular languages of infinite words preserving manyof its usual properties. This new class can be seen as a different way of generalising the notion of regularity from finite to infinite words. This paper compares regular and max-regular languages in terms of topological complexity.It is proved that up to Wadge equivalence the classes coincide. Moreover, when restricted to $\mathbf{\Delta}^0_2$-languages, the classes contain virtually the...

Automata and temporal logic over arbitrary linear time

Julien Cristau
Linear temporal logic was introduced in order to reason about reactive systems. It is often considered with respect to infinite words, to specify the behaviour of long-running systems. One can consider more general models for linear time, using words indexed by arbitrary linear orderings. We investigate the connections between temporal logic and automata on linear orderings, as introduced by Bruyere and Carton. We provide a doubly exponential procedure to compute from any LTL formula with...

Domination Problems in Nowhere-Dense Classes

Anuj Dawar & Stephan Kreutzer
We investigate the parameterized complexity of generalisations and variations of the dominating set problem on classes of graphs that are nowhere dense. In particular, we show that the distance-$d$ dominating-set problem, also known as the $(k,d)$-centres problem, is fixed-parameter tractable on any class that is nowhere dense and closed under induced subgraphs. This generalises known results about the dominating set problem on $H$-minor free classes, classes with locally excluded minors and classes of graphs of...

Covering of ordinals

Laurent Braud
The paper focuses on the structure of fundamental sequences of ordinals smaller than $\e$. A first result is the construction of a monadic second-order formula identifying a given structure, whereas such a formula cannot exist for ordinals themselves. The structures are precisely classified in the pushdown hierarchy. Ordinals are also located in the hierarchy, and a direct presentation is given.

Fractional Pebbling and Thrifty Branching Programs

Mark Braverman, Stephen Cook, Pierre McKenzie, Rahul Santhanam & Dustin Wehr
We study the branching program complexity of the {\em tree evaluation problem}, introduced in \cite{BrCoMcSaWe09} as a candidate for separating \nl\ from\logcfl. The input to the problem is a rooted, balanced $d$-ary tree of height$h$, whose internal nodes are labelled with $d$-ary functions on$[k]=\{1,\ldots,k\}$, and whose leaves are labelled with elements of $[k]$.Each node obtains a value in $[k]$ equal to its $d$-ary function applied to the values of its $d$ children. The output is...

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

Arithmetic Circuits and the Hadamard Product of Polynomials

Vikraman Arvind, Pushkar S. Joglekar & Srikanth Srinivasan
Motivated by the Hadamard product of matrices we define the Hadamard product of multivariate polynomials and study its arithmetic circuit and branching program complexity. We also give applications and connections to polynomial identity testing. Our main results are the following. \begin{itemize} \item[$\bullet$] We show that noncommutative polynomial identity testing for algebraic branching programs over rationals is complete for the logspace counting class $\ceql$, and over fields of characteristic $p$ the problem is in $\ModpL/\Poly$. \item[$\bullet$]...

Continuous-Time Stochastic Games with Time-Bounded Reachability

Tomas Brazdil, Vojtech Forejt, Jan Krcal, Jan Kretinsky & Antonin Kucera
We study continuous-time stochastic games with time-bounded reachability objectives. We show that each vertex in such a game has a \emph{value} (i.e., an equilibrium probability), and we classify the conditions under which optimal strategies exist. Finally, we show how to compute optimal strategies in finite uniform games, and how to compute $\varepsilon$-optimal strategies in finitely-branching games with bounded rates (for finite games, we provide detailed complexity estimations).

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.

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

Mediating for Reduction (on Minimizing Alternating Büchi Automata)

Parosh A. Abdulla, Yu-Fang Chen, Lukas Holik & Tomas Vojnar
We propose a new approach for minimizing alternating B\"uchi automata (ABA). The approach is based on the so called \emph{mediated equivalence} on states of ABA, which is the maximal equivalence contained in the so called \emph{mediated preorder}. Two states $p$ and $q$ can be related by the mediated preorder if there is a~\emph{mediator} (mediating state) which forward simulates $p$ and backward simulates $q$. Under some further conditions, letting a computation on some word jump from...

Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata

Daniel Kirsten & Sylvain Lombardy
This paper solves the unambiguity and the sequentiality problem for polynomially ambiguous min-plus automata. This result is proved through a decidable algebraic characterization involving so-called metatransitions and an application of results from the structure theory of finite semigroups. It is noteworthy that the equivalence problem is known to be undecidable for polynomially ambiguous automata.

On Approximating Multi-Criteria TSP

Bodo Manthey
We present approximation algorithms for almost all variants of the multi-criteria traveling salesman problem (TSP), whose performances are independent of the number $k$ of criteria and come close to the approximation ratios obtained for TSP with a single objective function. We present randomized approximation algorithms for multi-criteria maximum traveling salesman problems (Max-TSP). For multi-criteria Max-STSP, where the edge weights have to be symmetric, we devise an algorithm that achieves an approximation ratio of $2/3 -...

Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time

Fabian Kuhn
We are given a set $V$ of autonomous agents (e.g.\ the computers of a distributed system) that are connected to each other by a graph $G=(V,E)$ (e.g.\ by a communication network connecting the agents). Assume that all agents have a unique ID between $1$ and $N$ for a parameter $N\ge|V|$ and that each agent knows its ID as well as the IDs of its neighbors in $G$. Based on this limited information, every agent $v$...

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

Optimal Cache-Aware Suffix Selection

Gianni Franceschini, Roberto Grossi & S. Muthukrishnan
Given string $S[1..N]$ and integer $k$, the {\em suffix selection} problem is to determine the $k$th lexicographically smallest amongst the suffixes $S[i\ldots N]$, $1 \leq i \leq N$. We study the suffix selection problem in the cache-aware model that captures two-level memory inherent in computing systems, for a \emph{cache} of limited size $M$ and block size $B$. The complexity of interest is the number of block transfers. We present an optimal suffix selection algorithm in...

Registration Year

  • 2009

Resource Types

  • Text