Publications

Sort by  |  Author

Refereed Journal Publications

Generalized Juntas and NP-Hard Sets.
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Theoretical Computer Science, vol. 410, no. 38-40, pp. 3995-4000, September 2009.

Frequency of Correctness versus Average Polynomial Time.
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Information Processing Letters, vol. 109, no. 16, pp. 946-949, July 2009.

On the Power of Unambiguity in Alternating Machines.
H. Spakowski and R. Tripathi.
Theory of Computing Systems, vol. 41, no. 2, pp. 291-326, July 2007. [pdf]

An Improved Exact Algorithm for the Domatic Number Problem.
T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto.
Information Processing Letters, vol. 101, no. 3, pp. 101-106, February 2007.

LWPP and WPP are not Uniformly Gap-Definable.
H. Spakowski and R. Tripathi.
Journal of Computer and System Sciences, vol. 72, no. 4, pp. 660-689, June 2006.

Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.
E. Hemaspaandra, J. Rothe, and H. Spakowski.
R.A.I.R.O. Theoretical Informatics and Applications, vol. 40, no. 1, pp. 75-91, January 2006. [pdf]

The Complexity of Kemeny Elections.
E. Hemaspaandra, H. Spakowski, and J. Vogel.
Theoretical Computer Science, vol. 349, no. 3, pp. 382-391, December 2005.

Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties.
H. Spakowski, M. Thakur, and R. Tripathi.
Information and Computation, vol. 200, no. 1, pp. 1-34, July 2005.

Exact Complexity of the Winner Problem for Young Elections.
J. Rothe, H. Spakowski, and J. Vogel.
Theory of Computing Systems, vol. 36, no. 4, pp. 375-386, June 2003. [pdf]

Refereed Publications in Conference Proceedings

On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time.
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT 2007), Budapest, Hungary. Springer-Verlag Lecture Notes in Computer Science 4639, pages 300-311, August 2007.
An earlier version by J. Rothe and H. Spakowski appeared under the title "On Determining Dodgson Winners by Frequently Self-Knowingly Correct Algorithms and in Average-Case Polynomial Time" in the proceedings of the 1st International Workshop on Computational Social Choice (COMSOC 2006), U. Endriss and J. Lang, editors, pages 464-476. ILLC, University of Amsterdam, The Netherlands, December 2006. [pdf]

Hierarchical Unambiguity.
H. Spakowski and R. Tripathi.
Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), Stara Lesna, Slovakia. Springer-Verlag Lecture Notes in Computer Science 4162, pages 777-788, August/September 2006.

An Improved Exact Algorithm for the Domatic Number Problem.
T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto.
Proceedings of the Second IEEE International Conference on Information & Communication Technologies: From Theory to Applications (ICTTA 2006), Damascus, Syria. IEEE Computer Society Press, pages 1021-1022, April 2006.
Also presented at the ICALP Affiliated Workshop for Improving Exponential-Time Algorithms (iETA'06), R. Niedermeier and O. Watanabe, editors, workshop notes, pages 53-58. Venice, Italy, July 2006.

On the Power of Unambiguity in Alternating Machines.
H. Spakowski and R. Tripathi.
Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), Lübeck, Germany. Springer-Verlag Lecture Notes in Computer Science 3623, pages 125-136, August 2005.

Degree Bounds on Polynomials and Relativization Theory.
H. Spakowski and R. Tripathi.
Proceedings of the Third IFIP International Conference on Theoretical Computer Science (TCS 2004), Toulouse, France. Kluwer Academic Publishers, pages 97-110, August 2004.

Complexity of Cycle Length Modularity Problems in Graphs.
E. Hemaspaandra, H. Spakowski, and M. Thakur.
Proceedings of the Sixth Latin American Symposium on Theoretical Informatics (LATIN 2004), Buenos Aires, Argentina. Springer-Verlag Lecture Notes in Computer Science 2976, pages 509-518, April 2004.

Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties.
H. Spakowski, M. Thakur, and R. Tripathi.
Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2003), Mumbai, India. Springer-Verlag Lecture Notes in Computer Science 2914, pages 375-386, December 2003.

Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections.
J. Rothe, H. Spakowski, and J. Vogel.
Proceedings of the Second IFIP International Conference on Theoretical Computer Science (TCS 2002), which was held as Stream 1 of the 17th World Computer Congress, Montréal, Quebéc, Canada. Kluwer Academic Publishers, pages 310-322, August 2002.

Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.
E. Hemaspaandra, J. Rothe, and H. Spakowski.
Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2002), Cesky Krumlov, Czech Republic. Springer-Verlag Lecture Notes in Computer Science 2573, pages 258-269, June 2002.

The Complexity of Kemeny's Voting System.
H. Spakowski and J. Vogel.
Proceedings of the Argentinian Workshop on Theoretical Computer Science (WAIT 2001), Buenos Aires, Argentina, pages 157-168, September 2001.

Theta_2^p-Completeness: A Classical Approach for New Results.
H. Spakowski and J. Vogel.
Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2000), Delhi, India. Springer-Verlag Lecture Notes in Computer Science 1974, pages 348-360, December 2000.

The Operators minCh and maxCh on the Polynomial Hierarchy.
H. Spakowski and J. Vogel.
Proceedings of the Twelfth International Symposium on Fundamentals of Computation Theory (FCT 1999), Iasi, Romania. Springer-Verlag Lecture Notes in Computer Science 1684, pages 524-535, August 1999.

Additional Journal and Other Publication

Completeness for Parallel Access to NP and Counting Class Separations.
H. Spakowski.
In "Ausgezeichnete Informatikdissertationen 2005", D. Wagner et al., editors, Lecture Notes in Informatics, vol. D-6, pages 181-190, 2006.

Technical Reports

Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas.
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Technical Report arXiv:0806.2555v1 [cs.CC], ACM Computing Research Repository (CoRR), 20 pages, June 2008.
Also appears as University of Rochester Computer Science Department Technical Report TR 934, Rochester, NY, 20 pages, June 2008.

On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time.
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Technical Report cs.GT/0703097, ACM Computing Research Repository (CoRR), 21 pages, March 2007.
Also appears as University of Rochester Computer Science Department Technical Report TR 914, Rochester, NY, 21 pages, March 2007.

Hierarchical Unambiguity.
H. Spakowski and R. Tripathi.
Technical Report cs.CC/0702047, ACM Computing Research Repository (CoRR), 40 pages, February 2007

An Improved Exact Algorithm for the Domatic Number Problem.
T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto.
Technical Report cs.CC/0603060, ACM Computing Research Repository (CoRR), 9 pages, March 2006.

Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.
E. Hemaspaandra, J. Rothe, and H. Spakowski.
Technical Report cs.CC/0110025, ACM Computing Research Repository (CoRR), 16 pages, October 2001. Revised, January 2005.

On the Power of Unambiguity in Alternating Machines.
H. Spakowski and R. Tripathi.
Technical Report TR 851, University of Rochester, Department of Computer Science, Rochester, NY, October 2004. Revised in November 2005.

Degree Bounds on Polynomials and Relativization Theory.
H. Spakowski and R. Tripathi.
Technical Report TR 820, University of Rochester, Department of Computer Science, Rochester, NY, December 2003. Revised in March 2004. Revised in October 2004.

The Complexity of Kemeny Elections.
E. Hemaspaandra, H. Spakowski, and J. Vogel.
Friedrich-Schiller-Universität Jena Technical Report Math/Inf/14/03, 14 pages, October 2003.

Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties.
H. Spakowski, M. Thakur, and R. Tripathi.
Technical Report TR 801, University of Rochester, Department of Computer Science, Rochester, NY, June 2003. Modified in July 2003. Revised in October 2004.

Complexity of Cycle Length Modularity Problems.
E. Hemaspaandra, H. Spakowski, and M. Thakur.
Technical Report cs.CC/0306131, ACM Computing Research Repository (CoRR), June 2003.
Also appears as TR 802, University of Rochester, Department of Computer Science, Rochester, NY, June 2003.

Exact Complexity of the Winner Problem for Young Elections.
J. Rothe, H. Spakowski, and J. Vogel.
Technical Report cs.CC/0112021, ACM Computing Research Repository (CoRR), 10 pages, December 2001.

Toward a Theory of Completeness for Parallel Access to NP.
H. Spakowski and J. Vogel.
Friedrich-Schiller-Universität Jena Technical Report Math/Inf/00/19, 18 pages, July 2000.

The Complexity of Voting Schemes --- a Method for Proving Completeness for Parallel Access to NP.
H. Spakowski and J. Vogel.
Friedrich-Schiller-Universität Jena Technical Report Math/Inf/00/16, 21 pages, June 2000.

The Operators minCh and maxCh on the Polynomial Hierarchy.
H. Spakowski and J. Vogel.
Friedrich-Schiller-Universität Jena Technical Report Math/Inf/99/22, 19 pages, August 1999.

PhD Thesis

Completeness for Parallel Access to NP and Counting Class Separations.
H. Spakowski.
PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 105 pages, July 2005.

Diploma Thesis

Die Operatoren minCh und maxCh auf den Klassen der Polynomialzeithierarchie.
H. Spakowski.
Diploma Thesis. Institut für Informatik, Friedrich-Schiller-Universität Jena, Jena, Germany, 37 pages, 1999.