Holger Spakowski

SIGACT News, 2018

Team Diagonalization.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

CoRR, 2018

The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

2016

On Limited Nondeterminism and ACC Circuit Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2016

2012

Avoiding Simplicity is Complex.

[BibT_eX]

[DOI]

Eric Allender

Theory Comput. Syst., 2012

2009

Generalized juntas and NP-hard sets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Frequency of correctness versus average polynomial time.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

2008

Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas

[BibT_eX]

[DOI]

CoRR, 2008

2007

An improved exact algorithm for the domatic number problem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2007

On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

2006

LWPP and WPP are not uniformly gap-definable.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

Hierarchical Unambiguity.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

2005

The complexity of Kemeny elections.

[BibT_eX]

[DOI]

Edith Hemaspaandra

Theor. Comput. Sci., 2005

Completeness for parallel access to NP and counting class separation.

[BibT_eX]

[DOI]

Proceedings of the Ausgezeichnete Informatikdissertationen 2005, 2005

On the Power of Unambiguity in Alternating Machines.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

Completeness for parallel access to NP and counting class separations.

[BibT_eX]

[DOI]

PhD thesis, 2005

2004

Complexity of Cycle Length Modularity Problems in Graphs.

[BibT_eX]

[DOI]

Edith Hemaspaandra

Mayur Thakur

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Degree Bounds on Polynomials and Relativization Theory.

[BibT_eX]

[DOI]

Proceedings of the Exploring New Frontiers of Theoretical Informatics, 2004

2003

Exact Complexity of the Winner Problem for Young Elections.

[BibT_eX]

[DOI]

Jörg Rothe

Theory Comput. Syst., 2003

Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties.

[BibT_eX]

[DOI]

Mayur Thakur

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2002

Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.

[BibT_eX]

[DOI]

Edith Hemaspaandra

Jörg Rothe

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

Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections.

[BibT_eX]

[DOI]

Jörg Rothe

Proceedings of the Foundations of Information Technology in the Era of Networking and Mobile Computing, 2002

2000

Theta<sub>2</sub><sup>p</sup>-Completeness: A Classical Approach for New Results.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 2000

1999

The Operators minCh and maxCh on the Polynomial Hierarchy.

[BibT_eX]

[DOI]