Publications

Sort by  |  Author

To Appear

Control Complexity in Bucklin and Fallback Voting: A Theoretical Analysis.
G. Erdélyi, M. Fellows, J. Rothe, and L. Schend.
To appear in Journal of Computer and System Sciences.

Control Complexity in Bucklin and Fallback Voting: An Experimental Analysis.
G. Erdélyi, M. Fellows, J. Rothe, and L. Schend.
To appear in Journal of Computer and System Sciences.

2014

The Complexity of Probabilistic Lobbying.
D. Binkele-Raible, G. Erdélyi, H. Fernau, J. Goldsmith, N. Mattei, and J. Rothe.
Discrete Optimization, vol. 11, no. 1, pp. 1-21, February 2014.

2013

Computational Aspects of Manipulation and Control in Judgment Aggregation.
D. Baumeister, G. Erdélyi, O. Erdélyi, and J. Rothe.
Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT 2013), Brussels, Belgium. Springer-Verlag Lecture Notes in Artificial Intelligence 8176, pages 71-85, November 2013.
An extended version appears in the proceedings of the 5th International Workshop on Computational Social Choice (COMSOC 2014), A. Procaccia and T. Walsh, editors. Carnegie Mellon University, Pittsburgh, USA, June 2014. A preliminary version appeared in the nonarchival proceedings of the ESSLLI Workshop on Logical Models of Group Decision Making (ESSLLI-LMGD 2013), Düsseldorf, Germany, August 2013.

2012

Control in Judgment Aggregation.
D. Baumeister, G. Erdélyi, O. Erdélyi, and J. Rothe.
Proceedings of the 6th European Starting AI Researcher Symposium (STAIRS 2012), Montpellier, France. IOS Press, pages 23-34, August 2012.
A version combining this STAIRS 2012 paper with an ADT 2011 paper appears as "Bribery and Control in Judgment Aggregation" in the proceedings of the 4th International Workshop on Computational Social Choice (COMSOC 2012), F. Brandt and P. Faliszewski, editors, pages 37-48. AGH University of Science and Technology, Kraków, Poland, September 2012.

Control Complexity in Bucklin and Fallback Voting.
G. Erdélyi, M. Fellows, J. Rothe, and L. Schend.
Technical Report arXiv:1103.2230v2 [cs.CC], ACM Computing Research Repository (CoRR), 50 pages, March 2011. Revised, August 2012.

2011

The Complexity of Voter Partition in Bucklin and Fallback Voting: Solving Three Open Problems.
G. Erdélyi, L. Piras, and J. Rothe.
Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), Taipei, Taiwan. IFAAMAS, pages 837-844, May 2011.

How Hard is it to Bribe the Judges? A Study of the Complexity of Bribery in Judgment Aggregation.
D. Baumeister, G. Erdélyi, and J. Rothe.
Proceedings of the 2nd International Conference on Algorithmic Decision Theory (ADT 2011), DIMACS Center, Rutgers University, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 6992, pages 1-15, October 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, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Chapter 10 in "Handbook on Approval Voting," pp. 199-251, J. Laslier and R. Sanver, editors. Springer-Verlag, Berlin, Heidelberg, 2010.

Control Complexity in Fallback Voting.
G. Erdélyi and J. Rothe.
Proceedings of Computing: the 16th Australasian Theory Symposium (CATS 2010), Brisbane, Australia. Australian Computer Society, Conferences in Research and Practice in Information Technology Series, pages 39-48, January 2010.

Parameterized Control Complexity in Fallback Voting.
G. Erdélyi and M. Fellows.
Technical Report arXiv:1004.3659v1 [cs.CC], ACM Computing Research Repository (CoRR), 13 pages, April 2010.

Control Complexity in Fallback Voting.
G. Erdélyi, L. Piras, and J. Rothe.
Technical Report arXiv:1004.3398v1 [cs.GT], ACM Computing Research Repository (CoRR), 30 pages, April 2010.

Bucklin Voting is Broadly Resistant to Control.
G. Erdélyi, L. Piras, and J. Rothe.
Technical Report arXiv:1005.4115v1 [cs.GT], ACM Computing Research Repository (CoRR), 20 pages, May 2010.

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.

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

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 Control Complexity of Sincere-Strategy Preference-Based Approval Voting and of Fallback Voting, and a Study of Optimal Lobbying and Junta Distributions for SAT.
G. Erdélyi.
PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 103 pages, March 2009.

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.

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

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.

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]

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.

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

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.

2004

Quantenkryptographie.
G. Erdélyi.
Diploma Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 58 pages, April 2004.