## Publications

### To Appear

How Can We Model Emotional and Behavioral Dynamics in Collective Decision Making?

J. Rothe.

Chapter to appear in The Future of Economic Design, J. Laslier, H. Moulin, R. Sanver, W. Zwicker (editors). Series: Studies in Economic Design. Springer, 2018.

The Price to Pay for Forgoing Normalization in Fair Division of Indivisible Goods.

P. Lange and J. Rothe.

To appear in Annals of Mathematics and Artificial Intelligence.

How Hard Is the Manipulative Design of Scoring Systems?

D. Baumeister and T. Hogrebe.

To appear in the proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019), Macao, China. AAAI Press/IJCAI, August 2019.

Deciding Acceptance in Incomplete Argumentation Frameworks.

A. Niskanen, D. Neugebauer, M. Järvisalo and J. Rothe.

To appear in the proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), New York, NY, USA.
AAAI Press, February 2020.

Complexity of Verification in Abtract Argumentation Frameworks.

D. Baumeister.

To appear in SIGACT News.

### 2019

Duplication Monotonicity in the Allocation of Indivisible Goods.

B. Kuckuck and J. Rothe.

AI Communications, vol. 32, no. 4, pp. 253-270, October 2019.

Borda Count in Collective Decision Making: A Summary of Recent Results.

J. Rothe.

Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019), Honolulu, Hawaii, USA. AAAI Press, pages 9830-9836, January/February 2019.

Stability in FEN-Hedonic Games for Single-Player Deviations.

A. Kerkmann and J. Rothe.

Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), Montréal, Canada. IFAAMAS, pages 891-899, May 2019.

The Complexity of Online Bribery in Sequential Elections.

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

Proceedings of the 17th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2019), Toulouse, France. Electronic Proceedings in Theoretical Computer
Science 297, pages 233-251, July 2019.

Manipulative Design of Scoring Systems (Extended Abstract).

D. Baumeister and T. Hogrebe.

Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), Montréal, Canada. IFAAMAS, pages 1814-1816, May 2019.

Complexity of Distances in Elections (Doctoral Consortium).

T. Hogrebe.

Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), Montréal, Canada. IFAAMAS, pages 2414-2416, May 2019.

Refugee Allocation in the Setting of Hedonic Games.

B. Kuckuck, J. Rothe, and A. Weißenfeld.

Proceedings of the 6th International Conference on Algorithmic Decision Theory (ADT 2019), Duke University,
Durham, NC, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 11834, pages 65-80, October 2019.

Optimizing Social Welfare in Social Networks.

P. Lange and J. Rothe.

Proceedings of the 6th International Conference on Algorithmic Decision Theory (ADT 2019), Duke University, Durham, NC, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 11834, pages 81-96, October 2019.

Generalized Distance Bribery.

D. Baumeister, T. Hogrebe, and L. Rey.

Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019), Honolulu, Hawaii, USA. AAAI Press, pages 1764-1771, January/February 2019.

Stabilität in FEN-hedonischen Spielen.

A. Kerkmann.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 53 pages, March 2019.

### 2018

Strategy-Proofness of Scoring Allocation Correspondences for Indivisible Goods.

N. Nguyen, D. Baumeister and J. Rothe.

Social Choice and Welfare, vol. 50, no. 1, pp. 101-122, January 2018.

Complexity of Control by Partitioning Veto Elections and of Control by Adding Candidates to Plurality Elections.

C. Maushagen and J. Rothe.

Annals of Mathematics and Artificial Intelligence, vol. 82, no. 4, pp. 219-244, April 2018.

Structural Control in Weighted Voting Games.

A. Rey and J. Rothe.

The B.E. Journal of Theoretical Economics, vol. 18, no. 2, July 2018.

Approximation and Complexity of the Optimization and Existence Problems for Maximin Share, Proportional Share, and Minimax Share Allocation of Indivisible Goods.

T. Heinen, N. Nguyen, T. Nguyen, and J. Rothe.

Journal of Autonomous Agents and Multi-Agent Systems, vol. 32, no. 6, pp. 741-778, November 2018.

Verification in Incomplete Argumentation Frameworks.

D. Baumeister, D. Neugebauer, J. Rothe, and H. Schadrack.

Artificial Intelligence, vol. 264, pp. 1-26, November 2018.

Borda-Induced Hedonic Games with Friends, Enemies, and Neutral Players.

J. Rothe, H. Schadrack, and L. Schend.

Mathematical Social Sciences, vol. 96, pp. 21-36, November 2018.

Bounds on the Cost of Stabilizing a Cooperative Game.

Y. Bachrach, E. Elkind, E. Malizia, R. Meir, D. Pasechnik, J. Rosenschein, J. Rothe, and M. Zuckerman.

Journal of Artificial Intelligence Research, vol. 63, pp. 987-1023, December 2018.

Complexity of Verification in Incomplete Argumentation Frameworks.

D. Baumeister, D. Neugebauer, J. Rothe, and H. Schadrack.

Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI 2018), New Orleans, LA, USA. AAAI Press, pages 1753-1760, February 2018.

An
**extended version** also appears in the nonarchival proceedings of the 7th International Workshop on Computational Social Choice (COMSOC 2018), Troy, NY, USA, June 2018.

The Price to Pay for Forgoing Normalization in Fair Division of Indivisible Goods.

P. Lange, N. Nguyen, and J. Rothe.

Nonarchival website proceedings of the 11th
Multidisciplinary Workshop on Advances in Preference Handling (M-PREF 2018), New Orleans, LA, USA, February 2018.

A
**preliminary version** appeared in the nonarchival website proceedings of the 15th International Symposium on Artificial Intelligence and Mathematics (ISAIM 2018), Fort Lauderdale, FL, USA. January 2018.

Sequential Allocation Rules are Separable: Refuting a Conjecture on Scoring-Based Allocation of Indivisible Goods.

B. Kuckuck and J. Rothe.

Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018), Stockholm, Sweden. IFAAMAS, pages 650-658, July 2018.

An
**extended version** also appears in the nonarchival
proceedings of the 7th International Workshop on Computational Social Choice (COMSOC 2018), Troy, NY, USA, June 2018.

Complexity of Shift Bribery in Iterative Elections.

C. Maushagen, M. Neveling, J. Rothe, and A. Selker.

Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018), Stockholm, Sweden. IFAAMAS, pages 1567-1575, July 2018.

A
**preliminary version** appeared in the nonarchival website proceedings of the 15th International Symposium on Artificial Intelligence and Mathematics (ISAIM 2018), Fort Lauderdale, FL, USA. January 2018.

Credulous and Skeptical Acceptance in Incomplete Argumentation Frameworks.

D. Baumeister, D. Neugebauer, and J. Rothe.

Proceedings of the 7th International Conference on Computational Models of Argument (COMMA 2018), Warsaw, Poland. IOS Press, pages 181-192, September 2018.

Monotonicity, Duplication Monotonicity, and Pareto Optimality in the Scoring-Based Allocation of Indivisible Goods.

B. Kuckuck and J. Rothe.

Proceedings of the 6th International Conference on Agreement Technologies (AT 2018), Bergen, Norway. Springer-Verlag Lecture Notes in Artificial Intelligence 11327, pages 173-189, December 2018.

Lokale Dominanz in iterativen Wahlen.

L. Boes.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 65 pages, September 2018.

The Complexity of Various Distance Bribery Models.

T. Hogrebe.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 58 pages, July 2018.

### 2017

Strategic Behavior in Judgment Aggregation.

D. Baumeister, J. Rothe, and A. Selker.

Chapter 8 in Trends in Computational Social Choice, U. Endriss (editor), pp. 145-168. AI Access Foundation, 2017.

Path-Disruption Games: Bribery and a Probabilistic Model.

A. Rey, J. Rothe, A. Marple.

Theory of Computing Systems, vol. 60, no. 2, pp. 222-252, February 2017.

Positional Scoring-Based Allocation of Indivisible Goods.

D. Baumeister, S. Bouveret, J. Lang, T. Nguyen, N. Nguyen, J. Rothe, and A. Saffidine.

Journal of Autonomous Agents and Multi-Agent Systems, vol. 31, no. 3, pp. 628-655, May 2017.

The Complexity of Online Voter Control in Sequential Elections.

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

Journal of Autonomous Agents and Multi-Agent Systems, vol. 31, no. 5, pp. 1055-1076, September 2017.

The Complexity of Controlling Candidate-Sequential Elections.

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

Theoretical Computer Science, vol. 678, pp. 14-21, 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, CA, USA.
AAAI Press, pages 3029-3035, February 2017.

An
**extended version** also appears in the nonarchival proceedings of
the 7th International Workshop on Computational Social Choice (COMSOC 2018), Troy, NY, USA, June 2018.

Approximate Solutions To Max-Min Fair and Proportionally Fair Allocations of Indivisible Goods.

N. Nguyen, T. Nguyen, and J. Rothe.

Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), São Paulo, Brazil. IFAAMAS, pages 262-271, May 2017.

Complexity of Control by Partition of Voters and of Voter Groups in Veto and Other Scoring Protocols.

C. Maushagen and J. Rothe.

Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2017), São Paulo, Brazil. IFAAMAS, pages 615-623, May 2017.

Closing the Gap of Control Complexity in Borda Elections: Solving Ten Open Cases.

M. Neveling and J. Rothe.

Proceedings of the 18th Italian Conference on Theoretical Computer Science (ICTCS 2017), Napoli, Italy. CEUR-WS.org, vol. 1949, pages 138-149, September 2017.

Generating Defeasible Knowledge Bases from Real-World Argumentations using D-BAS.

D. Neugebauer.

Proceedings of the 1st Workshop on Advances in Argumentation in Artificial Intelligence (AI^3 2017), Bari, Italy. CEUR-WS.org, vol. 2012, pp. 105-110, November 2017.

Fair and Square: Issues of Fairness and Computation in Partition Problems.

N. Nguyen.

PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 153 pages with papers (67 pages without them), December 2017.

Klassische und parametrisierte Komplexität von Problemen der Wahlkontrolle.

C. Maushagen.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 50 pages, January 2017.

Wahlkontrolle im Standard- und im Online-Modell für Scoring-Protokolle.

M. Neveling.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 39 pages, January 2017.

Proceedings of the 5th International Conference on Algorithmic Decision Theory.

J. Rothe (editor).

Springer-Verlag Lecture Notes in Artificial Intelligence 10576, xxiii+390 pp., 2017.

### 2016

Control and Bribery in Voting.

P. Faliszewski and J. Rothe.

Chapter 7 in Handbook of Computational
Social Choice, F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia (editors),
pp. 146-168. Cambridge University Press, 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. 37-57, January 2016.

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

A. Rey, J. Rothe, H. Schadrack, and L. Schend.

Annals of Mathematics and Artificial Intelligence, vol. 77, no. 3-4, pp. 317-333, August 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 277-285, 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, FL, USA. January 2016.

Altruistic Hedonic Games.

N. Nguyen, L. Rey, A. Rey, J. Rothe, and L. Schend.

Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), Singapore. IFAAMAS, pages 251-259, May 2016.

Also presented at the 7th International Workshop on Cooperative Games in Multiagent Systems (CoopMAS 2016), co-located 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 232-241, May 2016.

Also presented at the 7th International Workshop on Cooperative Games in Multiagent Systems (CoopMAS 2016), co-located with AAMAS 2016, nonarchival proceedings.

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 Dagstuhl-Leibniz-Zentrum für Informatik, LIPIcs, vol. 58, pages 80:1-80: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 1371-1372, May 2016. Also presented at the *7th International Workshop on Cooperative Games in Multiagent Systems* (CoopMAS 2016), co-located 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.

Cost of Stability and Least Core in Path-Disruption Games.

V. Persien, A. Rey, and J. Rothe.

Proceedings of the 8th European Starting AI
Researcher Symposium (STAIRS 2016), The Hague, The Netherlands.
IOS Press, pages 99-110, August/September 2016.

Minisum and Minimax Committee Election Rules for General Preference Types.

D. Baumeister, T. Böhnlein, L. Rey, O. Schaudt, and A. Selker.

Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), The Hague, The Netherlands. IOS Press, pages 1656–1657, August/September 2016.

From Election Fraud to Finding the Dream Team: A Study of the Computational Complexity in Voting Problems and Stability in Hedonic Games.

L. Schend.

PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 211 pages, January 2016.

Beyond Intractability:A Computational Complexity Analysis ofVarious Types of Influence and Stabilityin Cooperative Games.

A. Rey.

PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 151 pages, April 2016.

### 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. 632-660, June 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. 661-670, June 2015.

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 Multi-Agent Systems, vol. 29, no. 6, pp. 1091-1124, November 2015.

Complexity of Manipulation and Bribery in Judgment Aggregation for Uniform Premise-Based Quota Rules.

D. Baumeister, G. Erdélyi, O. Erdélyi, and J. Rothe.

Mathematical Social Sciences, vol. 76, pp. 19-30, July 2015.

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 1229-1237, May 2015.

Voter Dissatisfaction in Committee Elections (Extended Abstract).

D. Baumeister and S. Dennisen.

Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015), Istanbul, Turkey. IFAAMAS, pages 1707-1708, May 2015.

Strategy-Proofness of Scoring Allocation Correspondences for Indivisible Goods.

N. Nguyen, D. Baumeister, J. Rothe,

Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), Buenos Aires, Argentina. AAAI Press/IJCAI, pages 1127-1133, July 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 Premise-Based 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, KY, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 9346, pages 432-448, September 2015.

Verification in Attack-Incomplete Argumentation Frameworks.

D. Baumeister, D. Neugebauer, and J. Rothe.

Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT 2015), Lexington, KY, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 9346, pages 341-358, 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 Rank-Weighted Utilitarianism in Resource Allocation.

T. Heinen, N. Nguyen, and J. Rothe.

Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT 2015), Lexington, KY, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 9346, pages 521-536, September 2015.

Verification in Argument-Incomplete Argumentation Frameworks.

D. Baumeister, J. Rothe, and H. Schadrack.

Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT 2015), Lexington, KY, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 9346, pages 359-376, September 2015.

Appears also in the nonarchival proceedings of the 6th International Workshop on Computational Social Choice (COMSOC 2016), Toulouse, France, June 2016.

Winner Determination and Manipulation in Minisum and Minimax Committee Elections.

D. Baumeister, S. Dennisen, and L. Rey.

Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT 2015), Lexington, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 9346, pages 469-485, September 2015.

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

J. Rothe (editor).

Springer Texts in Business and Economics, Springer-Verlag, Berlin, Heidelberg, xii+612 pages, 2015.

Authors: J. Rothe (Chapter 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).

### 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 Multi-Agent Systems, vol. 28, no. 2, pp. 256-289, March 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. 697-710, June 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.

Binary Linear Programming Solutions and Non-Approximability for Control Problems in Voting Systems.

F. Gurski and M. Roos.

Discrete Applied Mathematics, vol. 162, pp. 391-398, January 2014.

False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time.

A. Rey and J. Rothe.

Journal of Artificial Intelligence Research, vol. 50, pp. 573-601, July 2014.

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. 54-68, December 2014.

Scoring Rules for the Allocation of Indivisible Goods.

D. Baumeister, S. Bouveret, J. Lang, T. Nguyen, N. Nguyen, and J. Rothe.

Proceedings of the 21st European Conference on
Artificial Intelligence (ECAI 2014), Prague, Czech Republic. IOS
Press, pages 75-80, August 2014.

An extended version, jointly with A. Saffidine, 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, PA, USA, June 2014.

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 250-259, August 2014.

False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time.

A. Rey and J. Rothe.

Proceedings of the 11th Latin American Theoretical Informatics Symposium (LATIN 2014), Montevideo, Uruguay. Springer-Verlag Lecture Notes in Computer Science 8392, pages 60-71, March/April 2014.

Also presented at the 5th International Workshop on Cooperative Games in Multiagent Systems (CoopMAS 2014), co-located with AAMAS
2014, nonarchival proceedings.

Bribery in Multiple-Adversary Path-Disruption 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 Joint
Conference on Autonomous Agents and Multiagent Systems (AAMAS 2014), Paris, France. IFAAMAS, pages 1375-1376, May 2014.

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

A. 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 website proceedings of the Special Session
on Computational Social Choice at the 13th International Symposium on
Artificial Intelligence and Mathematics (ISAIM 2014), Fort Lauderdale, FL, USA. January 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 Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2014), Paris, France. IFAAMAS, pages 1357-1358, May 2014.

Messung und Minimierung der Wählerunzufriedenheit in Komiteewahlen.

S. Dennisen.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 2014.

Bestechung und Margin of Victory für einige Wahlsysteme.

Y. Reisch.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, April 2014.

Manipulative Angriffe auf Judgment-Aggregation-Prozeduren.

A. Selker.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 50 pages, September 2014.

Cake-cutting with Leftovers.

D. Neugebauer.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 53 pages, November 2014.

Complexity of Abstract Argumentation.

L. Rey.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 49 pages, August 2014.

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

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. 1-3, pp. 65-90, May-July 2013.

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. 1-3, pp. 161-193, May-July 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.

Envy-Ratio and Average-Nash 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, MN, USA. IFAAMAS, pages 1139-1140, May 2013.

An extended version was presented at the 6th International Workshop on Optimisation in Multi-Agent Systems (OPTMAS 2013), co-located with AAMAS 2013, nonarchival proceedings, pages 1-18.

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

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. Springer-Verlag Lecture Notes in Artificial Intelligence 8176, pages 271-284, November 2013.

Algorithms, Approximation, and Empirical Studies in Behavioral and Computational Social Choice---Preface.

J. Goldsmith and J. Rothe.

Annals of Mathematics and Artificial Intelligence, vol. 68, no. 1-3, pp. 3-4, May-July 2013.

False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time.

A. Rey and J. Rothe.

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

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

P. Faliszewski, Y. Reisch, J. Rothe, and L. Schend.

Technical Report arXiv:1307.7322v1 [cs.GT], ACM Computing Research Repository (CoRR), 28 pages, July 2013.

Approximability and Inapproximability of Social Welfare Optimization in Multiagent Resource Allocation.

T. Nguyen.

PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 109 pages, November 2013.

Algorithms and Complexity for Fair Division, Voting, and Peer Reviewing.

M. Roos.

PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 150 pages, November 2013.

Die Kosten der Stabilität in kooperativen Spielen.

T. Nikolaidou.

Diploma Thesis. Mathematisches Institut der Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, April 2013.

Manipulation Of Scoring Allocation Rules for Indivisible Ressources.

N. Nguyen.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 57 pages, September 2013.

Stability in Hedonic Games.

H. Schadrack.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 44 pages, September 2013.

Nash-Gleichgewichte in sequenziellen Wahlspielen.

J. Eßer.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 35 pages, October 2013.

### 2012

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. 186-190, February 2012.

Exact Optimization of Social Welfare by the Nash Product is DP-Complete.

N. Nguyen, M. Roos, and J. Rothe.

Website proceedings of the 12th International Symposium on Artificial Intelligence and Mathematics (ISAIM 2012), Fort Lauderdale, FL, USA. January 2012.

Complexity and Approximability of Social Welfare Optimization in Multiagent Resource Allocation (Extended Abstract).

T. Nguyen, N. Nguyen, M. Roos, and J. Rothe.

Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012), Valencia, Spain. IFAAMAS, pages 1287-1288, June 2012.

An extended version appears in the proceedings of the 4th International Workshop on Computational Social Choice (COMSOC 2012), F. Brandt and P. Faliszewski, editors, pages 335-346. AGH University of Science and Technology, Kraków, Poland, September 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 577-584, June 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. Springer-Verlag Lecture Notes in Computer Science 7276, pages 356-368, June 2012.

Probabilistic Path-Disruption Games.

A. Rey and J. Rothe.

Proceedings of the 20th European Conference on
Artificial Intelligence (ECAI 2012), Montpellier, France. IOS
Press, pages 923-924, August 2012.

An extended version appears in the proceedings of the 6th European Starting AI Researcher Symposium (STAIRS 2012), Montpellier, France. IOS Press, pages 264-269, August 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.

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 133-138, August 2012.

An extended version appears in the proceedings of the 4th International Workshop on Computational Social Choice (COMSOC 2012), F. Brandt and P. Faliszewski, editors, pages 49-60. AGH University of Science and Technology, Kraków, Poland, September 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 396-401, 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 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.

A Dynamic Model of Preference Aggregation.

H. Schadrack.

Proceedings of the 10th Conference on Logic and the Foundations of Game and Decision Theory (LOFT 2012), Sevilla, Spain. Short paper, June 2012.

Complexity and Approximability of Egalitarian and Nash Product Social Welfare Optimization in Multiagent Resource Allocation.

T. Nguyen, N. Nguyen, M. Roos, and J. Rothe.

Proceedings of the 6th European Starting AI Researcher Symposium (STAIRS 2012), Montpellier, France. IOS Press, pages 204-215, August 2012.

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

M. Roos, J. Rothe, J. Rudolph, B. Scheuermann, and D. Stoyan.

Website proceedings of the 6th Multidisciplinary Workshop on Advances in Preference Handling (M-PREF 2012), Montpellier, France, August 2012.

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

J. Rothe and L. Schend.

Website proceedings of the Special Session on Computational Social Choice at the 12th International Symposium on Artificial Intelligence and Mathematics (ISAIM 2012), Fort Lauderdale, FL, 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.

Website proceedings of the Special Session on Computational Social Choice at the 12th International Symposium on Artificial Intelligence and Mathematics (ISAIM 2012), Fort Lauderdale, FL, USA. January 2012.

Controlling Candidate-Sequential 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 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.

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.

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.

Computational Complexity in Three Areas of Computational Social Choice: Possible Winners, Unidirectional Covering Sets, and Judgment Aggregation

D. Baumeister.

PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 130 pages, September 2012.

Algorithmische und Sozialwahl-Eigenschaften des Wahlsystems von Schulze.

D. Internó.

Diploma Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, December 2012.

### 2011

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.

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.

Information and Computation, vol. 209, no. 2, pp. 89-107, February 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 853-860, May 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 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, CA, USA. AAAI Press, pages 255-260, August 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, Piscataway, NJ, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 6992, pages 1-15, October 2011.

Bribery in Path-Disruption Games.

A. Rey and J. Rothe.

Proceedings of the 2nd International Conference on Algorithmic Decision Theory (ADT 2011), DIMACS Center, Rutgers University, Piscataway, NJ, USA. Springer-Verlag Lecture Notes in Artificial Intelligence 6992, pages 247-261, 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.

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.

L. Piras.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 69 pages, January 2011.

Awarded the Ferchau Prize 2011 for the best Master thesis in Computer Science at HHU Düsseldorf.

Bribery in Path-Disruption Games.

A. Rey.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 58 pages, August 2011.

### 2010

Exakte Algorithmen für schwere Graphenprobleme.

F. Gurski, I. Rothe, J. Rothe, and E. Wanke.

eXamen.press, Springer-Verlag, Berlin, Heidelberg, xii+331 pages, 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.

Least Squares Timestamp Synchronization for Local Broadcast Networks.

F. Jarre, W. Kiess, M. Mauve, M. Roos, and B. Scheuermann.

Optimization and Engineering, vol. 11, no. 1, pp. 107-123, March 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.

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 641-648, May 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.

A Market-Affected Sealed-Bid Auction Protocol.

C. Lindner.

Proceedings of the 6th Hellenic Conference on Artificial Intelligence (SETN 2010), Athens, Greece. Springer-Verlag Lecture Notes in Artificial Intelligence 6040, pages 193-202, May 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 1021-1022 (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 1019-1020 (short paper), August 2010.

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 277-289, August 2010.

Introduction to Computational Complexity.

M. Roos and J. Rothe.

Supplement in the Mathematical Programming Glossary, A. Holder, editor. INFORMS Computing Society,
March 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.

Bestechung in Judgement-Aggregation-Protokollen.

K. Siekmann.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 49 pages, September 2010.

Bestechungsszenarien für Wahlsysteme und ihre Komplexität.

O. Wollermann.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 61 pages, March 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 pages, September 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.

On the Time Synchronization of Distributed Log Files in Networks with Local Broadcast Media.

F. Jarre, W. Kiess, M. Mauve, M. Roos, and B. Scheuermann.

IEEE/ACM Transactions on Networking, vol. 91, no. 1, pp. 431-444, April 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.

E. Hemaspaandra, L. 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 NLC-Width and Clique-Width for Powers of Graphs of Bounded Tree-Width.

F. Gurski and E. Wanke.

Discrete Applied Mathematics, vol. 157, no. 4, pp. 583-595, 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, 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.

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.

On Module-Composed Graphs.

F. Gurski and E. Wanke.

Proceedings of the 35th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France. Springer-Verlag Lecture Notes in Computer Science 5911, pages 166-177, June 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.

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.

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.

Degrees of Guaranteed Envy-Freeness in Finite Bounded Cake-Cutting Protocols.

C. Lindner and J. Rothe.

Technical Report arXiv:0902.0620v5 [cs.GT], ACM Computing Research Repository (CoRR), 37 pages, February 2009. Revised, October 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 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.

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.

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.

Optimierung von Mehrgitterverfahren für die Bildverarbeitung.

M. Roos.

Diploma Thesis. Mathematisches Institut der Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 90 pages, March 2009.

Komplexität von Nash-Equilibria.

A. Ingenhag.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 50 pages, January 2009.

Netzwerkflüsse und das Bestechungsproblem für das Copeland-Wahlsystem.

A. Bruné.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 71 pages, April 2009.

Empirische Evaluierung einer Greedy-Heuristik für Dodgson-Wahlen.

S. Bungter.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 85 pages, July 2009.

### 2008

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

J. Rothe.

eXamen.press, Springer-Verlag, Berlin, Heidelberg, xii+535 pages, 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.

Graph Parameters Measuring Neighbourhoods in Graphs - Bounds and Applications.

F. Gurski.

Discrete Applied Mathematics, vol. 156, no. 10, pp. 1865-1874, 2008.

Polynomial Algorithms for Protein Similarity Search for Restricted mRNA Structures.

F. Gurski.

Information Processing Letters, vol. 105, no. 5, pp. 170-176, 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.

Offline Time Synchronization for libpcap Logs.

F. Jarre, W. Kiess, D. Marks, M. Mauve, M. Roos, and B. Scheuermann.

WMAN-FG 2008: 1. GI/ITG KuVS Fachgespräch WMAN (Wireless Mobile Ad-Hoc Networks), Ulm, Germany, April 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, 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.

Error Bounds and Consistency of Maximum Likelihood Time Synchronization.

F. Jarre, W. Kiess, M. Mauve, M. Roos, and B. Scheuermann.

Technical Report TR-2008-001, Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, February 2008.

Das Ununterscheidbarkeitsproblem Fully-Flipped-QSCD und seine Anwendung in der Quantenkryptographie.

T. Daumann.

Diploma Thesis. Mathematisches Institut der Heinrich-Heine-Universität Düsseldorf, Düsseldorf, 95 pages, June 2008.

Lokale Suchheuristiken und Approximationsalgorithmen für Minimax-Lösungen beim Approval-Wahlverfahren.

S. Peslak.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 53 pages, March 2008.

Verteiltes Faktorisieren mit dem quadratischen Sieb: Eine Java-Implementierung.

M. Roos.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 56 pages, March 2008.

### 2007

An Improved Exact Algorithm for the Domatic Number Problem.

T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto.

Information Processing Letters, vol. 101, no. 3, pp. 101-106, February 2007.

Cryptology.

J. Rothe.

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

Complexity Theory.

J. Rothe.

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

On the Power of Unambiguity in Alternating Machines.

H. Spakowski and R. Tripathi.

Theory of Computing Systems, vol. 41, no. 2, pp. 291-326, July 2007. [pdf]

Anyone But Him: The Complexity of Precluding an Alternative.

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

Artificial Intelligence, vol. 171, no. 5-6, pp. 255-285, April 2007.

Quantum Cryptography: A Survey.

D. Bruß, G. Erdélyi, T. Meyer, T. Riege, and J. Rothe.

ACM Computing Surveys, vol. 39, no. 2, article 6, 27 pp., June 2007.

A Local Characterization of Bounded Clique-Width for Line Graphs.

F. Gurski and E. Wanke.

Discrete Mathematics, vol. 307, no. 6, pp. 756-759, 2007.

Characterizations for Restricted Graphs of NLC-Width 2.

F. Gurski.

Theoretical Computer Science, vol. 372, no. 1, pp. 108-114, 2007.

Line Graphs of Bounded Clique-Width.

F. Gurski and E. Wanke.

Discrete Mathematics, vol. 307, no. 22, pp. 2734-2754, 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, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.

Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI 2007), Vancouver, Canada. AAAI Press, pages 724-730, July 2007.

A version merging the AAAI-2007 and the AAIM-2008 versions appeared under the title "Llull and Copeland Voting Computationally Resist Bribery and Control" in the proceedings of the 2nd International Workshop on Computational Social Choice (COMSOC 2008), U. Endriss and P. Goldberg, editors, pages 241-252. University of Liverpool, UK, September 2008.

On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time.

G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.

Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT 2007), Budapest, Hungary.
Springer-Verlag Lecture Notes in Computer Science 4639, pages 300-311, August 2007.

An earlier version by J. Rothe and H. Spakowski appeared under the title "On Determining Dodgson Winners by Frequently Self-Knowingly Correct Algorithms and in Average-Case Polynomial Time" in the proceedings of the 1st International Workshop on Computational Social Choice (COMSOC 2006), U. Endriss and J. Lang, editors, pages 464-476. ILLC, University of Amsterdam, The Netherlands, December 2006. [pdf]

Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle
Problem.

D. Baumeister and J. Rothe.

Proceedings of the 5th Conference on Machines, Computations and Universality (MCU 2007), Orléans, France. Springer-Verlag Lecture Notes in Computer Science 4664, pages 134-145, September 2007. [pdf]

An algorithm for pseudo-3D-representation of the contour of the tongue while playing the didgeridoo.

W. Angerstein, V. Aurich, C. Lindner, and T. Massing.

Proceedings of the International Symposium on Musical Acoustics, pages 40-48, J. Agulló and A. Barjau, editors, ETSEIB, Department of Mechanical Engineering, Universitat Politècnica de Catalunya, Barcelona, September 2007.

The Clique-Width of Tree Powers and Leaf Powers (Extended Abstract).

F. Gurski and E. Wanke.

Proceedings of the 33th Workshop on Graph-Theoretic Concepts in Computer Science
(WG 2007), Dornburg, Germany. Springer-Verlag Lecture Notes in Computer Science 4769, pages 76-85, 2007.

A Method of Factoring Integers by Solving Multivariate Integer Polynomial Equations.

T. Nguyen.

Proceedings of the National Conference on
Algebra–Geometry–Topology, Vinh, Vietnam. Vinh University Press, pages 65-66 (short paper), December 2007.

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. 16-20, June 2007.

An algorithm for pseudo-3D-representation of the contour of the tongue while playing the didgeridoo.

W. Angerstein, V. Aurich, C. Lindner, and T. Massing.

Poster presented at the International Symposium on Musical Acoustics, J. Agulló and A. Barjau, editors, ETSEIB, Department of Mechanical Engineering, Universitat Politècnica de Catalunya, Barcelona, September 2007.

Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory.

L. Hemaspaandra, J. Rothe, and A. Saxena.

Technical Report cs.CC/0503049, ACM Computing Research Repository (CoRR), March 2005. Revised in April 2005 and November 2007.

Also appears as TR 854, University of Rochester, Department of Computer Science, Rochester, NY, December 2004. Revised in April 2005 and November 2007.

Hierarchical Unambiguity.

H. Spakowski and R. Tripathi.

Technical Report cs.CC/0702047, ACM Computing Research Repository (CoRR), 40 pages, February 2007

Llull and Copeland Voting Broadly Resist Bribery and Control.

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

The Expressive Power and Algorithmic Use of Graph Parameters.

F. Gurski.

Habilitationsschrift. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 149 pages, October 2007.

Komplexität der Kontrollprobleme für eine Variante des Approval
Voting.

M. Nowak.

Diploma Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 76 pages, October 2007.

Complexity of the Tantrix(TM) Rotation Puzzle Problem.

D. Baumeister.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 54 pages, September 2007.

Segmentation of Fine Structures in Noisy Volume Data.

C. Lindner.

Master Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 59 pages, July 2007.

Some Algorithms for Factoring Integers and Applications in Cryptography Theory.

T. Nguyen.

Master Thesis. National Institute of Mathematics, Hanoi, Vietnam, 60 pages, 2007.

### 2006

On Computing the Smallest Four-Coloring of Planar Graphs and Non-Self-Reducible Sets in P.

A. Große, J. Rothe, and G. Wechsung.

Information Processing Letters, vol. 99, no. 6, pp. 215-221, September 2006. [pdf]

Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.

E. Hemaspaandra, J. Rothe, and H. Spakowski.

R.A.I.R.O. Theoretical Informatics and Applications, vol. 40, no. 1, pp. 75-91, January 2006. [pdf]

LWPP and WPP are not Uniformly Gap-Definable.

H. Spakowski and R. Tripathi.

Journal of Computer and System Sciences, vol. 72, no. 4, pp. 660-689, June 2006.

Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems - a Survey.

T. Riege and J. Rothe.

Journal of Universal Computer Science, vol. 12, no. 5, pp. 551-578, May 2006.

An Improved Exact Algorithm for the Domatic Number Problem.

T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto.

Proceedings of the Second IEEE International Conference on Information & Communication Technologies: From Theory to Applications (ICTTA 2006), Damascus, Syria. IEEE Computer Society Press, pages 1021-1022, April 2006.

Also presented at the ICALP Affiliated Workshop for Improving Exponential-Time Algorithms (iETA'06), R. Niedermeier and O. Watanabe, editors, workshop notes, pages 53-58. Venice, Italy, July 2006.

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

L. Hemaspaandra, K. Pasanen, and J. Rothe.

Theoretical Computer Science, vol. 362, no. 1-3, pp. 54-62, October 2006. [pdf]

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.

T. Riege and J. Rothe.

Theory of Computing Systems, vol. 39, no. 5, pp. 635-668, September 2006.
On-line publication DOI 10.1007/s00224-004-1209-8, December 2004. [pdf]

Completeness for Parallel Access to NP and Counting Class Separations.

H. Spakowski.

In "Ausgezeichnete Informatikdissertationen 2005", D. Wagner et al., editors, Lecture Notes in Informatics, vol. D-6, pages 181-190, 2006.

Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.

T. Riege and J. Rothe.

Journal of Universal Computer Science, vol. 12, no. 6, pp. 725-744, June 2006.

Special issue: Computational Challenges of Massive Data Sets and Randomness in Computation, J. Rothe and H. Arimura, editors. Selected contributions from the First and Second Japanese-German Frontiers of Science Symposia (JaGFoS).

Computational Challenges of Massive Data Sets and Randomness in Computation.

J. Rothe and H. Arimura.

Journal of Universal Computer Science, vol. 12, no. 6, pp. 579-580, June 2006.

Preface of the Editors, J.UCS Special Issue on the First and Second Japanese-German Frontiers of Science Symposia.

Characterizations for co-Graphs Defined by Restricted NLC-Width or Clique-Width Operations.

F. Gurski.

Discrete Mathematics, vol. 306, no. 2, pp. 271-277, 2006.

Linear Layouts Measuring Neighbourhoods in Graphs.

F. Gurski.

Discrete Mathematics, vol. 306, no. 15, pp. 1637-1650, 2006.

Vertex Disjoint Paths on Clique-Width Bounded Graphs.

F. Gurski and E. Wanke.

Theoretical Computer Science, vol. 359, no. 1-3, pp. 188-199, 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.

Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems.

T. Riege and J. Rothe.

Technical Report TR06-036, Electronic Colloquium on Computational Complexity (ECCC), 24 pages, March 2006.

A Note on the Complexity of Computing the Smallest Four-Coloring of Planar Graphs.

A. Große, J. Rothe, and G. Wechsung.

Technical Report cs.CC/0106045-v2, ACM Computing Research Repository (CoRR), 9 pages, February 2006.

Revises the June 2001 version of Technical Report cs.CC/0106045 (CoRR).

Anyone But Him: The Complexity of Precluding an Alternative.

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

Technical Report cs.GT/0507027-v4, ACM Computing Research Repository (CoRR), 33 pages, March 2006.

Also appears as TR 873, University of Rochester, Department of Computer Science, Rochester, NY, March 2006.

Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.

T. Riege and J. Rothe.

Technical Report TR06-078, Electronic Colloquium on Computational Complexity (ECCC), 16 pages, June 2006.

Hierarchical Unambiguity.

H. Spakowski and R. Tripathi.

Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), Stara Lesna, Slovakia. Springer-Verlag Lecture Notes in Computer Science 4162, pages 777-788, August/September 2006.

Improving Exponential-Time Algorithms for NP-Complete Problems.

T. Riege and J. Rothe.

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

A Richer Understanding of the Complexity of Election Systems.

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

Technical Report cs.GT/0609112, ACM Computing Research Repository (CoRR), 33 pages, September 2006.

Also appears as TR 903, University of Rochester, Department of Computer Science, Rochester, NY, September 2006.

The Domatic Number Problem: Boolean Hierarchy Completeness and Exact Exponential-Time Algorithms.

T. Riege.

PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 109 pages, November 2006.

Charakterisierung der Existenz von
Einwegfunktionen.

T. Schlüter.

Diploma Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 63 pages, August 2006.

Das Hidden Subgroup Problem, Quantenalgorithmen und Anmerkungen zur Kryptographie.

D. Rehli.

Diploma Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 77 pages, November 2006.

### 2005

Complexity Theory and Cryptology. An Introduction to Cryptocomplexity.

J. Rothe.

EATCS Texts in Theoretical Computer Science, Springer-Verlag, Berlin, Heidelberg, xii+478 pages, 2005.

Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties.

H. Spakowski, M. Thakur, and R. Tripathi.

Information and Computation, vol. 200, no. 1, pp. 1-34, July 2005.

The Complexity of Kemeny Elections.

E. Hemaspaandra, H. Spakowski, and J. Vogel.

Theoretical Computer Science, vol. 349, no. 3, pp. 382-391, December 2005.

On the Power of Unambiguity in Alternating Machines.

H. Spakowski and R. Tripathi.

Proceedings of the 15th International Symposium on Fundamentals of Computation Theory (FCT 2005), Lübeck, Germany.
Springer-Verlag Lecture Notes in Computer Science 3623, pages 125-136, August 2005.

On the Relationship Between NLC-Width and Linear NLC-Width.

F. Gurski and E. Wanke.

Theoretical Computer Science, vol. 347, no. 1-2, pp. 76-85, 2005.

Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory.

L. Hemaspaandra, J. Rothe, and A. Saxena.

Proceedings of the Ninth Italian Conference on Theoretical Computer Science (ICTCS 2005), Siena, Italy.
Springer-Verlag Lecture Notes in Computer Science 3701, pages 265-279, October 2005.

An Exact 2.9416^n Algorithm for the Three Domatic Number Problem.

T. Riege and J. Rothe.

Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS 2005), Gdansk, Poland.
Springer-Verlag Lecture Notes in Computer Science 3618, pages 733-744, August 2005.

Anyone but Him: The Complexity of Precluding an Alternative.

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

Proceedings of the 20th National Conference on Artificial Intelligence (AAAI 2005), Pittsburgh, USA.
AAAI Press, pages 95-101, July 2005.

Quantum Cryptography: A Survey.

D. Bruß, G. Erdélyi, T. Meyer, T. Riege, and J. Rothe.

Technical Report TR05-146, Electronic Colloquium on Computational Complexity (ECCC), 25 pages, March 2006.

Extends the December 2005 version of TR05-146 (ECCC).

An Exact 2.9416^n Algorithm for the Three Domatic Number Problem.

T. Riege and J. Rothe.

Technical Report cs.CC/0506090, ACM Computing Research Repository (CoRR), 20 pages, June 2005.

Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.

E. Hemaspaandra, J. Rothe, and H. Spakowski.

Technical Report cs.CC/0110025, ACM Computing Research Repository (CoRR), 16 pages, October 2001. Revised, January 2005.

Minimizing NLC-Width is NP-Complete (Extended Abstract).

F. Gurski and E. Wanke.

Proceedings of the 31th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), Metz, France. Springer-Verlag Lecture Notes in Computer Science 3787, pages 69-80, 2005.

The Complexity of Voting.

J. Rothe.

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

Quantenkryptographie.

G. Erdélyi, T. Riege, and J. Rothe.

Invited talk at the Kutatasok 2005 az Eötvös Jozsef Föiskolan, Steinerne Molnar Judit, editor, pages 411-432. Baja, Hungary, November 2005.

Completeness for Parallel Access to NP and Counting Class Separations.

H. Spakowski.

PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 105 pages, July 2005.

Komplexitätstheoretische Untersuchungen zu Zählklassen, dem Graphisomorphie- und dem Ringisomorphie-Problem.

A. Stelzer.

Diploma Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 68 pages, December 2005.

### 2004

Kriptográfia.

J. Rothe.

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

Bonyolultságelmélet.

J. Rothe.

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

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.

T. Riege and J. Rothe.

Proceedings of the First IEEE International Conference on Information & Communication Technologies: From Theory to Applications (ICTTA 2004), Damascus, Syria. IEEE Computer Society Press, pages 653-654, April 2004. A six-page extended abstract is available from CD-ROM ISBN 0-7803-8483-0.

Complexity of Cycle Length Modularity Problems in Graphs.

E. Hemaspaandra, H. Spakowski, and M. Thakur.

Proceedings of the Sixth Latin American Symposium on Theoretical Informatics (LATIN 2004), Buenos Aires, Argentina.
Springer-Verlag Lecture Notes in Computer Science 2976, pages 509-518, April 2004.

Degree Bounds on Polynomials and Relativization Theory.

H. Spakowski and R. Tripathi.

Proceedings of the Third IFIP International Conference on Theoretical Computer Science (TCS 2004), Toulouse, France. Kluwer Academic Publishers, pages 97-110, August 2004.

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.

T. Riege and J. Rothe.

Technical Report cs.CC/0212016-v3,ACM Computing Research Repository (CoRR), 38 pages, March 2004.

Revises and extends the Technical Report cs.CC/0212016-v1, ACM Computing Research Repository (CoRR), 15 pages, December 2002.

On the Power of Unambiguity in Alternating Machines.

H. Spakowski and R. Tripathi.

Technical Report TR 851, University of Rochester, Department of Computer Science, Rochester,
NY, October 2004. Revised in November 2005.

Vertex Disjoint Paths on Clique-Width Bounded Graphs (Extended Abstract).

F. Gurski and E. Wanke.

Proceedings of the 6th Latin American Theortical Informatics (LATIN 2004), Buenos Aires, Argentina. Springer-Verlag Lecture Notes in Computer Science 2976, pages 119-128, 2004.

Exact-Four-Colorability, Exact Domatic Number Problems, and the Boolean Hierarchy.

J. Rothe.

Proceedings of the Dagstuhl Seminar 04421 "Algebraic Methods in Computational Complexity", 18 pp., October 2004.

Quantenkryptographie.

G. Erdélyi.

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

### 2003

Exact Complexity of Exact-Four-Colorability.

J. Rothe.

Information Processing Letters, vol. 87, no. 1, pp. 7-12, July 2003. [pdf]

Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties.

H. Spakowski, M. Thakur, and R. Tripathi.

Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2003), Mumbai, India.
Springer-Verlag Lecture Notes in Computer Science
2914, pages 375-386, December 2003.

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. 375-386, June 2003. [pdf]

Deciding Clique-Width for Graphs of Bounded Tree-Width.

W. Espelage, F. Gurski, and E. Wanke.

Journal of Graph Algorithms and Applications, vol. 7, no. 2, pp. 141-180, 2003.

Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties.

H. Spakowski, M. Thakur, and R. Tripathi.

Technical Report TR 801, University of Rochester, Department of Computer Science, Rochester,
NY, June 2003. Modified in July 2003. Revised in October 2004.

Complexity of Cycle Length Modularity Problems.

E. Hemaspaandra, H. Spakowski, and M. Thakur.

Technical Report cs.CC/0306131, ACM Computing Research Repository (CoRR), June 2003.

Also appears as TR 802, University of Rochester, Department of Computer Science, Rochester,
NY, June 2003.

Degree Bounds on Polynomials and Relativization Theory.

H. Spakowski and R. Tripathi.

Technical Report TR 820, University of Rochester, Department of Computer Science, Rochester,
NY, December 2003. Revised in March 2004. Revised in
October 2004.

The Complexity of Kemeny Elections.

E. Hemaspaandra, H. Spakowski, and J. Vogel.

Friedrich-Schiller-Universität Jena Technical Report Math/Inf/14/03, 14 pages, October 2003.

Effiziente Algorithmen für baumstrukturierte Graphklassen.

F. Gurski.

PhD Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 142 pages, July 2003.

Einwegfunktionen in der Kryptographie und deren Anwendung. Eine heuristische Analyse und Java-Implementierung.

O. Haupt.

Diploma Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 75 pages, September 2003.

### 2002

On Characterizing the Existence of Partial One-Way Permutations.

J. Rothe and L. Hemaspaandra.

Information Processing Letters, vol. 82, no. 3, pp. 165-171, May 2002.

Exact Complexity of Exact-Four-Colorability and of the Winner Problem for Young Elections.

J. Rothe, H. Spakowski, and J. Vogel.

Proceedings of the Second IFIP International Conference on Theoretical Computer Science (TCS 2002), which was held as Stream 1 of the 17th World Computer Congress, Montréal, Quebéc, Canada. Kluwer Academic Publishers, pages 310-322, 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 Graph-Theoretic Concepts in Computer Science (WG 2002), Cesky Krumlov, Czech Republic.
Springer-Verlag Lecture Notes in Computer Science 2573, pages 258-269, June 2002.

Some Facets of Complexity Theory and Cryptography: A Five-Lecture Tutorial.

J. Rothe.

ACM Computing Surveys, vol. 34, no. 4, pp. 504-549, December 2002.

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. 81-93, February 2002. [pdf]

Some Facets of Complexity Theory and Cryptography:
A Five-Lectures Tutorial.

J. Rothe.

Technical Report cs.CC/0111056, ACM Computing Research Repository (CoRR), 57 pages, December 2002.

Revised and extended version of the Lecture Notes for the 11th Jyväskylä Summer School, University of Jyväskylä, Finland, 46 pages, August 2001.

Complexity Theory and Cryptography.

J. Rothe.

Poster presented at the 8th German-American Frontiers of Science Symposium, Irvine, CA, USA, June 2002.

Vollständige Probleme in der Booleschen Hierarchie über NP.

T. Riege.

Diploma Thesis. Institut für Informatik, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 51 pages, August 2002.

### 2001

Kryptographische Protokolle und Null-Information.

J. Rothe.

Informatik Spektrum, vol. 25, no. 2, pp. 120-131, April 2002. In German.

Appears also in: Jahrbuch der Heinrich-Heine-Universität Düsseldorf 2001, pp. 183-201, Düsseldorf, 2001.

Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions.

A. Große, J. Rothe, and G. Wechsung.

Proceedings of the Proceedings of the Seventh International Italian Conference on Theoretical Computer Science (ICTCS 2001), Torino, Italia.
Springer-Verlag Lecture Notes in Computer Science 2202, pages 339-356, 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.
Springer-Verlag Lecture Notes in Computer Science 2138, pages 162-171, August 2001.

Exact Complexity of the Winner Problem for Young Elections.

J. Rothe, H. Spakowski, and J. Vogel.

Technical Report cs.CC/0112021, ACM Computing Research Repository (CoRR), 10 pages, December 2001.

Exact Complexity of Exact-Four-Colorability.

J. Rothe.

Technical Report cs.CC/0109018, ACM Computing Research Repository (CoRR), 5 pages, September 2001.

Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones.

A. Große, J. Rothe, and G. Wechsung.

Technical Report cs.CC/0106041, ACM Computing Research Repository (CoRR), 12 pages, June 2001.

Revises Friedrich-Schiller-Universität Jena Technical Report Math/Inf/00/23, 14 pages, August 2000.

The Complexity of Kemeny's Voting System.

H. Spakowski and J. Vogel.

Proceedings of the Argentinian Workshop on Theoretical Computer Science (WAIT 2001), Buenos Aires, Argentina, pages 157-168, September 2001.

How to Solve NP-Hard Graph Problems on Clique-Width Bounded Graphs in Polynomial Time.

W. Espelage, F. Gurski, and E. Wanke.

Proceedings of the 27th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), Boltenhagen, Germany. Springer-Verlag Lecture Notes in Computer Science 2204, pages 117-128, 2001.

Deciding Clique-Width for Graphs of Bounded Tree-Width (Extended Abstract).

W. Espelage, F. Gurski, and E. Wanke.

Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS 2001), Providence, RI, USA. Springer-Verlag Lecture Notes in Computer Science 2125, pages 87-98, 2001.

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. 504-549, December 2002. [pdf]

Kryptographische Protokolle und Null-Information.

J. Rothe.

Jahrbuch der Heinrich-Heine-Universität Düsseldorf 2001, pp. 183-201, Düsseldorf, 2001. In German.

Appears also in: Informatik Spektrum, Springer-Verlag, vol. 25, no. 2, pp. 120-131, April 2002.

### 2000

Characterizing the Existence of One-Way Permutations.

L. Hemaspaandra and J. Rothe.

Theoretical Computer Science, vol. 244, no. 1-2, pp. 257-261, August 2000.

Tally NP Sets and Easy Census Functions.

J. Goldsmith, M. Ogihara, and J. Rothe.

Information and Computation, vol. 158, no. 1, pp. 29-52, 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. 86-95, March 2000.

Heuristics versus Completeness for Graph Coloring.

J. Rothe.

Chicago Journal of Theoretical Computer Science, vol. 2000, article 1, 16 pages, February 2000.

Theta_2^p-Completeness: A Classical Approach for New Results.

H. Spakowski and J. Vogel.

Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2000), Delhi, India.
Springer-Verlag Lecture Notes in Computer Science
1974, pages 348-360, December 2000.

A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem.

L. Hemaspaandra and J. Rothe.

Theoretical Computer Science, vol. 244, no. 1-2, pp. 205-217, August 2000.

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

L. Hemaspaandra, K. Pasanen, and J. Rothe.

Technical Report cs.CC/0010011, ACM Computing Research Repository (CoRR), 9 pages, October 2000.

Toward a Theory of Completeness for Parallel Access to NP.

H. Spakowski and J. Vogel.

Friedrich-Schiller-Universität Jena Technical Report Math/Inf/00/19, 18 pages, July 2000.

The Complexity of Voting Schemes --- a Method for Proving Completeness for Parallel Access to NP.

H. Spakowski and J. Vogel.

Friedrich-Schiller-Universität Jena Technical Report Math/Inf/00/16, 21 pages, June 2000.

The Tree-Width of Clique-Width Bounded Graphs Without K_{n,n}.

F. Gurski and E. Wanke.

Proceedings of the 26th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000), Konstanz, Germany. Springer-Verlag Lecture Notes in Computer Science 1928, pages 196-205, 2000.

Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions.

A. Große, J. Rothe, and G. Wechsung.

Friedrich-Schiller-Universität Jena Technical Report Math/Inf/00/23, 14 pages, August 2000.

### 1999

Creating Strong, Total, Commutative, Associative One-Way Functions from Any One-Way Function in Complexity Theory.

L. Hemaspaandra and J. Rothe.

Journal of Computer and System Sciences, vol. 58, no. 3, pp. 648-659, 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. 159-176, March/April 1999.

Restrictive Acceptance Suffices for Equivalence Problems.

B. Borchert, L. Hemaspaandra, and J. Rothe.

Proceedings of the Twelfth International Symposium on Fundamentals of Computation Theory (FCT 1999), Iasi, Romania.
Springer-Verlag Lecture Notes in Computer Science 1684, pages 124-135, August/September 1999.

The Operators minCh and maxCh on the Polynomial Hierarchy.

H. Spakowski and J. Vogel.

Proceedings of the Twelfth International Symposium on Fundamentals of Computation Theory (FCT 1999), Iasi, Romania. Springer-Verlag Lecture Notes in Computer Science 1684, pages 524-535, August 1999.

Komplexität von Zertifikaten, Heuristiken und Zähltypen mit Anwendungen in der Kryptographie und Schaltkreistheorie.

J. Rothe.

Summary of the Habilitationsschrift. Jenaer Schriften zur Mathematik und Informatik. Technical Report Math/Inf/99/7. Friedrich-Schiller-Universität Jena, Jena, Germany, 23 pages, February 1999. In German.

Characterizations of the Existence of Partial and Total One-Way Permutations.

L. Hemaspaandra and J. Rothe.

Technical Report cs.CC/9907040, ACM Computing Research Repository (CoRR), 12 pages, July 1999.

Earlier version appeared as Friedrich-Schiller-Universität Jena Technical Report Math/Inf/96/7, 12 pages, April 1996.

Restrictive Acceptance Suffices for Equivalence Problems.

B. Borchert, L. Hemaspaandra, and J. Rothe.

Technical Report cs.CC/9907041, ACM Computing Research Repository (CoRR), 14 pages, July 1999.

Revises Friedrich-Schiller-Universität Jena Technical Report Math/Inf/96/13,
1996.

Polynomial-Time Multi-Selectivity.

L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe.

Technical Report cs.CC/9907034, ACM Computing Research Repository (CoRR), 40 pages, July 1999.

Earlier version appeared as University of Rochester Technical Report TR 568, 35 pages, January 1995.

Easy Sets and Hard Certificate Schemes.

L. Hemaspaandra, J. Rothe, and G. Wechsung.

Technical Report cs.CC/9907035, ACM Computing Research Repository (CoRR), 26 pages, July 1999.

Revises Friedrich-Schiller-Universität Jena Technical Report Math/95/5,
1995.

The Operators minCh and maxCh on the Polynomial Hierarchy.

H. Spakowski and J. Vogel.

Friedrich-Schiller-Universität Jena Technical Report Math/Inf/99/22, 19 pages, August 1999.

One-Way Functions in Worst-Case 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. 25-40, December 1999.

Leichte und schwere Mengen in NP.

J. Rothe.

In: Komplexität, Graphen und Algorithmen, J. Vogel, K. Wagner, Eds., pp. 71-90, Würzburg, February 1999. In German.

One-Way Functions in Worst-Case Cryptography: Algebraic and Security Properties.

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

Technical Report cs.CC/9911007, ACM Computing Research Repository (CoRR), 17 pages, November 1999.

Complexity of Certificates, Heuristics, and Counting Types, with Applications to Cryptography and Circuit Theory.

J. Rothe.

Habilitationsschrift. Institut für Informatik, Friedrich-Schiller-Universität Jena, Jena, Germany, 159 pages, February 1999.

Die Operatoren minCh und maxCh auf den Klassen der Polynomialzeithierarchie.

H. Spakowski.

Diploma Thesis. Institut für Informatik, Friedrich-Schiller-Universität Jena, Jena, Germany, 37 pages, 1999.

### 1998

Boolean Operations, Joins, and the Extended Low Hierarchy.

L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe.

Theoretical Computer Science vol. 205, no. 1-2, pp. 317-327, 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. 151-156, February 1998.

Tally NP Sets and Easy Census Functions.

J. Goldsmith, M. Ogihara, and J. Rothe.

Proceedings of the Twenty-Third International Symposium on Mathematical Foundations of Computer Science (MFCS 1998), Brno, Czech Republic.
Springer-Verlag Lecture Notes in Computer Science 1450, pages 483-492, August 1998.

Immunity and Simplicity for Exact Counting and Other Counting Classes.

J. Rothe.

Proceedings of the Ninth International Conference on Computing and Information (ICCI 1998), pages 279-286, Winnipeg, Manitoba, Canada, June 1998.

A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem.

L. Hemaspaandra and J. Rothe.

Proceedings of the Twenty-Third International Symposium on Mathematical Foundations of Computer Science (MFCS 1998), Brno, Czech Republic.
Springer-Verlag Lecture Notes in Computer Science 1450, pages 418-426, August 1998.

Heuristics versus Completeness for Graph Coloring.

J. Rothe.

Friedrich-Schiller-Universität Jena Technical Report Math/Inf/98/29, 13 pages, November 1998.

Creating Strong Total Commutative Associative Complexity-Theoretic One-Way Functions from Any Complexity-Theoretic One-Way Function.

L. Hemaspaandra and J. Rothe.

University of Rochester Technical Report TR 688, Rochester, NY, 13
pages, Mai 1998.

Appears also as Technical Report cs.CC/9808003, ACM Computing Research Repository (CoRR), 11 pages, August 1998.

Tally NP Sets and Easy Census Functions.

J. Goldsmith, M. Ogihara, and J. Rothe.

University of Rochester
Technical Report TR 684, Rochester, NY, 23 pages, March 1998.

Appears also as Technical Report cs.CC/9809002, ACM Computing Research Repository (CoRR), 24 pages, September 1998.

Immunity and Simplicity for Exact Counting and Other Counting Classes.

J. Rothe.

University of Rochester
Technical Report TR 679, Rochester, NY, 21 pages, January 1998.

Appears also as Technical Report cs.CC/9809001, ACM Computing Research Repository (CoRR), 20 pages, September 1998.

Algorithmische Charakterisierungen spezieller Graphklassen.

F. Gurski.

Diploma Thesis. Mathematisches Institut, Heinrich-Heine-Universität Düsseldorf, Düsseldorf, Germany, 94 pages, September 1998.

### 1997

Polynomial-Time Multi-Selectivity.

L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe.

Journal of Universal Computer Science, vol. 3, no. 3, pp. 197-229, March 1997.

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. Springer-Verlag Lecture Notes in Computer Science 1256, pages 214-224, July 1997.

On Sets with Easy Certificates and the Existence of One-Way Permutations.

L. Hemaspaandra, J. Rothe, and G. Wechsung.

Proceedings of the Third Italian Conference on Algorithms and Complexity (CIAC 1997), Rome, Italy. Springer-Verlag Lecture Notes in Computer Science 1203, pages 264-275, March 1997.

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. 806-825, November 1997.

Easy Sets and Hard Certificate Schemes.

L. Hemaspaandra, J. Rothe, and G. Wechsung.

Acta Informatica, vol. 34, no. 11, pp. 859-879, November 1997.

Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets.

L. Hemaspaandra and J. Rothe.

SIAM Journal on Computing, vol. 26, no. 3, pp. 634-653, June 1997. [pdf]

Raising NP Lower Bounds to Parallel NP Lower Bounds.

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

University of Rochester Technical Report TR 658, Rochester, NY, 12 pages, May 1997.

Appears also as Technical Report cs.CC/9907039, ACM Computing Research Repository (CoRR), 14 pages, July 1999.

Raising NP Lower Bounds to Parallel NP Lower Bounds.

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

SIGACT News, vol. 28, no. 2, pp. 2-13, June 1997.

A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem.

L. Hemaspaandra and J. Rothe.

University of Rochester Technical Report TR 662, Rochester, NY, 10 pages, 1997.

Appears also as Technical Report cs.CC/9907038, ACM Computing Research Repository (CoRR), 15 pages, July 1999.

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.

University of Rochester Technical Report TR 640, Rochester, NY, October 1996, revised May 1997.

Appears also as Technical Report cs.CC/9907036, ACM Computing Research Repository (CoRR), 22 pages, July 1999.

### 1996

The Join Can Lower Complexity.

L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe.

Proceedings of the Second Annual International Computing and Combinatorics Conference (COCOON 1996), Hong Kong. Springer-Verlag Lecture Notes in Computer Science 1090, pages 260-267, June 1996.

The Join Can Lower Complexity.

L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe.

Friedrich-Schiller-Universität Jena Technical Report Math/Inf/96/12, 10 pages, June 1996.

Boolean Operations, Joins, and the Extended Low Hierarchy.

L. Hemaspaandra, Z. Jiang, J. Rothe, and O. Watanabe.

University of Rochester Technical Report TR 627, June 1996.

Appears also as Technical Report cs.CC/9907037, ACM Computing Research Repository (CoRR), 12 pages, July 1999.

Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems.

B. Borchert, L. Hemaspaandra, and J. Rothe.

Friedrich-Schiller-Universität Jena Technical Report Math/Inf/96/13, 14 pages, June 1996.

Easy Sets and Hard Certificate Schemes.

L. Hemaspaandra, J. Rothe, and G. Wechsung.

Workshop on Computability, Complexity and Logic, Preprint-Reihe Mathematik Nr. 1-1996, Universität Greifswald, abstract p. 43, Zinnowitz, Germany, März 1996.

On Some Promise Classes in Structural Complexity Theory.

J. Rothe.

Dissertation Summaries in Mathematics Khayyam Publishing Company (Athens, Ohio), vol. 1, no. 1-2, pp. 323-330, 1996.

### 1995

Intersection Suffices for Boolean Hierarchy Equivalence.

L. Hemaspaandra and J. Rothe.

Proceedings of the First Annual International Computing and Combinatorics Conference (COCOON 1995), Xi'an, China.
Springer-Verlag Lecture Notes in Computer Science 959, pages 430-435, August 1995.

A Promise Class at Least as Hard as the Polynomial Hierarchy.

J. Rothe.

Journal of Computing and Information, vol. 1, no. 1, pp. 92-107. CD-ROM ISSN 1201-8511, Trent University Press, April 1995.

Special Issue: Proceedings of the Sixth International Conference on Computing and Information, May 1994.

On Some Promise Classes in Structural Complexity Theory.

J. Rothe.

PhD Thesis. Institut für Informatik, Friedrich-Schiller-Universität Jena, Jena, Germany, 113 pages, October 1995.

Reviewed by U. Schöning in Zentralblatt für Mathematik, Springer-Verlag.

### 1994

A Note on the Polynomial-Time Hierarchy and Probabilistic Operators.

J. Rothe and J. Vogel.

Computers and Artificial Intelligence, vol. 13, no. 1, pp. 2-12, January 1994.

A Promise Class at Least as Hard as the Polynomial Hierarchy.

J. Rothe.

Proceedings of the Sixth International Conference on Computing and Information (ICCI 1994), pages 92-107, Peterborough, Ontario, Canada, May 1994.

Upward Separation for FewP and Related Classes.

R. Rao, J. Rothe, and O. Watanabe.

Information Processing Letters, vol. 52, no. 4, pp. 175-180, November 1994.

Corrigendum appears in the same journal, vol. 74, no. 1-2, p. 89, April 2000.

A General Method to Determine Invariants.

I. Rothe, J. Rothe, H. Süße, and K. Voß.

University of Rochester Technical Report TR 503,
Rochester, NY, 24 pages, April 1994.

Upward Separation for FewP and Related Classes.

R. Rao, J. Rothe, and O. Watanabe.

University of Rochester Technical Report TR 488, 9 pages, February 1994.

A Promise Class at Least as Hard as the Polynomial Hierarchy.

J. Rothe.

University of Rochester Technical Report TR 484, 20 pages, January 1994.

Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets.

L. Hemaspaandra and J. Rothe.

University of Rochester Technical Report TR 483, Rochester, NY, 24 pages, January 1994.

Appears also as Technical Report cs.CC/9907033, ACM Computing Research Repository (CoRR), 27 pages, July 1999.

### 1993

On Promise Classes and Operators.

J. Rothe.

Friedrich-Schiller-Universität Jena Technical Report Math/93/9, 11 pages, December 1993.

### 1992

A Note on the Polynomial-Time Hierarchy and Probabilistic Operators.

J. Rothe and J. Vogel.

Friedrich-Schiller-Universität Jena Technical Report Math/92/8, 11 pages, November 1992.

### 1991

Die Polynomialzeit-Hierarchie und Probabilistische Operatoren.

J. Rothe.

Diploma Thesis. Institut für Informatik, Friedrich-Schiller-Universität Jena, Jena, Germany, 65 pages, September 1991.