Leen Torenvliet

Falk Unger

Nikolai K. Vereshchagin

Algorithmica, 2019

A Hierarchy of Polynomial Kernels.

[BibT_eX]

[DOI]

Jouke Witteveen

Ralph Bottesch

Proceedings of the SOFSEM 2019: Theory and Practice of Computer Science, 2019

2017

Levelable Sets and the Algebraic Structure of Parameterizations.

[BibT_eX]

[DOI]

Jouke Witteveen

CoRR, 2017

2016

Fixed-parameter decidability: Extending parameterized complexity analysis.

[BibT_eX]

[DOI]

Jouke Witteveen

Math. Log. Q., 2016

2015

Hardness of Approximation for Knapsack Problems.

[BibT_eX]

[DOI]

Bruno Loff

Theory Comput. Syst., 2015

Discovering Motifs in Real-World Social Networks.

[BibT_eX]

[DOI]

Lotte B. Romijn

Breanndán Ó Nualláin

Proceedings of the SOFSEM 2015: Theory and Practice of Computer Science, 2015

2011

Nonapproximability of the normalized information distance.

[BibT_eX]

[DOI]

Sebastiaan A. Terwijn

Paul M. B. Vitányi

J. Comput. Syst. Sci., 2011

2010

Non-Uniform Reductions.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Normalized Information Distance is Not Semicomputable

[BibT_eX]

[DOI]

Sebastiaan Terwijn

Paul M. B. Vitányi

CoRR, 2010

2009

Nonapproximablity of the Normalized Information Distance

[BibT_eX]

[DOI]

Sebastiaan Terwijn

Paul M. B. Vitányi

CoRR, 2009

2008

The value of agreement a new boosting algorithm.

[BibT_eX]

[DOI]

Boaz Leskes

J. Comput. Syst. Sci., 2008

2006

Enumerations of the Kolmogorov function.

[BibT_eX]

[DOI]

J. Symb. Log., 2006

Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds.

[BibT_eX]

[DOI]

Falk Unger

Proceedings of the STACS 2006, 2006

P-Selectivity, Immunity, and the Power of One Bit.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2006: Theory and Practice of Computer Science, 2006

2005

A Post's Program for Complexity Theory.

[BibT_eX]

Bull. EATCS, 2005

2004

The importance of measurements for Internet policy.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Conference on Systems, 2004

Separating Complexity Classes Using Structural Properties.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Theory of Semi-Feasible Algorithms

[BibT_eX]

[DOI]

Monographs in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-662-05080-4, 2003

2001

The Communication Complexity of Enumeration, Elimination, and Selection.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

Two oracles that force a big crunch.

[BibT_eX]

[DOI]

Comput. Complex., 2001

2000

Randomness is Hard.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

Separating Complexity Classes Using Autoreducibility.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

1999

Complicated Complementations.

[BibT_eX]

[DOI]

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

Splittings, Robustness, and Structure of Complete Sets.

[BibT_eX]

[DOI]

Albrecht Hoene

SIAM J. Comput., 1998

Arithmetical Measure.

[BibT_eX]

[DOI]

Sebastiaan Terwijn

Math. Log. Q., 1998

1997

Six Hypotheses in Search of a Theorem.

[BibT_eX]

[DOI]

Lance Fortnow

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Optimal Advice.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

P-Selektive Self-Reducible Sets: A New Characterization of P.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

1995

A Note on the Complexity of Restricted Attribute-Value Grammars

[BibT_eX]

[DOI]

Marten Trautwein

CoRR, 1995

The Malleability of TSP_{2Opt}.

[BibT_eX]

[DOI]

Sophie Fischer

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1995

Witness-Isomorphic Reductions and the Local Search Problem (Extended Abstract).

[BibT_eX]

[DOI]

Sophie Fischer

Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

Using Autoreducibility to Separate Complexity Classes.

[BibT_eX]

[DOI]

Lance Fortnow

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Semi-membership algorithms: some recent advances.

[BibT_eX]

[DOI]

SIGACT News, 1994

On the Cutting Edge of Relativization: The Resource Bounded Injury Method.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

On the Structure of Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

Twenty Questions to a P-Selector.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1993

The Relative Power of Logspace and Polynomial Time Reductions.

[BibT_eX]

[DOI]

Edith Spaan

Comput. Complex., 1993

P-Selective Self-reducibles Sets: A New Characterization of <i>P</i>.

[BibT_eX]

[DOI]

Peter van Helden

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

Bounded Reductions.

[BibT_eX]

Edith Spaan

Proceedings of the Complexity Theory: Current Research, 1992

1991

Completeness for Nondeterministic Complexity Classes.

[BibT_eX]

[DOI]

Steven Homer

Math. Syst. Theory, 1991

1990

Generalized Kolmogorov Complexity in Relativized Separations (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

1989

Maintaining Multiple Representations of Dynamic Data Structures

[BibT_eX]

[DOI]

Inf. Comput., November, 1989

Simplicity, Immunity, Relativizations and Nondeterminism

[BibT_eX]

[DOI]

Inf. Comput., January, 1989

Two Models for the Reconstruction Problem for Dynamic Data Structures.

[BibT_eX]

J. Inf. Process. Cybern., 1989

Nondeterminism fairness and a fundamental analogy.

[BibT_eX]

Edith Spaan

Bull. EATCS, 1989

Multiple Representations of Dynamic Data Structures.

[BibT_eX]

Proceedings of the Information Processing 89, Proceedings of the IFIP 11th World Computer Congress, San Francisco, USA, August 28, 1989

1988

A Second Step Toward the Strong Polynomial-Time Hierarchy.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1988

1986

Diagonalisation methods in a polynomial setting.

[BibT_eX]

[DOI]

Proceedings of the Structure in Complexity Theory, 1986

1985

Combined Simplicity and Immunity in Relativized NP.

[BibT_eX]

[DOI]

Proceedings of the STACS 85, 1985

1983

The Reconstruction and Optimization of Trie Hashing Functions.

[BibT_eX]

[DOI]