Publications : CCC : Computational Complexity and Cryptology

Publications

2009

A Richer Understanding of the Complexity of Election Systems.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Chapter 14 in "Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz," S. Ravi and S. Shukla (editors), pp. 375-406. Springer, Berlin, Heidelberg, New York, 2009.

Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem.
D. Baumeister and J. Rothe.
Fundamenta Informaticae, vol. 91, no. 1, pp. 35-51, 2009.

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Mathematical Logic Quarterly, vol. 55, no. 4, pp. 397-424, August 2009.

Llull and Copeland Voting Computationally Resist Bribery and Constructive Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Journal of Artificial Intelligence Research, vol. 35, pp. 275-341, June 2009.

The Three-Color and Two-Color Tantrix(TM) Rotation Puzzle Problems are NP-Complete via Parsimonious Reductions.
D. Baumeister and J. Rothe.
Information and Computation, vol. 207, no. 11, pp. 1119-1139, November 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

Komplexitätstheorie und Kryptologie. Eine Einführung in Kryptokomplexität.
J. Rothe.
eXamen.press, Springer-Verlag, Berlin, Heidelberg, xii+535 pages, 2008.

Copeland Voting Fully Resists Constructive Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM 2008), Shanghai, China. Springer-Verlag Lecture Notes in Computer Science 5034, pages 165-176, June 2008.

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report cs.GT/0608057, ACM Computing Research Repository (CoRR), 53 pages, August 2006. Revised, September 2008.
Also appears as University of Rochester Computer Science Department Technical Report TR 900, Rochester, NY, 53 pages, June 2006. Revised, August 2006 and September 2008.

Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem.
D. Baumeister and J. Rothe.
Technical Report arXiv:0705.0915v2 [cs.CC], ACM Computing Research Repository (CoRR), 13 pages, May 2007. Revised, 19 pages, June 2008.

The Three-Color and Two-Color Tantrix(TM) Rotation Puzzle Problems are NP-Complete via Parsimonious Reductions.
D. Baumeister and J. Rothe.
Technical Report arXiv:0711.1827v3 [cs.CC], ACM Computing Research Repository (CoRR), 24 pages, November 2007. Revised, 30 pages, June 2008.

Llull and Copeland Voting Computationally Resist Bribery and Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report arXiV:0809.4484v2 [cs.GT], ACM Computing Research Repository (CoRR), 77 pages, September 2008.
Also appears as University of Rochester Computer Science Department Technical Report TR 933, Rochester, NY, 77 pages, April 2008. Revised, September 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.

Cryptology.
J. Rothe.
Chapter 7 in "Algorithms of Informatics I," A. Iványi (editor), pp. 332-363. Mondat Kiadó, Budapest, 2007. English translation of "Informatikai Algoritmusok I."

Complexity Theory.
J. Rothe.
Chapter 8 in "Algorithms of Informatics I," A. Iványi (editor), pp. 364-392. Mondat Kiadó, Budapest, 2007. English translation of "Informatikai Algoritmusok I."

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]

Anyone But Him: The Complexity of Precluding an Alternative.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Artificial Intelligence, vol. 171, no. 5-6, pp. 255-285, April 2007.

Quantum Cryptography: A Survey.
D. Bruß, G. Erdélyi, T. Meyer, T. Riege, and J. Rothe.
ACM Computing Surveys, vol. 39, no. 2, article 6, 27 pp., June 2007.

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), Hyderabad, India. AAAI Press, pages 1308-1314, January 2007.
Also appeared in the proceedings of the 1st International Workshop on Computational Social Choice (COMSOC 2006), U. Endriss and J. Lang, editors, pages 234-247. ILLC, University of Amsterdam, The Netherlands, December 2006.

Llull and Copeland Voting Broadly Resist Bribery and Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI 2007), Vancouver, Canada. AAAI Press, pages 724-730, July 2007.
A version merging the AAAI-2007 and the AAIM-2008 versions appeared under the title "Llull and Copeland Voting Computationally Resist Bribery and Control" in the proceedings of the 2nd International Workshop on Computational Social Choice (COMSOC 2008), U. Endriss and P. Goldberg, editors, pages 241-252. University of Liverpool, UK, September 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.
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]

Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem.
D. Baumeister and J. Rothe.
Proceedings of the 5th Conference on Machines, Computations and Universality (MCU 2007), Orléans, France. Springer-Verlag Lecture Notes in Computer Science 4664, pages 134-145, September 2007. [pdf]

Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory.
L. Hemaspaandra, J. Rothe, and A. Saxena.
Technical Report cs.CC/0503049, ACM Computing Research Repository (CoRR), March 2005. Revised in April 2005 and November 2007.
Also appears as TR 854, University of Rochester, Department of Computer Science, Rochester, NY, December 2004. Revised in April 2005 and November 2007.

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

Llull and Copeland Voting Broadly Resist Bribery and Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
University of Rochester Computer Science Department Technical Report TR 913, Rochester, NY, 13 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.

Copeland Voting Fully Resists Constructive Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report arXiv:0711.4759v2 [cs.GT], ACM Computing Research Repository (CoRR), 15 pages, November 2007. Revised, December 2007.
Also appears as University of Rochester Computer Science Department Technical Report TR 923, Rochester, NY, 15 pages, October 2007.

Complexity of the Tantrix(TM) Rotation Puzzle Problem.
D. Baumeister.
Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 54 pages, September 2007.

2006

On Computing the Smallest Four-Coloring of Planar Graphs and Non-Self-Reducible Sets in P.
A. Große, J. Rothe, and G. Wechsung.
Information Processing Letters, vol. 99, no. 6, pp. 215-221, September 2006. [pdf]

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.

Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems - a Survey.
T. Riege and J. Rothe.
Journal of Universal Computer Science, vol. 12, no. 5, pp. 551-578, May 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.

If P ≠ NP then Some Strongly Noninvertible Functions are Invertible.
L. Hemaspaandra, K. Pasanen, and J. Rothe.
Theoretical Computer Science, vol. 362, no. 1-3, pp. 54-62, October 2006. [pdf]

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.
T. Riege and J. Rothe.
Theory of Computing Systems, vol. 39, no. 5, pp. 635-668, September 2006. On-line publication DOI 10.1007/s00224-004-1209-8, December 2004. [pdf]

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.

Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.
T. Riege and J. Rothe.
Journal of Universal Computer Science, vol. 12, no. 6, pp. 725-744, June 2006.
Special issue: Computational Challenges of Massive Data Sets and Randomness in Computation, J. Rothe and H. Arimura, editors. Selected contributions from the First and Second Japanese-German Frontiers of Science Symposia (JaGFoS).

Computational Challenges of Massive Data Sets and Randomness in Computation.
J. Rothe and H. Arimura.
Journal of Universal Computer Science, vol. 12, no. 6, pp. 579-580, June 2006.
Preface of the Editors, J.UCS Special Issue on the First and Second Japanese-German Frontiers of Science Symposia.

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.

Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems.
T. Riege and J. Rothe.
Technical Report TR06-036, Electronic Colloquium on Computational Complexity (ECCC), 24 pages, March 2006.

A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs.
A. Große, J. Rothe, and G. Wechsung.
Technical Report cs.CC/0106045-v2, ACM Computing Research Repository (CoRR), 9 pages, February 2006.
Revises the June 2001 version of Technical Report cs.CC/0106045 (CoRR).

Anyone But Him: The Complexity of Precluding an Alternative.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report cs.GT/0507027-v4, ACM Computing Research Repository (CoRR), 33 pages, March 2006.
Also appears as TR 873, University of Rochester, Department of Computer Science, Rochester, NY, March 2006.

Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.
T. Riege and J. Rothe.
Technical Report TR06-078, Electronic Colloquium on Computational Complexity (ECCC), 16 pages, June 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.

Improving Exponential-Time Algorithms for NP-Complete Problems.
T. Riege and J. Rothe.
Invited talk at the ICALP Affiliated Workshop for Improving Exponential-Time Algorithms (iETA'06), R. Niedermeier and O. Watanabe, editors, workshop notes, pages 65-76. Venice, Italy, July 2006.

A Richer Understanding of the Complexity of Election Systems.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report cs.GT/0609112, ACM Computing Research Repository (CoRR), 33 pages, September 2006.
Also appears as TR 903, University of Rochester, Department of Computer Science, Rochester, NY, September 2006.

The Domatic Number Problem: Boolean Hierarchy Completeness and Exact Exponential-Time Algorithms.
T. Riege.
PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 109 pages, November 2006.

2005

Complexity Theory and Cryptology. An Introduction to Cryptocomplexity.
J. Rothe.
EATCS Texts in Theoretical Computer Science, Springer-Verlag, Berlin, Heidelberg, xii+478 pages, 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.

Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory.
L. Hemaspaandra, J. Rothe, and A. Saxena.
Proceedings of the Ninth Italian Conference on Theoretical Computer Science (ICTCS 2005), Siena, Italy. Springer-Verlag Lecture Notes in Computer Science 3701, pages 265-279, October 2005.

An Exact 2.9416^n Algorithm for the Three Domatic Number Problem.
T. Riege and J. Rothe.
Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), Gdansk, Poland. Springer-Verlag Lecture Notes in Computer Science 3618, pages 733-744, August 2005.

Anyone but Him: The Complexity of Precluding an Alternative.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Proceedings of the 20th National Conference on Artificial Intelligence (AAAI 2005), Pittsburgh, USA. AAAI Press, pages 95-101, July 2005.

Quantum Cryptography: A Survey.
D. Bruß, G. Erdélyi, T. Meyer, T. Riege, and J. Rothe.
Technical Report TR05-146, Electronic Colloquium on Computational Complexity (ECCC), 25 pages, March 2006.
Extends the December 2005 version of TR05-146 (ECCC).

An Exact 2.9416^n Algorithm for the Three Domatic Number Problem.
T. Riege and J. Rothe.
Technical Report cs.CC/0506090, ACM Computing Research Repository (CoRR), 20 pages, June 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.

The Complexity of Voting.
J. Rothe.
Invited talk at the Second International Conference of Applied Mathematics, D. Bainov and S. Nenov, editors, abstract pages 220-221. Plovdiv, Bulgaria, August 2005.

Quantenkryptographie.
G. Erdélyi, T. Riege, and J. Rothe.
Invited talk at the Kutatasok 2005 az Eötvös Jozsef Föiskolan, Steinerne Molnar Judit, editor, pages 411-432. Baja, Hungary, November 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

Kriptográfia.
J. Rothe.
Chapter 3 in "Informatikai Algoritmusok I," A. Iványi (editor), pp. 94-124. ELTE Eötvös Kiadó, Budapest, 2004. In Hungarian. [pdf]

Bonyolultságelmélet.
J. Rothe.
Chapter 4 in "Informatikai Algoritmusok I," A. Iványi (editor), pp. 125-160. ELTE Eötvös Kiadó, Budapest, 2004. In Hungarian. [pdf]

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.
T. Riege and J. Rothe.
Proceedings of the First IEEE International Conference on Information & Communication Technologies: From Theory to Applications (ICTTA 2004), Damascus, Syria. IEEE Computer Society Press, pages 653-654, April 2004. A six-page extended abstract is available from CD-ROM ISBN 0-7803-8483-0.

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 the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.
T. Riege and J. Rothe.
Technical Report cs.CC/0212016-v3,ACM Computing Research Repository (CoRR), 38 pages, March 2004.
Revises and extends the Technical Report cs.CC/0212016-v1, ACM Computing Research Repository (CoRR), 15 pages, December 2002.

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.

Exact-Four-Colorability, Exact Domatic Number Problems, and the Boolean Hierarchy.
J. Rothe.
Proceedings of the Dagstuhl Seminar 04421 "Algebraic Methods in Computational Complexity", 18 pp., October 2004.

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.

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.

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.