Holger Spakowski

According to our database, Holger Spakowski authored at least 24 papers between 1999 and 2020.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2020

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

Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe

Comput. Complex., 2020

2018

Column: Team Diagonalization.

Lane A. Hemaspaandra, Holger Spakowski

SIGACT News, 2018

Team Diagonalization.

Lane A. Hemaspaandra, Holger Spakowski

CoRR, 2018

2016

On Limited Nondeterminism and ACC Circuit Lower Bounds.

Holger Spakowski

Proceedings of the Language and Automata Theory and Applications, 2016

2012

Avoiding Simplicity is Complex.

Eric Allender, Holger Spakowski

Theory Comput. Syst., 2012

2009

Generalized juntas and NP-hard sets.

Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski

Theor. Comput. Sci., 2009

Hierarchical Unambiguity.

Holger Spakowski, Rahul Tripathi

SIAM J. Comput., 2009

Frequency of correctness versus average polynomial time.

Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski

Inf. Process. Lett., 2009

2008

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

Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski

CoRR, 2008

2007

On the Power of Unambiguity in Alternating Machines.

Holger Spakowski, Rahul Tripathi

Theory Comput. Syst., 2007

An improved exact algorithm for the domatic number problem.

Tobias Riege, Jörg Rothe, Holger Spakowski, Masaki Yamamoto

Inf. Process. Lett., 2007

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

Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski

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

2006

LWPP and WPP are not uniformly gap-definable.

Holger Spakowski, Rahul Tripathi

J. Comput. Syst. Sci., 2006

Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP.

Edith Hemaspaandra, Jörg Rothe, Holger Spakowski

RAIRO Theor. Informatics Appl., 2006

2005

The complexity of Kemeny elections.

Edith Hemaspaandra, Holger Spakowski, Jörg Vogel

Theor. Comput. Sci., 2005

Quantum and classical complexity classes: Separations, collapses, and closure properties.

Holger Spakowski, Mayur Thakur, Rahul Tripathi

Inf. Comput., 2005

Completeness for parallel access to NP and counting class separation.

Holger Spakowski

Proceedings of the Ausgezeichnete Informatikdissertationen 2005, 2005

Completeness for parallel access to NP and counting class separations.

Holger Spakowski

PhD thesis, 2005

2004

Complexity of Cycle Length Modularity Problems in Graphs.

Edith Hemaspaandra, Holger Spakowski, Mayur Thakur

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

Degree Bounds on Polynomials and Relativization Theory.

Holger Spakowski, Rahul Tripathi

Proceedings of the Exploring New Frontiers of Theoretical Informatics, 2004

2003

Exact Complexity of the Winner Problem for Young Elections.

Jörg Rothe, Holger Spakowski, Jörg Vogel

Theory Comput. Syst., 2003

2002

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

Jörg Rothe, Holger Spakowski, Jörg Vogel

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

2000

Theta₂^p-Completeness: A Classical Approach for New Results.

Holger Spakowski, Jörg Vogel

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

1999

The Operators minCh and maxCh on the Polynomial Hierarchy.

Holger Spakowski, Jörg Vogel

Proceedings of the Fundamentals of Computation Theory, 12th International Symposium, 1999