Holger Spakowski

36 papers B 7C 1Journal 22Unranked 4
YearRankTypeTitle / Venue / Authors
2020 J jnl
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.
Comput. Complex.
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe
2018 J jnl
Column: Team Diagonalization.
SIGACT News
Lane A. Hemaspaandra, Holger Spakowski
2018 J jnl
Team Diagonalization.
CoRR
Lane A. Hemaspaandra, Holger Spakowski
2018 B conf
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.
MFCS
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe
2017 J jnl
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction.
CoRR
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe
2016 C conf
On Limited Nondeterminism and ACC Circuit Lower Bounds.
LATA
Holger Spakowski
2012 J jnl
Avoiding Simplicity is Complex.
Theory Comput. Syst.
Eric Allender, Holger Spakowski
2009 J jnl
Frequency of correctness versus average polynomial time.
Inf. Process. Lett.
Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski
2009 J jnl
Generalized juntas and NP-hard sets.
Theor. Comput. Sci.
Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski
2009 J jnl
Hierarchical Unambiguity.
SIAM J. Comput.
Holger Spakowski, Rahul Tripathi
2008 J jnl
Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas
CoRR
Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski
2007 J jnl
An improved exact algorithm for the domatic number problem.
Inf. Process. Lett.
Tobias Riege, Jörg Rothe, Holger Spakowski, Masaki Yamamoto
2007 J jnl
Hierarchical Unambiguity
CoRR
Holger Spakowski, Rahul Tripathi
2007 B conf
On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time.
FCT
Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski
2007 J jnl
On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time
CoRR
Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski
2007 J jnl
On the Power of Unambiguity in Alternating Machines.
Theory Comput. Syst.
Holger Spakowski, Rahul Tripathi
2006 J jnl
An Improved Exact Algorithm for the Domatic Number Problem
CoRR
Tobias Riege, Jörg Rothe, Holger Spakowski, Masaki Yamamoto
2006 B conf
Hierarchical Unambiguity.
MFCS
Holger Spakowski, Rahul Tripathi
2006 J jnl
LWPP and WPP are not uniformly gap-definable.
J. Comput. Syst. Sci.
Holger Spakowski, Rahul Tripathi
2006 J jnl
Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP.
RAIRO Theor. Informatics Appl.
Edith Hemaspaandra, Jörg Rothe, Holger Spakowski
2005 — ch.
Completeness for parallel access to NP and counting class separation.
Ausgezeichnete Informatikdissertationen
Holger Spakowski
2005 — —
Completeness for parallel access to NP and counting class separations.
Holger Spakowski
2005 B conf
On the Power of Unambiguity in Alternating Machines.
FCT
Holger Spakowski, Rahul Tripathi
2005 J jnl
Quantum and classical complexity classes: Separations, collapses, and closure properties.
Inf. Comput.
Holger Spakowski, Mayur Thakur, Rahul Tripathi
2005 J jnl
The complexity of Kemeny elections.
Theor. Comput. Sci.
Edith Hemaspaandra, Holger Spakowski, Jörg Vogel
2004 B conf
Complexity of Cycle Length Modularity Problems in Graphs.
LATIN
Edith Hemaspaandra, Holger Spakowski, Mayur Thakur
2004 — conf
Degree Bounds on Polynomials and Relativization Theory.
IFIP TCS
Holger Spakowski, Rahul Tripathi
2003 J jnl
Complexity of Cycle Length Modularity Problems in Graphs
CoRR
Edith Hemaspaandra, Holger Spakowski, Mayur Thakur
2003 J jnl
Exact Complexity of the Winner Problem for Young Elections.
Theory Comput. Syst.
Jörg Rothe, Holger Spakowski, Jörg Vogel
2003 — conf
Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties.
FSTTCS
Holger Spakowski, Mayur Thakur, Rahul Tripathi
2002 — conf
Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections.
IFIP TCS
Jörg Rothe, Holger Spakowski, Jörg Vogel
2002 B conf
Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.
WG
Edith Hemaspaandra, Jörg Rothe, Holger Spakowski
2001 J jnl
Exact Complexity of the Winner Problem for Young Elections
CoRR
Jörg Rothe, Holger Spakowski, Jörg Vogel
2001 J jnl
Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP
CoRR
Edith Hemaspaandra, Jörg Rothe, Holger Spakowski
2000 — conf
Theta
FSTTCS
Holger Spakowski, Jörg Vogel
1999 B conf
The Operators minCh and maxCh on the Polynomial Hierarchy.
FCT
Holger Spakowski, Jörg Vogel