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

__
TR12-150
| 1st November 2012
__

Michael Elberfeld, Christoph Stockhusen, Till Tantau#### On the Space Complexity of Parameterized Problems

Revisions: 1

__
TR11-128
| 21st September 2011
__

Michael Elberfeld, Andreas Jakoby, Till Tantau#### Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth

__
TR10-062
| 7th April 2010
__

Michael Elberfeld, Andreas Jakoby, Till Tantau#### Logspace Versions of the Theorems of Bodlaender and Courcelle

__
TR08-027
| 4th December 2007
__

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

__
TR07-039
| 27th March 2007
__

Bodo Manthey, Till Tantau#### Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise

Revisions: 1

__
TR06-035
| 19th January 2006
__

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

__
TR04-028
| 19th March 2004
__

Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker#### Aggregates with Component Size One Characterize Polynomial Space

__
TR03-077
| 4th September 2003
__

Till Tantau#### Logspace Optimisation Problems and their Approximation Properties

__
TR03-024
| 25th February 2003
__

Till Tantau#### Weak Cardinality Theorems for First-Order Logic

__
TR02-004
| 2nd November 2001
__

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

__
TR01-092
| 2nd October 2001
__

Till Tantau#### A Note on the Complexity of the Reachability Problem for Tournaments

__
TR00-077
| 24th August 2000
__

Till Tantau#### On the Power of Extra Queries to Selective Languages

Revisions: 1

Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau

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

Michael Elberfeld, Christoph Stockhusen, Till Tantau

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

Michael Elberfeld, Andreas Jakoby, Till Tantau

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

Michael Elberfeld, Andreas Jakoby, Till Tantau

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

Till Tantau

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

Bodo Manthey, Till Tantau

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

Till Tantau

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

Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker

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

Till Tantau

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

Till Tantau

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

Till Tantau

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

Till Tantau

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

Till Tantau

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