Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Till Tantau:

TR19-146 | 31st October 2019
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau

Dynamic Kernels for Hitting Sets and Set Packing

Computing kernels for the hitting set problem (the problem of
finding a size-$k$ set that intersects each hyperedge of a
hypergraph) is a well-studied computational problem. For hypergraphs
with $m$ hyperedges, each of size at most~$d$, the best algorithms
can compute kernels of size $O(k^d)$ in ... more >>>

TR12-150 | 1st November 2012
Michael Elberfeld, Christoph Stockhusen, Till Tantau

On the Space Complexity of Parameterized Problems

Revisions: 1

Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. ... more >>>

TR11-128 | 21st September 2011
Michael Elberfeld, Andreas Jakoby, Till Tantau

Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth

An algorithmic meta theorem for a logic and a class $C$ of structures states that all problems expressible in this logic can be solved efficiently for inputs from $C$. The prime example is Courcelle's Theorem, which states that monadic second-order (MSO) definable problems are linear-time solvable on graphs of bounded ... more >>>

TR10-062 | 7th April 2010
Michael Elberfeld, Andreas Jakoby, Till Tantau

Logspace Versions of the Theorems of Bodlaender and Courcelle

Bodlaender's Theorem states that for every $k$ there is a linear-time algorithm that decides whether an input graph has tree width~$k$ and, if so, computes a width-$k$ tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula $\phi$ and for
every $k$ there is ... more >>>

TR08-027 | 4th December 2007
Till Tantau

Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets

The Hartmanis--Immerman--Sewelson theorem is the classical link between the exponential and the polynomial time realm. It states that NE = E if, and only if, every sparse set in NP lies in P. We establish similar links for classes other than sparse sets:

1. E = UE if, and only ... more >>>

TR07-039 | 27th March 2007
Bodo Manthey, Till Tantau

Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise

Revisions: 1

Binary search trees are a fundamental data structure and their height
plays a key role in the analysis of divide-and-conquer algorithms like
quicksort. Their worst-case height is linear; their average height,
whose exact value is one of the best-studied problems in average-case
complexity, is logarithmic. We analyze their smoothed height ... more >>>

TR06-035 | 19th January 2006
Till Tantau

The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters

The reachability problem for graphs cannot be described, in the
sense of descriptive complexity theory, using a single first-order
formula. This is true both for directed and undirected graphs, both
in the finite and infinite. However, if we restrict ourselves to
graphs in which a certain graph parameter is fixed ... more >>>

TR04-028 | 19th March 2004
Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker

Aggregates with Component Size One Characterize Polynomial Space

Aggregates are a computational model similar to circuits, but the
underlying graph is not necessarily acyclic. Logspace-uniform
polynomial-size aggregates decide exactly the languages in PSPACE;
without uniformity condition they decide the languages in
PSPACE/poly. As a measure of similarity to boolean circuits we
introduce the parameter component size. We ... more >>>

TR03-077 | 4th September 2003
Till Tantau

Logspace Optimisation Problems and their Approximation Properties

This paper introduces logspace optimisation problems as
analogues of the well-studied polynomial-time optimisation
problems. Similarly to them, logspace
optimisation problems can have vastly different approximation
properties, even though the underlying existence and budget problems
have the same computational complexity. Numerous natural problems
are presented that exhibit such a varying ... more >>>

TR03-024 | 25th February 2003
Till Tantau

Weak Cardinality Theorems for First-Order Logic

Kummer's cardinality theorem states that a language is recursive
if a Turing machine can exclude for any n words one of the
n + 1 possibilities for the number of words in the language. It
is known that this theorem does not hold for polynomial-time
computations, but there ... more >>>

TR02-004 | 2nd November 2001
Till Tantau

A Note on the Power of Extra Queries to Membership Comparable Sets

A language is called k-membership comparable if there exists a
polynomial-time algorithm that excludes for any k words one of
the 2^k possibilities for their characteristic string.
It is known that all membership comparable languages can be
reduced to some P-selective language with polynomially many
adaptive queries. We show however ... more >>>

TR01-092 | 2nd October 2001
Till Tantau

A Note on the Complexity of the Reachability Problem for Tournaments

Deciding whether a vertex in a graph is reachable from another
vertex has been studied intensively in complexity theory and is
well understood. For common types of graphs like directed graphs,
undirected graphs, dags or trees it takes a (possibly
nondeterministic) logspace machine to decide the reachability
problem, and ... more >>>

TR00-077 | 24th August 2000
Till Tantau

On the Power of Extra Queries to Selective Languages

Revisions: 1

A language is \emph{selective} if there exists a
selection algorithm for it. Such an algorithm selects
from any two words one, which is an element of the
language whenever at least one of them is.
Restricting the complexity of selection algorithms
yields different \emph{selectivity classes} ... more >>>

ISSN 1433-8092 | Imprint