Publications : CCC : Computational Complexity and Cryptology

Publications

2013

The Complexity of Computing Minimal Unidirectional Covering Sets.
D. Baumeister, F. Brandt, F. Fischer, J. Hoffmann, and J. Rothe.
Theory of Computing Systems, vol. 53, no. 3, pp. 467-502, October 2013.

2011

The Complexity of Probabilistic Lobbying.
D. Binkele-Raible, G. Erdélyi, H. Fernau, J. Goldsmith, N. Mattei, and J. Rothe.
Technical Report arXiv:0906.4431v4 [cs.CC], ACM Computing Research Repository (CoRR), 35 pages, June 2009. Revised, February 2011.

2010

Computational Aspects of Approval Voting.
D. Baumeister, G. Erdélyi, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Chapter 10 in "Handbook on Approval Voting," J. Laslier and R. Sanver (editors), pp. 199-251. Springer-Verlag, Berlin, Heidelberg, 2010.

The Complexity of Computing Minimal Unidirectional Covering Sets.
D. Baumeister, F. Brandt, F. Fischer, J. Hoffmann, and J. Rothe.
Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC 2010), Rome, Italy. Springer-Verlag Lecture Notes in Computer Science 6078, pages 299-310, May 2010.

2009

A Richer Understanding of the Complexity of Election Systems.
P. Faliszewski, E. Hemaspaandra, L. 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.

Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control.
G. Erdélyi, M. Nowak, and J. Rothe.
Mathematical Logic Quarterly, vol. 55, no. 4, pp. 425-443, August 2009.

Llull and Copeland Voting Computationally Resist Bribery and Constructive Control.
P. Faliszewski, E. Hemaspaandra, L. 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.

The Cost of Stability in Weighted Voting Games (Extended Abstract).
Y. Bachrach, R. Meir, M. Zuckerman, J. Rothe, and J. Rosenschein.
Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary. IFAAMAS, pages 1289-1290, May 2009.

The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control.
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2009), Stanford University, Palo Alto, CA, USA. ACM Digital Library, pages 118-127, July 2009.

The Complexity of Probabilistic Lobbying.
G. Erdélyi, H. Fernau, J. Goldsmith, N. Mattei, D. Raible, and J. Rothe.
Proceedings of the 1st International Conference on Algorithmic Decision Theory (ADT 2009), Venice, Italy. Springer-Verlag Lecture Notes in Artificial Intelligence 5783, pages 86-97, October 2009.

The Cost of Stability in Coalitional Games.
Y. Bachrach, E. Elkind, R. Meir, D. Pasechnik, M. Zuckerman, J. Rothe, and J. Rosenschein.
Proceedings of the 2nd International Symposium on Algorithmic Game Theory (SAGT 2009), Paphos, Cyprus. Springer-Verlag Lecture Notes in Computer Science 5814, pages 122-134, October 2009.

Degrees of Guaranteed Envy-Freeness in Finite Bounded Cake-Cutting Protocols.
C. Lindner and J. Rothe.
Proceedings of the 5th Workshop on Internet & Network Economics (WINE 2009), Rome, Italy. Springer-Verlag Lecture Notes in Computer Science 5929, pages 149-159, December 2009.

Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control.
G. Erdélyi, M. Nowak, and J. Rothe.
Technical Report arXiv:0806.0535v5 [cs.GT], ACM Computing Research Repository (CoRR), 26 pages, June 2008. Revised, September 2008 and June 2009.

Computational Aspects of Approval Voting.
D. Baumeister, G. Erdélyi, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report 944, University of Rochester, Computer Science Department, Rochester, NY, 61 pages, May 2009.

The Cost of Stability in Coalitional Games.
Y. Bachrach, E. Elkind, R. Meir, D. Pasechnik, M. Zuckerman, J. Rothe, and J. Rosenschein.
Technical Report arXiv:0907.4385 [cs.GT], ACM Computing Research Repository (CoRR), 20 pages, July 2009.

The Complexity of Computing Minimal Unidirectional Covering Sets.
D. Baumeister, F. Brandt, F. Fischer, J. Hoffmann, and J. Rothe.
Technical Report arXiv:0901.3692v3 [cs.CC], ACM Computing Research Repository (CoRR), 27 pages, July 2009.
Supersedes the Technical Report "Deciding Membership in Minimal Upward Covering Sets is Hard for Parallel Access to NP" coauthored by D. Baumeister, F. Brandt, F. Fischer, and J. Rothe, arXiv:0901.3692v2 [cs.CC], ACM Computing Research Repository (CoRR), 14 pages, April 2009.

2008

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

The Three-Color and Two-Color Tantrix(TM) Rotation Puzzle Problems are NP-Complete via Parsimonious Reductions.
D. Baumeister and J. Rothe.
Proceedings of the 2nd International Conference on Language and Automata Theory and Applications (LATA 2008), Tarragona, Spain. Springer-Verlag Lecture Notes in Computer Science 5196, pages 76-87, March 2008.
Preproceedings, pages 89-100, Technical Report, Rovira i Virgili University, Tarragona, Spain, 2008. [pdf]

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.

Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control.
G. Erdélyi, M. Nowak, and J. Rothe.
Proceedings of the 33rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), Torun, Poland. Springer-Verlag Lecture Notes in Computer Science 5162, pages 311-322, August 2008.
An extended version appeared under the title "Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control" in the proceedings of the 2nd International Workshop on Computational Social Choice (COMSOC 2008), U. Endriss and P. Goldberg, editors, pages 229-240. University of Liverpool, UK, September 2008.

Computational Complexity for Social Choice Theorists.
J. Rothe.
Invited tutorial at the 2nd International Workshop on Computational Social Choice (COMSOC'08), Liverpool, United Kingdom, September 2008.

Computational Foundations of Social Choice: A Complexity-Theoretic Perspective.
J. Rothe.
Invited talk at the ESF LogICCC Launch Conference, Prague, Czech Republic, October 2008.

Fixed-Parameter Tractability and Parameterized Complexity Applied to Problems From Computational Social Choice.
C. Lindner and J. Rothe.
Supplement in the Mathematical Programming Glossary, A. Holder, editor. INFORMS Computing Society, October 2008.

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.
E. Hemaspaandra, L. 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, E. Hemaspaandra, L. 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

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."

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

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.
E. Hemaspaandra, L. 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, E. Hemaspaandra, L. 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.

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.

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]

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.

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.