Holger Spakowski

Eric Allender, Holger Spakowski: Avoiding Simplicity is Complex. Theory Comput. Syst. 51(3): 282-296 (2012)

Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: Frequency of correctness versus average polynomial time. Inf. Process. Lett. 109(16): 946-949 (2009)

Holger Spakowski, Rahul Tripathi: Hierarchical Unambiguity. SIAM J. Comput. 38(5): 2079-2112 (2009)

Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: Generalized juntas and NP-hard sets. Theor. Comput. Sci. 410(38-40): 3995-4000 (2009)

Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas. CoRR abs/0806.2555 (2008)

Tobias Riege, Jörg Rothe, Holger Spakowski, Masaki Yamamoto: An improved exact algorithm for the domatic number problem. Inf. Process. Lett. 101(3): 101-106 (2007)

Holger Spakowski, Rahul Tripathi: On the Power of Unambiguity in Alternating Machines. Theory Comput. Syst. 41(2): 291-326 (2007)

Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: On Approximating Optimal Weighted Lobbying, and Frequency of Correctness Versus Average-Case Polynomial Time. FCT 2007: 300-311

Holger Spakowski, Rahul Tripathi: Hierarchical Unambiguity. CoRR abs/cs/0702047 (2007)

Gábor Erdélyi, Lane A. Hemaspaandra, Jörg Rothe, Holger Spakowski: On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time. CoRR abs/cs/0703097 (2007)

Edith Hemaspaandra, Jörg Rothe, Holger Spakowski: Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP. ITA 40(1): 75-91 (2006)

Holger Spakowski, Rahul Tripathi: LWPP and WPP are not uniformly gap-definable. J. Comput. Syst. Sci. 72(4): 660-689 (2006)

Holger Spakowski, Rahul Tripathi: Hierarchical Unambiguity. MFCS 2006: 777-788

Tobias Riege, Jörg Rothe, Holger Spakowski, Masaki Yamamoto: An Improved Exact Algorithm for the Domatic Number Problem. CoRR abs/cs/0603060 (2006)

Holger Spakowski: Completeness for parallel access to NP and counting class separations. Universität Düsseldorf 2005, pp. I-VI, 1-105

Holger Spakowski, Mayur Thakur, Rahul Tripathi: Quantum and classical complexity classes: Separations, collapses, and closure properties. Inf. Comput. 200(1): 1-34 (2005)

Edith Hemaspaandra, Holger Spakowski, Jörg Vogel: The complexity of Kemeny elections. Theor. Comput. Sci. 349(3): 382-391 (2005)

Holger Spakowski, Rahul Tripathi: On the Power of Unambiguity in Alternating Machines. FCT 2005: 125-136

Holger Spakowski, Rahul Tripathi: Degree Bounds on Polynomials and Relativization Theory. IFIP TCS 2004: 97-110

Edith Hemaspaandra, Holger Spakowski, Mayur Thakur: Complexity of Cycle Length Modularity Problems in Graphs. LATIN 2004: 509-518

Jörg Rothe, Holger Spakowski, Jörg Vogel: Exact Complexity of the Winner Problem for Young Elections. Theory Comput. Syst. 36(4): 375-386 (2003)

Holger Spakowski, Mayur Thakur, Rahul Tripathi: Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties. FSTTCS 2003: 375-386

Edith Hemaspaandra, Holger Spakowski, Mayur Thakur: Complexity of Cycle Length Modularity Problems in Graphs. CoRR cs.CC/0306131 (2003)

Jörg Rothe, Holger Spakowski, Jörg Vogel: Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections. IFIP TCS 2002: 310-322

Edith Hemaspaandra, Jörg Rothe, Holger Spakowski: Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP. WG 2002: 258-269

Edith Hemaspaandra, Jörg Rothe, Holger Spakowski: Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP. CoRR cs.CC/0110025 (2001)

Jörg Rothe, Holger Spakowski, Jörg Vogel: Exact Complexity of the Winner Problem for Young Elections. CoRR cs.CC/0112021 (2001)

Holger Spakowski, Jörg Vogel: Theta₂^p-Completeness: A Classical Approach for New Results. FSTTCS 2000: 348-360

Holger Spakowski, Jörg Vogel: The Operators minCh and maxCh on the Polynomial Hierarchy. FCT 1999: 524-535