Harald Hempel

Michael Krüger

Theor. Comput. Sci., 2012

2009

Aspects of Persistent Computations.

[BibT_eX]

[DOI]

Madlen Kimmritz

Int. J. Found. Comput. Sci., 2009

Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights.

[BibT_eX]

[DOI]

Tobias Berg

Proceedings of the Language and Automata Theory and Applications, 2009

2008

Persistent Computations of Turing Machines.

[BibT_eX]

[DOI]

Madlen Kimmritz

Proceedings of the Implementation and Applications of Automata, 2008

Inverse Problems Have Inverse Complexity.

[BibT_eX]

[DOI]

Tobias Berg

Proceedings of the Fifth IFIP International Conference On Theoretical Computer Science, 2008

Approximating Alternative Solutions.

[BibT_eX]

[DOI]

Michael Krüger

Proceedings of the Computing and Combinatorics, 14th Annual International Conference, 2008

2006

Randomized Algorithms and Complexity Theory.

[BibT_eX]

[DOI]

J. Univers. Comput. Sci., 2006

Inverse HAMILTONIAN CYCLE and Inverse 3-D MATCHING Are coNP-Complete.

[BibT_eX]

[DOI]

Michael Krüger

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

2005

All superlinear inverse schemes are coNP-hard.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Extending Downward Collapse from 1-versus-2 Queries to m-versus-m + 1 Queries.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

2004

Algebraic Properties for Selector Functions.

[BibT_eX]

[DOI]

Arfst Nickelsen

SIAM J. Comput., 2004

2003

P-immune sets with holes lack self-reducibility properties.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

On Functions and Relations.

[BibT_eX]

[DOI]

André Große

Proceedings of the Discrete Mathematics and Theoretical Computer Science, 2003

2002

Optimal Series-Parallel Trade-offs for Reducing a Function to Its Own Graph.

[BibT_eX]

[DOI]

Inf. Comput., 2002

On claw-free asteroidal triple-free graphs.

[BibT_eX]

[DOI]

Dieter Kratsch

Discret. Appl. Math., 2002

2001

Using the No-Search Easy-Hard Technique for Downward Collapse

[BibT_eX]

[DOI]

CoRR, 2001

Algebraic Properties for P-Selectivity.

[BibT_eX]

[DOI]

Arfst Nickelsen

Proceedings of the Computing and Combinatorics, 7th Annual International Conference, 2001

1999

Self-Specifying Machines.

[BibT_eX]

[DOI]

Gerd Wechsung

Int. J. Found. Comput. Sci., 1999

Translating Equality Downwards

[BibT_eX]

[DOI]

CoRR, 1999

R1-ttSN(NP) Distinguishes Robust Many-One and Turing Completeness

[BibT_eX]

[DOI]

CoRR, 1999

Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries.

[BibT_eX]

[DOI]

Proceedings of the STACS 99, 1999

1998

What's up with downward collapse: using the easy-hard technique to link Boolean and polynomial hierarchy collapses.

[BibT_eX]

[DOI]

SIGACT News, 1998

Query Order.

[BibT_eX]

[DOI]

Gerd Wechsung

SIAM J. Comput., 1998

A Downward Collapse within the Polynomial Hierarchy.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

RS N1-tt (NP) Distinguishes Robust Many-One and Turing Completeness.

[BibT_eX]

[DOI]

Theory Comput. Syst., 1998

Query Order and the Polynomial Hierarchy.

[BibT_eX]

[DOI]

J. Univers. Comput. Sci., 1998

Downward Collapse from a Weaker Hypothesis

[BibT_eX]

[DOI]

CoRR, 1998

Boolean hierarchies - on collapse properties and query order.

[BibT_eX]

[DOI]

PhD thesis, 1998

1997

The Operators min and max on the Polynomial Hierarchy

[BibT_eX]

[DOI]

Gerd Wechsung

Electron. Colloquium Comput. Complex., 1997

An Introduction to Query Order.

[BibT_eX]

Bull. EATCS, 1997

A Downward Translation in the Polynomial Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Query Order in the Polynomial Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 11th International Symposium, 1997

RSN1-tt(NP) Distinguishes Robust Many-One and Turing Completeness.

[BibT_eX]

[DOI]