Publications

Sort by  |  Author

2013

The Complexity of Online Manipulation of Sequential Elections.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2013), Chennai, India. Available at arXiv:1310.6997 [cs.GT], ACM Computing Research Repository (CoRR), pages 111-120, January 2013.
A preliminary version appears in the proceedings of the 4th International Workshop on Computational Social Choice (COMSOC 2012), F. Brandt and P. Faliszewski, editors, pages 227-238. AGH University of Science and Technology, Kraków, Poland, September, 2012.

2012

Controlling Candidate-Sequential Elections.
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012), Montpellier, France. IOS Press, pages 905-906, August 2012.

Online Voter Control in Sequential Elections.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012), Montpellier, France. IOS Press, pages 396-401, August 2012.

Controlling Candidate-Sequential Elections.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report arXiv:1202.6649v1 [cs.GT], ACM Computing Research Repository (CoRR), 6 pages, February 2012.
Also appears as University of Rochester Computer Science Department Technical Report URCS-TR-2012-975, Rochester, NY, 6 pages, February 2012.

The Complexity of Online Manipulation of Sequential Elections.
L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Technical Report arXiv:1202.6655v4 [cs.GT], ACM Computing Research Repository (CoRR), 24 pages, February 2012. Revised, May, July, and September 2012.
Also appears as University of Rochester Computer Science Department Technical Report URCS-TR-2012-974, Rochester, NY, 24 pages, February 2012. Revised, May, July, and September 2012.

Online Voter Control in Sequential Elections.
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Technical Report arXiv:1203.0411v1 [cs.GT], ACM Computing Research Repository (CoRR), 14 pages, March 2012.
Also appears as University of Rochester Computer Science Department Technical Report URCS-TR-2012-976, Rochester, NY, 14 pages, March 2012.

2011

The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Information and Computation, vol. 209, no. 2, pp. 89-107, February 2011.

2010

Computational Aspects of Approval Voting.
D. Baumeister, G. Erdélyi, L. Hemaspaandra, E. 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.

2009

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

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 Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control.
P. Faliszewski, L. Hemaspaandra, E. 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.

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 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.
Technical Report arXiv:0909.3257v2 [cs.GT], ACM Computing Research Repository (CoRR), 38 pages, September 2009. Revised, June 2010.
Also appears as University of Rochester Computer Science Department Technical Report TR 950, Rochester, NY, 38 pages, September 2009.

2008

Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory.
L. Hemaspaandra, J. Rothe, and A. Saxena.
Theoretical Computer Science, vol. 401, no. 1-3, pp. 27-35, July 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.
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.

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

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

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.