| Publication | Date of Publication | Type |
|---|
The malleability of TSP 2Opt
Graph-Theoretic Concepts in Computer Science | 2024-02-28 | Paper |
A hierarchy of polynomial kernels
(available as arXiv preprint) | 2020-10-22 | Paper |
| A hierarchy of polynomial kernels | 2020-10-22 | Paper |
On the cutting edge of relativization: The resource bounded injury method
Automata, Languages and Programming | 2019-04-29 | Paper |
Sparse selfreducible sets and nonuniform lower bounds
Algorithmica | 2019-01-11 | Paper |
Fixed-parameter decidability: extending parameterized complexity analysis
Mathematical Logic Quarterly | 2017-02-01 | Paper |
Hardness of approximation for knapsack problems
Theory of Computing Systems | 2015-05-29 | Paper |
Nonapproximability of the normalized information distance
Journal of Computer and System Sciences | 2011-04-28 | Paper |
Non-uniform reductions
Theory of Computing Systems | 2010-10-06 | Paper |
Witness-isomorphic reductions and the local search problem (extended abstract)
Lecture Notes in Computer Science | 2010-06-17 | Paper |
| A Post's program for complexity theory. | 2009-09-19 | Paper |
The value of agreement a new boosting algorithm
Journal of Computer and System Sciences | 2008-06-10 | Paper |
Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds
STACS 2006 | 2008-03-19 | Paper |
SOFSEM 2006: Theory and Practice of Computer Science
Lecture Notes in Computer Science | 2006-11-14 | Paper |
Enumerations of the Kolmogorov function
Journal of Symbolic Logic | 2006-08-03 | Paper |
| scientific article; zbMATH DE number 1993590 (Why is no real title available?) | 2003-10-21 | Paper |
Two oracles that force a big crunch
Computational Complexity | 2002-05-05 | Paper |
The communication complexity of enumeration, elimination, and selection
Journal of Computer and System Sciences | 2002-04-11 | Paper |
Theory of semi-feasible algorithms
Monographs in Theoretical Computer Science. An EATCS Series | 2002-04-01 | Paper |
Randomness is hard
SIAM Journal on Computing | 2001-03-19 | Paper |
| scientific article; zbMATH DE number 1335898 (Why is no real title available?) | 2000-05-14 | Paper |
| scientific article; zbMATH DE number 1306884 (Why is no real title available?) | 2000-04-26 | Paper |
Separating Complexity Classes Using Autoreducibility
SIAM Journal on Computing | 2000-03-19 | Paper |
| scientific article; zbMATH DE number 1222922 (Why is no real title available?) | 1999-10-10 | Paper |
Arithmetical Measure
Mathematical Logic Quarterly | 1998-11-01 | Paper |
Splittings, Robustness, and Structure of Complete Sets
SIAM Journal on Computing | 1998-05-10 | Paper |
| scientific article; zbMATH DE number 1048042 (Why is no real title available?) | 1997-09-22 | Paper |
\(p\)-selective self-reducible sets: a new characterization of P
Journal of Computer and System Sciences | 1997-03-31 | Paper |
Optimal advice
Theoretical Computer Science | 1997-02-28 | Paper |
| scientific article; zbMATH DE number 512826 (Why is no real title available?) | 1994-04-07 | Paper |
| scientific article; zbMATH DE number 512801 (Why is no real title available?) | 1994-03-10 | Paper |
The relative power of logspace and polynomial time reductions
Computational Complexity | 1994-01-19 | Paper |
| scientific article; zbMATH DE number 176522 (Why is no real title available?) | 1993-05-18 | Paper |
Completeness for nondeterministic complexity classes
Mathematical Systems Theory | 1992-06-26 | Paper |
| scientific article; zbMATH DE number 18632 (Why is no real title available?) | 1992-06-26 | Paper |
| scientific article; zbMATH DE number 4113964 (Why is no real title available?) | 1989-01-01 | Paper |
Maintaining multiple representations of dynamic data structures
Information and Computation | 1989-01-01 | Paper |
Simplicity, immunity, relativizations and nondeterminism
Information and Computation | 1989-01-01 | Paper |
A second step toward the strong polynomial-time hierarchy
Mathematical Systems Theory | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 3988707 (Why is no real title available?) | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3974294 (Why is no real title available?) | 1985-01-01 | Paper |
