List of Publications
Here are some further links to a database
containing also old technical reports and the complete publication list
of our group:
Jörg Rothe's publications
sorted by type of publication

sorted by year.
Publications of the Düsseldorf Computational Complexity and Cryptology group
sorted by type of publication

sorted by year.
Jörg Rothe's DBLP entry
(which is a bit hard to find due to the Umlaut in my name).
Books (authored, coauthored, edited, or coedited)

Economics and Computation. An Introduction to Algorithmic Game
Theory, Computational Social Choice, and Fair Division.

J. Rothe (editor and coauthor).
 Springer Texts in Business and Economics, SpringerVerlag,
Berlin, Heidelberg, xii+612 pp., 2015.
 Authors: J. Rothe (Chapters 1), P. Faliszewski, I. Rothe, and
J. Rothe (Chapter 2), E. Elkind and J. Rothe (Chapter 3),
D. Baumeister and J. Rothe (Chapter 4), E. Hemaspaandra,
L. Hemaspaandra, and J. Rothe (Chapter 5), D. Baumeister, G. Erdélyi,
and J. Rothe (Chapter 6), C. Lindner and J. Rothe (Chapter 7), J. Lang
and J. Rothe (Chapter 8).

Einführung in Computational Social Choice: Individuelle Strategien
und kollektive Entscheidungen beim Spielen, Wählen und Teilen.

J. Rothe,
D. Baumeister, C. Lindner, and I. Rothe.
 Spektrum Akademischer Verlag, Heidelberg, xii+375 pp., 2011.

Exakte Algorithmen für schwere Graphenprobleme.

F. Gurski, I. Rothe,
J. Rothe, and E. Wanke.
 eXamen.press, SpringerVerlag, Berlin, Heidelberg, xii+331 pp., 2010.

Proceedings of the Third International Workshop on Computational Social
Choice.

V. Conitzer and
J. Rothe (editors).
 Printed by Düsseldorf University Press.
University of Düsseldorf, Germany, viii+495 pp., September 2010.

Komplexitätstheorie und Kryptologie. Eine Einführung in Kryptokomplexität.

J. Rothe.
 eXamen.press, SpringerVerlag, Berlin, Heidelberg, xii+535 pp., 2008.

Complexity Theory and Cryptology. An Introduction to Cryptocomplexity.

J. Rothe.
 EATCS Texts in Theoretical Computer Science, SpringerVerlag,
Berlin, Heidelberg, xii+478 pp., 2005.
Refereed Journal Publications

The Complexity of Online Voter Control in Sequential Elections.

E. Hemaspaandra,
L. Hemaspaandra, and
J. Rothe.
 To appear in Journal of Autonomous Agents and MultiAgent
Systems.

Positional ScoringBased Allocation of Indivisible Goods.

D. Baumeister, S. Bouveret, J. Lang, N. Nguyen, T. Nguyen,
J. Rothe, and
A. Saffidine.
 To appear in Journal of Autonomous Agents and MultiAgent
Systems.

PathDisruption Games: Bribery and a Probabilistic Model.

A. Rey,
J. Rothe,
and
A. Marple.
 Theory of Computing Systems, vol. 60, no. 2, pp. 222252,
February 2017.

Toward the Complexity of the Existence of Wonderfully Stable
Partitions and Strictly Core Stable Coalition Structures in
EnemyOriented Hedonic Games.

A. Rey,
J. Rothe,
H. Schadrack, and
L. Schend.
 Annals of Mathematics and Artificial Intelligence, vol. 77,
no. 34, pp. 317333, August 2016.

A Statistical Approach to Calibrating the Scores of Biased
Reviewers of Scientific Papers.

W. Kuhlisch, M. Roos,
J. Rothe,
J. Rudolph, B. Scheuermann, and D. Stoyan.
 Metrika, vol. 79, no. 1, pp. 3757, January 2016.

Complexity of Manipulation, Bribery, and Campaign Management in
Bucklin and Fallback Voting.

P. Faliszewski,
Y. Reisch,
J. Rothe, and
L. Schend.
 Journal of Autonomous Agents and MultiAgent Systems,
vol. 29, no. 6, pp. 10911124, November 2015.

Complexity of Manipulation and Bribery in Judgment Aggregation for
Uniform PremiseBased Quota Rules.

D. Baumeister, G. Erdélyi, O. Erdélyi,
and
J. Rothe.
 Mathematical Social Sciences, vol. 76, pp. 1930, July
2015.

Control Complexity in Bucklin and Fallback Voting: An Experimental
Analysis.

G. Erdélyi, M. Fellows,
J. Rothe,
and L. Schend.
 Journal of Computer and System Sciences, vol. 81, no. 4,
pp. 661670, June 2015.

Control Complexity in Bucklin and Fallback Voting: A Theoretical
Analysis.

G. Erdélyi, M. Fellows,
J. Rothe,
and L. Schend.
 Journal of Computer and System Sciences, vol. 81, no. 4,
pp. 632660, June 2015.

Minimizing Envy and Maximizing Average Nash Social Welfare in
the Allocation of Indivisible Goods.

T. Nguyen and
J. Rothe.
 Discrete Applied Mathematics, vol. 179,
pp. 5468, December 2014.

FalseName
Manipulation in Weighted Voting Games is Hard for Probabilistic
Polynomial Time.

A. Rey and
J. Rothe.
 Journal of Artificial Intelligence Research, vol. 50,
pp. 573601, July 2014.

The Complexity of Online Manipulation of Sequential Elections.

E. Hemaspaandra,
L. Hemaspaandra,
and
J. Rothe.
 Journal of Computer and System Sciences, vol. 80,
no. 4, pp. 697710, June 2014.

Computational Complexity and Approximability of Social Welfare
Optimization in Multiagent Resource Allocation.

N. Nguyen, T. Nguyen, M. Roos, and
J. Rothe.
 Journal of Autonomous Agents and MultiAgent Systems, vol. 28,
no. 2, pp. 256289, March 2014.

The Complexity of Probabilistic Lobbying.

D. BinkeleRaible, G. Erdélyi, H. Fernau,
J. Goldsmith,
N. Mattei,
and
J. Rothe.
 Discrete Optimization, vol. 11,
no. 1, pp. 121, February 2014.

Challenges to Complexity Shields That Are Supposed to Protect
Elections Against Manipulation and Control: A Survey.

J. Rothe and
L. Schend.
 Annals of Mathematics and Artificial Intelligence, vol. 68,
no. 13, pp. 161193, MayJuly 2013.

A Survey of Approximability and Inapproximability Results for
Social Welfare Optimization in Multiagent Resource Allocation.

T. Nguyen, M. Roos, and
J. Rothe.
 Annals of Mathematics and Artificial Intelligence, vol. 68,
no. 13, pp. 6590, MayJuly 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. 467502, October 2013.

Taking the Final Step to a Full Dichotomy of the Possible Winner
Problem in Pure Scoring Rules.
 D. Baumeister
and
J. Rothe.

Information Processing Letters, vol. 112, no. 5,
pp. 186190, February 2012.

The Shield that Never Was: Societies with SinglePeaked
Preferences are More Open to Manipulation and Control.

P. Faliszewski,
E. Hemaspaandra,
L. Hemaspaandra,
and
J. Rothe.

Information and Computation, vol. 209, no. 2,
pp. 89107, February 2011.

Generalized Juntas and NPHard Sets.
 G. Erdélyi,
L. Hemaspaandra,
J. Rothe, and H. Spakowski.

Theoretical Computer Science, vol. 410, no. 3840,
pp. 39954000, September 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. 946949,
July 2009.

The ThreeColor and TwoColor Tantrix(TM) Rotation Puzzle Problems
are NPComplete via Parsimonious Reductions.
 D. Baumeister and J. Rothe.
 Information and Computation, vol. 207, no. 11, pp.
11191139, November 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.
275341, June 2009.

SincereStrategy PreferenceBased 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. 425443,
August 2009.

Hybrid Elections Broaden ComplexityTheoretic Resistance to Control.

E. Hemaspaandra,
L. Hemaspaandra,
and
J. Rothe.

Mathematical Logic Quarterly, vol. 55, no. 4, pp. 397424,
August 2009.
 Satisfiability Parsimoniously Reduces to the Tantrix(TM)
Rotation Puzzle Problem.

D. Baumeister and
J. Rothe.
 Fundamenta Informaticae, vol. 91, no. 1, pp. 3551, January
2009.

Enforcing and Defying Associativity, Commutativity,
Totality, and Strong Noninvertibility for OneWay Functions in
Complexity Theory.

L. Hemaspaandra,
J. Rothe, and
A. Saxena.
 Theoretical Computer Science,
vol. 401, no. 13, pp. 2735, July 2008.

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

Anyone but Him: The Complexity of Precluding an Alternative.
 E. Hemaspaandra,
L. Hemaspaandra,
and J. Rothe.
 Artificial Intelligence, vol. 171, no. 56, pp. 255285,
April 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. 101106, February 2007.

If P ≠ NP then Some Strongly Noninvertible Functions are
Invertible.

L. Hemaspaandra,
K. Pasanen, and
J. Rothe.
 Theoretical Computer Science,
vol. 362, no. 13, pp. 5462, October 2006.

On Computing the Smallest FourColoring of Planar Graphs and
NonSelfReducible Sets in P.
 A. Große,
J. Rothe, and
G. Wechsung.
 Information Processing Letters,
vol. 99, no. 6, pp. 215221, September 2006.

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. 635668, September 2006.

Completeness in the Boolean Hierarchy: ExactFourColorability,
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. 551578, May 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. 7591, January 2006.

Exact Complexity of ExactFourColorability.
 J. Rothe.
 Information Processing Letters, vol. 87, no. 1,
pp. 712, July 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. 375386, June 2003.

Some Facets of Complexity Theory and Cryptography:
A FiveLecture Tutorial.
 J. Rothe.
 ACM Computing Surveys, vol. 34,
no. 4, pp. 504549, December 2002.

On Characterizing the Existence of Partial OneWay Permutations.
 J. Rothe and
L. Hemaspaandra.
 Information Processing Letters, vol. 82, no. 3,
pp. 165171, May 2002.

Kryptographische Protokolle und NullInformation.
 J. Rothe.
 Informatik Spektrum, vol. 25, no. 2,
pp. 120131, April 2002.
In German.
 Appears also in:
Jahrbuch der HeinrichHeineUniversität
Düsseldorf 2001, pp. 183201, Düsseldorf, Germany, 2001.

Computing Complete Graph Isomorphisms and Hamiltonian Cycles from
Partial Ones.

A. Große,
J. Rothe, and
G. Wechsung.
 Theory of Computing Systems, vol. 35, no. 1,
pp. 8193, February 2002.

Characterizing the Existence of OneWay Permutations.

L. Hemaspaandra
and J. Rothe.
 Theoretical Computer Science, vol. 244, no. 12,
pp. 257261, August 2000.

A Second Step Towards ComplexityTheoretic Analogs of
Rice's Theorem.

L. Hemaspaandra
and J. Rothe.
 Theoretical Computer Science, vol. 244, no. 12,
pp. 205217, August 2000.

Tally NP Sets and Easy Census Functions.

J. Goldsmith,
M. Ogihara,
and J. Rothe.
 Information and Computation,
vol. 158, no. 1, pp. 2952, April 2000.

Restrictive Acceptance Suffices for Equivalence Problems.

B. Borchert,
L. Hemaspaandra,
and J. Rothe.
 London Mathematical Society Journal of Computation
and Mathematics, vol. 3, pp. 8695, March 2000.

Heuristics versus Completeness for Graph Coloring.
 J. Rothe.
 Chicago Journal of Theoretical Computer Science, vol. 2000,
article 1, 16 pages, February 2000.

Creating Strong, Total, Commutative, Associative OneWay
Functions from Any OneWay Function in Complexity Theory.

L. Hemaspaandra
and J. Rothe.
 Journal of Computer and System Sciences,
vol. 58, no. 3, pp. 648659, June 1999.

Immunity and Simplicity for Exact Counting and Other
Counting Classes.
 J. Rothe.
 R.A.I.R.O. Theoretical Informatics and Applications,
vol. 33, no. 2, pp. 159176, March/April 1999.

Boolean Operations, Joins, and the Extended Low Hierarchy.

L. Hemaspaandra,
Z. Jiang, J. Rothe, and
O. Watanabe.
 Theoretical Computer Science, vol. 205, no. 12,
pp. 317327, September 1998.

Recognizing When Greed Can Approximate Maximum Independent Sets is
Complete for Parallel Access to NP.
 E. Hemaspaandra and J. Rothe.
 Information Processing Letters, vol. 65, no. 3,
pp. 151156, February 1998.

Exact Analysis of Dodgson Elections: Lewis Carroll's 1876
Voting System is Complete for Parallel Access to NP.
 E. Hemaspaandra,
L. Hemaspaandra,
and J. Rothe.
 Journal of the Association for Computing Machinery, vol. 44,
no. 6, pp. 806825, November 1997.

Easy Sets and Hard Certificate Schemes.

L. Hemaspaandra,
J. Rothe, and
G. Wechsung.
 Acta Informatica, vol. 34, no. 11, pp. 859879, November 1997.

Unambiguous Computation: Boolean Hierarchies and Sparse
TuringComplete Sets.

L. Hemaspaandra
and J. Rothe.
 SIAM Journal on Computing, vol. 26, no. 3,
pp. 634653, June 1997.

PolynomialTime MultiSelectivity.

L. Hemaspaandra,
Z. Jiang, J. Rothe, and
O. Watanabe.
 Journal of Universal Computer Science, vol. 3, no. 3,
pp. 197229, March 1997.

Upward Separation for FewP and Related Classes.

R. Rao,
J. Rothe, and
O. Watanabe.
 Information Processing Letters, vol. 52, no. 4,
pp. 175180, November 1994.

Corrigendum
appears in the same journal,
vol. 74, no. 12, p. 89, April 2000.
 A Note on the PolynomialTime Hierarchy and Probabilistic
Operators.
 J. Rothe and J. Vogel.
 Computers and Artificial Intelligence, vol. 13, no. 1,
pp. 212, January 1994.
Refereed Publications in Conference Proceedings
 Complexity of Control by Partition of Voters and of Voter
Groups in Veto and Other Scoring Protocols.

C. Maushagen and
J. Rothe.
 To appear in the proceedings of the 16th International
Conference on Autonomous Agents and Multiagent Systems (AAMAS
2017), São Paulo, Brazil.
 IFAAMAS, May 2017.
 Approximate Solutions To MaxMin Fair and Proportionally
Fair Allocations of Indivisible Goods.

N. Nguyen, T. Nguyen and
J. Rothe.
 To appear in the proceedings of the 16th International
Conference on Autonomous Agents and Multiagent Systems (AAMAS
2017), São Paulo, Brazil.
 IFAAMAS, May 2017.

Solving Seven Open Problems of Offline and Online Control in Borda
Elections.

M. Neveling and
J. Rothe.
 Proceedings of the 31st AAAI Conference on
Artificial Intelligence (AAAI 2017), San Francisco, USA.
 AAAI Press, pages 30293035, February 2017.

Cost of Stability and Least Core in PathDisruption Games.

V. Persien, A. Rey und
J. Rothe.
 Proceedings of the 8th European Starting AI
Researcher Symposium (STAIRS 2016), The Hague, The Netherlands.
IOS Press, pages 99110, August/September 2016.

Complexity of Control by Partitioning Veto and Maximin
Elections and of Control by Adding Candidates to Plurality
Elections
 C. Maushagen and
J. Rothe.
 Proceedings of the 22nd European Conference on
Artificial Intelligence (ECAI 2016), The Hague, The Netherlands.
IOS Press, pages 277285, August/September 2016.
 A
preliminary version
appeared in the nonarchival website proceedings of the 14th
International Symposium on Artificial Intelligence and Mathematics
(ISAIM 2016), Fort Lauderdale, USA. January 2016.

Structural Control in Weighted Voting Games.
 A. Rey and
J. Rothe.
 Proceedings of the 41st International
Symposium on Mathematical Foundations of Computer Science
(MFCS 2016), Kraków, Poland.
 Schloss DagstuhlLeibnizZentrum für Informatik, LIPIcs, vol. 58,
pages 80:180:15, September 2016.
 An
extended abstract
appeared in the proceedings of the 15th International Conference
on Autonomous Agents and Multiagent Systems (AAMAS 2016),
Singapore, IFAAMAS, pages 13711372, May 2016.
 Also presented at the 7th International Workshop on Cooperative
Games in Multiagent Systems (CoopMAS 2016), colocated with AAMAS
2016, and at the 12th Conference on Logic and the Foundations of
Game and Decision Theory (LOFT 2016), Maastricht, The Netherlands,
July 2016, both with nonarchival proceedings.

Altruistic Hedonic Games.

N. Nguyen, A. Rey, L. Rey,
J. Rothe,
and L. Schend.
 Proceedings of the 15th International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2016), Singapore.
 IFAAMAS, pages 251259, May 2016.
 Also presented at the 7th International Workshop on Cooperative
Games in Multiagent Systems (CoopMAS 2016), colocated with AAMAS
2016, and at the
6th International Workshop on Computational Social Choice
(COMSOC 2016), Toulouse, France, June 2016, both with nonarchival
proceedings.

Local Fairness in Hedonic Games via Individual Threshold
Coalitions.

N. Nguyen and
J. Rothe.
 Proceedings of the 15th International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2016), Singapore.
 IFAAMAS, pages 232241, May 2016.
 Also presented at the 7th International Workshop on
Cooperative Games in Multiagent Systems (CoopMAS 2016), colocated
with AAMAS 2016, nonarchival proceedings.
 Verification in ArgumentIncomplete Argumentation Frameworks.

D. Baumeister,
J. Rothe, and
H. Schadrack.
 Proceedings of the 4th International Conference on Algorithmic
Decision Theory (ADT 2015), Lexington, USA.
 SpringerVerlag Lecture Notes in Artificial Intelligence
9346, pages 359376, September 2015.
 Appears also in the nonarchival proceedings of the
6th International Workshop on Computational Social Choice
(COMSOC 2016), Toulouse, France, June 2016.
 Complexity of Bribery and Control for Uniform PremiseBased
Quota Rules Under Various Preference Types.

D. Baumeister,
J. Rothe, and
A. Selker.
 Proceedings of the 4th International
Conference on Algorithmic Decision Theory (ADT 2015), Lexington,
USA.
 SpringerVerlag Lecture Notes in Artificial Intelligence
9346, pages 432448, September 2015.
 Verification in AttackIncomplete Argumentation Frameworks.

D. Baumeister, D. Neugebauer, and
J. Rothe.
 Proceedings of the 4th International
Conference on Algorithmic Decision Theory (ADT 2015), Lexington,
USA.
 SpringerVerlag Lecture Notes in Artificial Intelligence
9346, pages 341358, September 2015.
 Appears also in the nonarchival proceedings of the
6th International Workshop on Computational Social Choice
(COMSOC 2016), Toulouse, France, June 2016.
 Fairness and RankWeighted Utilitarianism in Resource
Allocation.

T. Heinen, N. Nguyen, and
J. Rothe.
 Proceedings of the 4th International
Conference on Algorithmic Decision Theory (ADT 2015), Lexington,
USA.
 SpringerVerlag Lecture Notes in Artificial Intelligence
9346, pages 521536, September 2015.

StrategyProofness of Scoring Allocation Correspondences for
Indivisible Goods.
 N. Nguyen, D. Baumeister,
and
J. Rothe.
 Proceedings of the
24th International Joint Conference on Artificial
Intelligence (IJCAI 2015), Buenos Aires, Argentina.
 AAAI Press/IJCAI, pages 11271133, July 2015.
 Appears also in the nonarchival proceedings of the
6th International Workshop on Computational Social Choice
(COMSOC 2016), Toulouse, France, June 2016.
 Representing and Solving Hedonic Games with Ordinal Preferences
and Thresholds.

J. Lang, A. Rey,
J. Rothe,
H. Schadrack, and L. Schend.
 Proceedings of the 14th International
Conference on Autonomous Agents and Multiagent Systems
(AAMAS 2015), Istanbul, Turkey.
 IFAAMAS, pages 12291237, May 2015.
 The Margin of Victory in Schulze, Cup, and Copeland
Elections: Complexity of the Regular and Exact Variants.

Y. Reisch,
J. Rothe, and
L. Schend.
 Proceedings of the 7th European Starting AI Researcher
Symposium (STAIRS 2014), Prague, Czech Republic. IOS Press, pages
250259, August 2014.
 Scoring Rules for the Allocation of Indivisible Goods.

D. Baumeister, S. Bouveret, J. Lang, N. Nguyen, T. Nguyen, and
J. Rothe.
 Proceedings of the 21st European Conference on Artificial
Intelligence (ECAI 2014), Prague, Czech Republic. IOS Press,
pages 7580, August 2014. (An extended version, jointly with
A. Saffidine, appears in the nonarchival 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.)

Toward the Complexity of the Existence of Wonderfully Stable
Partitions and Strictly Core Stable Coalition Structures in Hedonic
Games.

Anja Rey,
J. Rothe,
H. Schadrack, and L. Schend.
 Proceedings of the 11th Conference on Logic and the Foundations
of Game and Decision Theory (LOFT 2014), nonarchival proceedings.
Bergen, Norway, July 2014.
 Also invited for the nonarchival website proceedings of
the Special Session on Computational Social Choice at the 13th
International Symposium on Artificial Intelligence and Mathematics
(ISAIM 2014), Fort Lauderdale, USA. January 2014.
 Bribery in MultipleAdversary PathDisruption Games is Hard for
the Second Level of the Polynomial Hierarchy (Extended
Abstract).

A. Marple, A. Rey, and
J. Rothe.
 Proceedings of the 13th International
Conference on Autonomous Agents and Multiagent Systems
(AAMAS 2014), Paris, France.
 IFAAMAS, pages 13751376, May 2014.
 Complexity of Manipulation, Bribery, and Campaign Management in
Bucklin and Fallback Voting (Extended Abstract).

P. Faliszewski, Y. Reisch,
J. Rothe, and
L. Schend.
 Proceedings of the 13th International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2014), Paris, France.
 IFAAMAS, pages 13571358, May 2014.

FalseName Manipulation in Weighted Voting Games is Hard for
Probabilistic Polynomial Time.

Anja Rey and
J. Rothe.
 Proceedings of the 11th Latin American
Theoretical Informatics Symposium (LATIN 2014), Montevideo,
Uruguay.
 SpringerVerlag Lecture Notes in Computer Science 8392,
pages 6071, March/April 2014.
 Also presented at the 5th International Workshop on Cooperative
Games in Multiagent Systems (CoopMAS 2014), colocated with AAMAS
2014, nonarchival proceedings, Paris, France.
 Positional Scoring Rules for the Allocation of Indivisible
Goods.
 D. Baumeister, S. Bouveret, J. Lang, T. Nguyen,
J. Rothe, and A. Saffidine.
 Proceedings of the 11th European Workshop on
MultiAgent Systems (EUMAS 2013), Toulouse, France. December
2013.
 How to Decrease the Degree of Envy in Allocations of
Indivisible Goods.

T. Nguyen
and
J. Rothe.
 Proceedings of the 3rd International Conference on Algorithmic
Decision Theory (ADT 2013), Brussels, Belgium.
 SpringerVerlag Lecture Notes in Artificial Intelligence 8176,
pages 271284, November 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.
 SpringerVerlag Lecture Notes in Artificial Intelligence 8176,
pages 7185, November 2013.
 An extended version appears in the nonarchival 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
(ESSLLILMGD 2013), Düsseldorf, Germany, August 2013.
 EnvyRatio and AverageNash Social Welfare Optimization in
Multiagent Resource Allocation (Extended Abstract).

T. Nguyen and
J. Rothe.
 Proceedings of the 12th International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2013), St. Paul, USA.
 IFAAMAS, pages 11391140, May 2013.
 An extended version was presented at the 6th International
Workshop on Optimisation in MultiAgent Systems (OPTMAS 2013),
colocated with AAMAS 2013, nonarchival proceedings, pages 118.

The Complexity of Online Manipulation of Sequential Elections.

E. Hemaspaandra,
L. 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 111120, January 2013.
 A preliminary version appears in the nonarchival proceedings of
the 4th International Workshop on Computational Social Choice
(COMSOC 2012), F. Brandt and P. Faliszewski, editors, pages 227238.
AGH University of Science and Technology, Kraków, Poland, September
2012.

A Statistical Approach to Calibrating the Scores of Biased
Reviewers: The Linear vs. the Nonlinear Model.

M. Roos,
J. Rothe,
J. Rudolph,
D. Stoyan,
and
B. Scheuermann.
 Nonarchival website proceedings of the 6th Multidisciplinary
Workshop on Advances in Preference Handling (MPREF 2012),
Montpellier, France, August 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 2334, August 2012.
 A version combining this STAIRS 2012 paper with an ADT 2011 paper
appears as "Bribery and Control in Judgment Aggregation" in
the nonarchival proceedings of the 4th International Workshop on
Computational Social Choice (COMSOC 2012), F. Brandt and
P. Faliszewski, editors, pages 3748. AGH University of Science and
Technology, Kraków, Poland, September 2012.
 Complexity and Approximability of Egalitarian and Nash
Product Social Welfare Optimization in Multiagent Resource
Allocation.

N. Nguyen, T. Nguyen, M. Roos, and
and
J. Rothe.
 Proceedings of the 6th European Starting AI
Researcher Symposium (STAIRS 2012), Montpellier, France. IOS
Press, pages 204215, August 2012.
 Online Voter Control in 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 396401, August 2012.
 The Possible Winner Problem with Uncertain Weights.

D. Baumeister, M. Roos,
J. Rothe,
L. Schend, and L. Xia.
 Proceedings of the 20th European Conference on
Artificial Intelligence (ECAI 2012), Montpellier, France. IOS
Press, pages 133138, August 2012.
 An extended version appears in the nonarchival proceedings of the
4th International Workshop on Computational Social Choice
(COMSOC 2012), F. Brandt and P. Faliszewski, editors, pages 4960.
AGH University of Science and Technology, Kraków, Poland, September
2012.
 Controlling CandidateSequential Elections.

E. Hemaspaandra,
L. Hemaspaandra,
and
J. Rothe.
 Proceedings of the 20th European Conference on Artificial
Intelligence (ECAI 2012), Montpellier, France. IOS Press, pages
905906, August 2012.
 Probabilistic PathDisruption Games.

A. Rey
and
J. Rothe.
 Proceedings of the 20th European Conference on Artificial
Intelligence (ECAI 2012), Montpellier, France. IOS Press, pages
923924, August 2012.
 An extended version appears in the proceedings of the 6th
European Starting AI Researcher Symposium (STAIRS 2012),
Montpellier, France. IOS Press, pages 264269, August 2012.
 Control Complexity in Bucklin, Fallback, and Plurality Voting:
An Experimental Approach.

J. Rothe and L. Schend.
 Proceedings of the 11th International
Symposium on Experimental Algorithms (SEA 2012), Bordeaux, France.
 SpringerVerlag Lecture Notes in Computer Science 7276,
pages 356368, June 2012.
 Campaigns for Lazy Voters: Truncated Ballots.

D. Baumeister, P. Faliszewski, J. Lang, and
J. Rothe.
 Proceedings of the 11th International Conference on
Autonomous Agents and Multiagent Systems (AAMAS 2012), Valencia,
Spain.
 IFAAMAS, pages 577584, June 2012.
 Complexity and Approximability of Social Welfare Optimization in
Multiagent Resource Allocation (Extended Abstract).

N. Nguyen, T. Nguyen, M. Roos, and
J. Rothe.
 Proceedings of the 11th International Conference on
Autonomous Agents and Multiagent Systems (AAMAS 2012), Valencia,
Spain.
 IFAAMAS, pages 12871288, June 2012.
 An extended version appears in the nonarchival proceedings of the
4th International Workshop on Computational Social Choice
(COMSOC 2012), F. Brandt and P. Faliszewski, editors, pages 335346.
AGH University of Science and Technology, Kraków, Poland, September
2012.

Exact Optimization of Social Welfare by the Nash Product is DPComplete.

N. Nguyen, M. Roos, and
J. Rothe.
 Nonarchival website proceedings of the 12th International
Symposium on Artificial Intelligence and Mathematics (ISAIM 2012),
Fort Lauderdale, USA. January 2012.
 Bribery in PathDisruption Games.

A. Rey and
J. Rothe.
 Proceedings of the 2nd International
Conference on Algorithmic Decision Theory (ADT 2011),
DIMACS Center, Rutgers University, USA.
 SpringerVerlag Lecture Notes in Artificial Intelligence 6992,
pages 247261, October 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.
 SpringerVerlag Lecture Notes in Artificial Intelligence 6992,
pages 115, October 2011.

How to Calibrate the Scores of Biased Reviewers by Quadratic Programming.

M. Roos,
J. Rothe, and
B. Scheuermann.
 Proceedings of the 25th AAAI Conference on
Artificial Intelligence (AAAI 2011), San Francisco, USA.
 AAAI Press, pages 255260, August 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 837844, May 2011.
 Computational Complexity of Two Variants of the Possible Winner
Problem.

D. Baumeister, M. Roos, and
J. Rothe.
 Proceedings of the
10th International Conference on Autonomous Agents and
Multiagent Systems (AAMAS 2011), Taipei, Taiwan.
 IFAAMAS, pages 853860, May 2011.
 Merging and Splitting for Power Indices in Weighted Voting
Games and Network Flow Games on Hypergraphs.

A. Rey
and
J. Rothe.
 Proceedings of the 5th European Starting AI Researcher
Symposium (STAIRS 2010), Lisbon, Portugal. IOS Press, pages
277289, August 2010.
 Complexity of Merging and Splitting for the Probabilistic
Banzhaf Power Index in Weighted Voting Games.

A. Rey
and
J. Rothe.
 Proceedings of the 19th European Conference on
Artificial Intelligence (ECAI 2010), Lisbon, Portugal.
IOS Press, pages 10211022 (short paper), August 2010.
 Taking the Final Step to a Full Dichotomy of the Possible Winner
Problem in Pure Scoring Rules.

D. Baumeister
and
J. Rothe.
 Proceedings of the 19th European Conference on
Artificial Intelligence (ECAI 2010), Lisbon, Portugal.
IOS Press, pages 10191020 (short paper), August 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.
 SpringerVerlag Lecture Notes in Computer Science 6078,
pages 299310, May 2010.
 Complexity of Social Welfare Optimization in Multiagent
Resource Allocation.

M. Roos and
J. Rothe.
 Proceedings of the
9th International Conference on Autonomous Agents and
Multiagent Systems (AAMAS 2010), Toronto, Canada.
 IFAAMAS, pages 641648, May 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 3948, January 2010.
 Degrees of Guaranteed EnvyFreeness in Finite Bounded
CakeCutting Protocols.

C. Lindner and
J. Rothe.
 Proceedings of the 5th Workshop on Internet
& Network Economics (WINE 2009), Rome, Italy.
 SpringerVerlag Lecture Notes in Computer Science 5929,
pages 149159, December 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.
 SpringerVerlag Lecture Notes in Computer Science 5814,
pages 122134, October 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.
 SpringerVerlag Lecture Notes in Artificial Intelligence 5783,
pages 8697, October 2009.
 The Shield that Never Was: Societies with SinglePeaked
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, USA. ACM Digital Library, pages 118127, July 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 12891290, May 2009.
 SincereStrategy PreferenceBased 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.
 SpringerVerlag Lecture Notes in Computer Science 5162,
pages 311322, August 2008.
 An extended version appeared under the title
"SincereStrategy PreferenceBased Approval Voting Fully
Resists Constructive Control and Broadly Resists Destructive Control"
in the nonarchival proceedings of the
2nd International Workshop on Computational Social Choice
(COMSOC 2008), U. Endriss and P. Goldberg, editors,
pages 229240. University of Liverpool, UK, September 2008.

Copeland Voting Fully Resists Constructive Control.

P. Faliszewski,
E. Hemaspaandra,
L. Hemaspaandra,
and
J. Rothe.
 Proceedings of the 4th International Conference on
Algorithmic Aspects in Information and Management
(AAIM 2008), Shanghai, China.
 SpringerVerlag Lecture Notes in Computer Science 5034,
pages 165176, June 2008.
 The ThreeColor and TwoColor Tantrix(TM) Rotation Puzzle
Problems are NPComplete 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.
 SpringerVerlag Lecture Notes in Computer Science 5196,
pages 7687, March 2008.
 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.
 SpringerVerlag Lecture Notes in Computer Science 4664,
pages 134145, September 2007.
 On Approximating Optimal Weighted Lobbying, and Frequency of
Correctness versus AverageCase 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.
 SpringerVerlag Lecture Notes in Computer Science 4639,
pages 300311, August 2007.
 An earlier version by J. Rothe and H. Spakowski appeared under the
title "On Determining Dodgson Winners by Frequently SelfKnowingly
Correct Algorithms and in AverageCase Polynomial Time"
in the nonarchival proceedings of the
1st International Workshop on Computational Social Choice
(COMSOC 2006), U. Endriss and J. Lang,
editors, pages 464476. 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 724730, July 2007.
 A version merging the AAAI2007 and the AAIM2008 versions appeared
under the title "Llull and Copeland Voting Computationally Resist
Bribery and Control" in the nonarchival proceedings of the
2nd International Workshop on Computational Social Choice
(COMSOC 2008), U. Endriss and P. Goldberg, editors,
pages 241252. University of Liverpool, UK, September 2008.

Hybrid Elections Broaden ComplexityTheoretic 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 13081314, January 2007.
 Also appeared in the nonarchival proceedings of the
1st International Workshop on Computational Social Choice
(COMSOC 2006), U. Endriss and J. Lang, editors, pages 234247. ILLC,
University of Amsterdam, The Netherlands, December 2006.

An Improved Exact Algorithm for the Domatic Number Problem.
 T. Riege, J. Rothe, H. Spakowski, and
M. Yamamoto.
 Proceedings of the 2nd IEEE International
Conference on Information & Communication Technologies: From
Theory to Applications (ICTTA 2006), Damascus, Syria.
 IEEE Computer Society Press, pages 10211022, April 2006.
 Also presented at the
ICALP Affiliated Workshop for Improving ExponentialTime Algorithms
(iETA 2006), R. Niedermeier and O. Watanabe, editors, workshop notes,
pages 5358. Venice, Italy, July 2006.

Enforcing and Defying Associativity, Commutativity,
Totality, and Strong Noninvertibility for OneWay Functions in
Complexity Theory.

L. Hemaspaandra,
J. Rothe, and A. Saxena.
 Proceedings of the 9th Italian Conference on
Theoretical Computer Science (ICTCS 2005), Siena, Italy.
 SpringerVerlag Lecture Notes in Computer Science 3701,
pages 265279, 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.
 SpringerVerlag Lecture Notes in Computer Science 3618,
pages 733744, August 2005.

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

Complexity of the Exact Domatic Number Problem and of the Exact
Conveyor Flow Shop Problem.
 T. Riege and J. Rothe.
 Proceedings of the 1st IEEE International
Conference on Information & Communication Technologies: From
Theory to Applications (ICTTA 2004), Damascus, Syria.
 IEEE Computer Society Press, pages 653654, April 2004.
A sixpage extended abstract is available from CDROM ISBN 0780384830.

Exact Complexity of ExactFourColorability and of the Winner
Problem for Young Elections.
 J. Rothe, H. Spakowski, and J. Vogel.
 Proceedings of the 2nd IFIP International Conference on
Theoretical Computer Science (TCS 2002), which was held as Stream
1 of the 17th World Computer Congress (WCC 2002),
Montréal, Quebéc, Canada.
 Kluwer Academic Publishers, pages 310322, 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
GraphTheoretic Concepts in Computer Science (WG 2002),
Cesky Krumlov, Czech Republic.
 SpringerVerlag Lecture Notes in Computer Science 2573,
pages 258269, June 2002.
 Relating Partial and Complete Solutions and the Complexity of
Computing Smallest Solutions.

A. Große,
J. Rothe, and
G. Wechsung.
 Proceedings of the 7th International Italian Conference on
Theoretical Computer Science (ICTCS 2001),
Torino, Italy.
 SpringerVerlag Lecture Notes in Computer Science 2202,
pages 339356, October 2001.
 If P ≠ NP then Some Strongly Noninvertible Functions are
Invertible.

L. Hemaspaandra,
K. Pasanen, and J. Rothe.
 Proceedings of the 13th International Symposium on
Fundamentals of Computation Theory (FCT 2001),
Riga, Latvia.
 SpringerVerlag Lecture Notes in Computer Science 2138,
pages 162171, August 2001.
 Restrictive Acceptance Suffices for Equivalence Problems.

B. Borchert,
L. Hemaspaandra,
and J. Rothe.
 Proceedings of the 12th International Symposium on
Fundamentals of Computation Theory (FCT 1999),
Iasi, Romania.
 SpringerVerlag Lecture Notes in Computer Science 1684,
pages 124135, August/September 1999.
 Tally NP Sets and Easy Census Functions.

J. Goldsmith,
M. Ogihara,
and J. Rothe.
 Proceedings of the 23rd International Symposium on
Mathematical Foundations of Computer Science (MFCS 1998),
Brno, Czech Republic.
 SpringerVerlag Lecture Notes in Computer Science 1450,
pages 483492, August 1998.
 A Second Step Towards Circuit ComplexityTheoretic Analogs of
Rice's Theorem.

L. Hemaspaandra
and J. Rothe.
 Proceedings of the 23rd International Symposium on
Mathematical Foundations of Computer Science (MFCS 1998),
Brno, Czech Republic.
 SpringerVerlag Lecture Notes in Computer Science 1450,
pages 418426, August 1998.
 Immunity and Simplicity for Exact Counting and Other Counting
Classes.
 J. Rothe.
 Proceedings of the 9th International Conference on
Computing and Information (ICCI 1998), pages 279286,
Winnipeg, Manitoba, Canada, June 1998.
 Exact Analysis of Dodgson Elections: Lewis Carroll's 1876
Voting System is Complete for Parallel Access to NP.
 E. Hemaspaandra,
L. Hemaspaandra,
and J. Rothe.
 Proceedings of the 24th International Colloquium on
Automata, Languages, and Programming (ICALP 1997), Bologna, Italy.
 SpringerVerlag Lecture Notes in Computer Science 1256,
pages 214224, July 1997.
 On Sets with Easy Certificates and the Existence of OneWay
Permutations.

L. Hemaspaandra,
J. Rothe, and
G. Wechsung.
 Proceedings of the Third Italian Conference on
Algorithms and Complexity (CIAC 1997), Rome, Italy.
 SpringerVerlag Lecture Notes in Computer Science 1203,
pages 264275, March 1997.
 The Join Can Lower Complexity.

L. Hemaspaandra,
Z. Jiang, J. Rothe, and
O. Watanabe.
 Proceedings of the 2nd Annual International Computing
and Combinatorics Conference (COCOON 1996), Hong Kong.
 SpringerVerlag Lecture Notes in Computer Science 1090,
pages 260267, June 1996.
 Intersection Suffices for Boolean Hierarchy Equivalence.

L. Hemaspaandra
and J. Rothe.
 Proceedings of the 1st Annual International Computing
and Combinatorics Conference (COCOON 1995), Xi'an, China.
 SpringerVerlag Lecture Notes in Computer Science 959,
pages 430435, August 1995.

A Promise Class at Least as Hard as the Polynomial Hierarchy.
 J. Rothe.
 Proceedings of the 6th International Conference on
Computing and Information (ICCI 1994), pages 92107,
Peterborough, Ontario, Canada, May 1994.
Book Chapters

Control and Bribery in Voting.
 P. Faliszewski and
J. Rothe.
 Chapter 7 in "Handbook of Computational Social
Choice," pp. 146168, F. Brandt, V. Conitzer, U. Endriss,
J. Lang, and A. Procaccia (editors).
 Cambridge University Press, 2016.
 Password to open the pdf: cam1CSC

Computational Aspects of Approval Voting.
 D. Baumeister, G. Erdélyi,
E. Hemaspaandra,
L. Hemaspaandra, and J. Rothe.
 Chapter 10 in "Handbook on Approval Voting,"
pp. 199251, J. Laslier and R. Sanver, editors.
 SpringerVerlag, Berlin, Heidelberg, 2010.

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," pp. 375406,
S. Ravi and S. Shukla, editors.
 Springer, Berlin, Heidelberg, New
York, 2009.

Complexity Theory.
 J. Rothe.

Chapter 8 in "Algorithms of Informatics I,"
pp. 364392, A. Iványi, editor. Mondat Kiadó,
Budapest, 2007. English translation of
"Informatikai Algoritmusok I."

Cryptology.

J. Rothe.

Chapter 7 in "Algorithms of Informatics I," pp. 332363,
A. Iványi, editor. Mondat Kiadó, Budapest, 2007.
English translation of "Informatikai Algoritmusok I."

Bonyolultságelmélet.

J. Rothe.

Chapter 4 in "Informatikai Algoritmusok I,"
pp. 125160, A. Iványi, editor. ELTE Eötvös Kiadó,
Budapest, 2004. In Hungarian.

Kriptográfia.

J. Rothe.

Chapter 3 in "Informatikai Algoritmusok I,"
pp. 94124, A. Iványi, editor. ELTE Eötvös Kiadó,
Budapest, 2004. In Hungarian.
Invited Contributions to Journals, Conferences, Workshops, etc.

TypicalCase Challenges to Complexity Shields That Are Supposed to
Protect Elections Against Manipulation and Control: A Survey.
J. Rothe
and L. Schend.
 Nonarchival website proceedings of the Special Session on
Computational Social Choice at the 12th International Symposium on
Artificial Intelligence and Mathematics (ISAIM 2012), Fort
Lauderdale, USA. January 2012.

A Survey of Approximability and Inapproximability Results for Social
Welfare Optimization in Multiagent Resource Allocation.
T. Nguyen, M. Roos, and
J. Rothe.
 Nonarchival website proceedings of the Special Session on
Computational Social Choice at the 12th International Symposium on
Artificial Intelligence and Mathematics (ISAIM 2012), Fort
Lauderdale, USA. January 2012.

Introduction to Computational Complexity

M. Roos and
J. Rothe.
 Supplement in the
Mathematical Programming Glossary,
A. Holder, editor. INFORMS Computing Society, May 2010.

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

Review of "Complexity and Cryptography: An Introduction"
by John Talbot and Dominic Welsh, Cambridge University Press, 2006, 292 pages.

J. Rothe.

SIGACT News, vol. 38, no. 2, pp. 1620, June 2007.

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

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

Improving ExponentialTime Algorithms for NPComplete Problems.
 T. Riege and J. Rothe.
 Invited talk at the
ICALP Affiliated Workshop for Improving ExponentialTime Algorithms
(iETA 2006), R. Niedermeier and O. Watanabe, editors, workshop notes,
pages 6576. Venice, Italy, July 2006.

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 411432.
Baja, Hungary, November 2005.

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

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

Wechsung in Jena, H. Hempel, editor, Jena. Contributions to the
Festschrift for the 65th birthday of Gerd Wechsung:
 Appears also in:
Informatik Spektrum, vol. 27, no. 1,
pp. 7881, February 2004.

Complexity Theory and Cryptography.
 J. Rothe.
 Poster presented at the
8th GermanAmerican Frontiers of Science Symposium,
Irvine, California, USA, June 2002.

Course MC 5: "Some Facets of Complexity Theory and
Cryptography."
 J. Rothe.
 Invitation to be a Lecturer of the 11th Jyväskylä Summer School
at the University of Jyväskylä, Finland, in August, 2001.
 Lecture Notes appeared in revised form in the
ACM Computing Surveys, vol. 34, no. 4, pp. 504549, December 2002.

Kryptographische Protokolle und NullInformation.
 J. Rothe.
 Jahrbuch der HeinrichHeineUniversität
Düsseldorf 2001, pp. 183201, Düsseldorf, Germany, 2001.
In German.
 Appears also in:
Informatik Spektrum, vol. 25, no. 2,
pp. 120131, April 2002.

OneWay Functions in WorstCase Cryptography:
Algebraic and Security Properties are on the House.

A. Beygelzimer,
L. Hemaspaandra,
C. Homan,
and J. Rothe.

SIGACT News, vol. 30, no. 4, pp. 2540, December 1999.

Leichte und schwere Mengen in NP.
 J. Rothe.
 In: Komplexität, Graphen und Algorithmen,
J. Vogel, K. Wagner, Eds., pp. 7190, Würzburg, February 1999.
In German.

Raising NP Lower Bounds to Parallel NP Lower Bounds.
 E. Hemaspaandra,
L. Hemaspaandra,
and J. Rothe.

SIGACT News, vol. 28, no. 2, pp. 213, June 1997.

Easy Sets and Hard Certificate Schemes.

L. Hemaspaandra,
J. Rothe, and
G. Wechsung.
 Workshop on Computability, Complexity and Logic,
PreprintReihe Mathematik Nr. 11996, Universität Greifswald,
abstract p. 43, Zinnowitz, Germany, March 1996.
Additional Journal and Other Publications

Editorial of the Special Issue "Algorithms, Approximation, and
Empirical Studies in Behavioral and Computational Social
ChoicePreface."
 J. Goldsmith and J. Rothe.
 Annals of Mathematics and Artificial Intelligence,
vol. 68, no. 13, pp. 34, MayJuly 2013.

Editorial of the Special Issue "Logic and Complexity
within Computational Social Choice."
 P. Goldberg and J. Rothe.
 Mathematical Logic Quarterly,
vol. 55, no. 4, p. 340, August 2009.

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. 579580, June 2006.
 Preface of the editors.
J.UCS special issue on the First and Second JapaneseGerman
Frontiers of Science Symposia (JaGFoS).

Improving Deterministic and Randomized ExponentialTime 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. 725744, June 2006.
 In:
"Computational Challenges of Massive Data Sets and Randomness
in Computation," J. Rothe and H. Arimura, editors.
J.UCS special issue on the First and Second JapaneseGerman
Frontiers of Science Symposia (JaGFoS).
 On Some Promise Classes in Structural Complexity Theory.
 J. Rothe.
 Dissertation Summaries in Mathematics,
Khayyam Publishing Company (Athens, Ohio), vol. 1, no. 12,
pp. 323330, 1996.

A Promise Class at Least as Hard as the Polynomial Hierarchy.
 J. Rothe.
 Journal of Computing and Information, vol. 1, no. 1,
pp. 92107. CDROM ISSN 12018511, Trent University Press, April 1995.
Special Issue:
Proceedings of the 6th International Conference on Computing and
Information, May 1994.
OnLine Available Technical Reports since 2004

Complexity of Manipulation, Bribery, and Campaign Management in
Bucklin and Fallback Voting.

P. Faliszewski,
Y. Reisch,
J. Rothe, and Lena Schend.
 Technical Report arXiv:1307.7322v1 [cs.GT], ACM Computing Research
Repository (CoRR), 28 pages, July 2013.

FalseName Manipulation in Weighted Voting Games is Hard for
Probabilistic Polynomial Time.

Anja Rey and
J. Rothe.
 Technical Report arXiv:1303.1691v1 [cs.GT], ACM Computing Research
Repository (CoRR), 15 pages, March 2013.

Control Complexity in Bucklin, Fallback, and Plurality Voting: An
Experimental Approach.

J. Rothe
and L. Schend.
 Technical Report arXiv:1203.3967v2 [cs.GT], ACM Computing Research
Repository (CoRR), 370 pages, March 2012. Revised, August 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 Technical Report URCSTR2012976, University of
Rochester, Department of Computer Science, Rochester, NY, 14 pages,
March 2012.

The Complexity of Online Manipulation of Sequential Elections.

E. Hemaspaandra,
L. 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 Technical Report URCSTR2012974, University of
Rochester, Department of Computer Science, Rochester, NY, 24 pages,
February 2012. Revised, May, July, and September 2012.

Controlling CandidateSequential Elections.

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

Taking the Final Step to a Full Dichotomy of the Possible Winner Problem in Pure Scoring Rules.

D. Baumeister and
J. Rothe.
 Technical Report arXiv:1108.4436v2 [cs.CC], ACM Computing Research
Repository (CoRR), 9 pages, August 2011. Revised, November 2011.

Control Complexity in Bucklin and Fallback Voting.

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

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.

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.

The Shield that Never Was: Societies with SinglePeaked
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 Technical Report TR 950, University of Rochester,
Department of Computer Science, Rochester, NY, 38 pages, September 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.

The Complexity of Probabilistic Lobbying.

D. BinkeleRaible, 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.

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

Degrees of Guaranteed EnvyFreeness in Finite Bounded
CakeCutting Protocols.

C. Lindner and
J. Rothe.
 Technical Report arXiv:0902.0620v5 [cs.CC], ACM Computing Research
Repository (CoRR), 37 pages, February 2009. Revised, October 2009.

Frequency of Correctness versus AverageCase 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.

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

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 Technical Report TR 933, University of Rochester,
Department of Computer Science, Rochester, NY, 77 pages, April 2008.
Revised, September 2008.

The ThreeColor and TwoColor Tantrix(TM) Rotation
Puzzle Problems are NPComplete 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.

Copeland Voting Fully Resists Constructive Control.

P. Faliszewski, E. Hemaspaandra,
L. 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 Technical Report TR 923, University of Rochester,
Department of Computer Science, Rochester, NY, 15 pages, October 2007.

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.

On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus AverageCase 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 Technical Report TR 914, University of Rochester,
Department of Computer Science, Rochester, NY, March 2007.

Llull and Copeland Voting Broadly Resist Bribery and Control.

P. Faliszewski, E. Hemaspaandra,
L. Hemaspaandra,
and
J. Rothe.
 Technical Report TR 913, University of Rochester,
Department of Computer Science, Rochester, NY, 13 pages, February 2007.

A Richer Understanding of the Complexity of Election Systems.

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

Quantum Cryptography: A Survey.
 D. Bruss, G. Erdélyi, T. Meyer, T. Riege, and
J. Rothe.
 Technical Report TR05146, Electronic Colloquium on
Computational Complexity (ECCC), September 2006,
31 pages. Extends the December 2005 and March 2006 versions of TR05146.

Hybrid Elections Broaden ComplexityTheoretic 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 Technical Report TR 900, University of Rochester,
Department of Computer Science, Rochester, NY, June 2006.
Revised, August 2006 and September 2008.

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

Anyone But Him: The Complexity of Precluding an Alternative.

E. Hemaspaandra,
L. Hemaspaandra,
and
J. Rothe.
 Technical Report cs.GT/0507027v4, 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.

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

A Note on the Complexity of Computing the Smallest FourColoring of
Planar Graphs.

A. Große,
J. Rothe, and
G. Wechsung.
 Revises Technical Report cs.CC/0106045,
ACM Computing Research Repository (CoRR),
9 pages, February 2006.

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.

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

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.

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.
 T. Riege and
J. Rothe.
 Technical Report cs.CC/0212016v3, revised and extended version of
Technical Report cs.CC/0212016, ACM Computing Research Repository (CoRR),
37 pages, March 2004.
Habilitationsschrift

Complexity of Certificates, Heuristics, and Counting Types,
with Applications to Cryptography and Circuit Theory.
 J. Rothe.
 FriedrichSchillerUniversität Jena, Jena,
Germany, 159 pages, February 1999.

Komplexität von Zertifikaten, Heuristiken und Zähltypen
mit Anwendungen in der Kryptographie und Schaltkreistheorie.
 J. Rothe.
 Summary of the Habilitationsschrift.
Technical Report Math/Inf/99/7, FriedrichSchillerUniversität
Jena, Jena, Germany, 23 pages, February 1999. In German.
PhD Thesis

On Some Promise Classes in Structural Complexity Theory.
 J. Rothe.
 FriedrichSchillerUniversität Jena, Jena, Germany, 113 pages,
October 1995. Reviewed by U. Schöning in
Zentralblatt für Mathematik, SpringerVerlag.
Diploma Thesis

Die PolynomialzeitHierarchie und Probabilistische Operatoren.
 J. Rothe.
 FriedrichSchillerUniversität Jena, Jena, Germany, 65 pages,
September 1991. In German.