Publications

Sort by  |  Author

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.

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.

2008

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.

2007

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.

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]

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.
Technical Report cs.CC/0702047, ACM Computing Research Repository (CoRR), 40 pages, February 2007

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.

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]

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

2003

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 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]

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.

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.

2002

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.

2001

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.

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.

2000

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.

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.

1999

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.

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.

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.