List of Publications

Here are some further links to a database containing also old technical reports and the complete publication list of our group:

Jörg Rothe's publications sorted by type of publication | sorted by year.

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

Jörg Rothe's DBLP entry (which is a bit hard to find due to the Umlaut in my name).

Books

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

Complexity Theory and Cryptology. An Introduction to Cryptocomplexity.
J. Rothe.
EATCS Texts in Theoretical Computer Science, Springer-Verlag, Berlin, Heidelberg, New York, xii+478 pp., 2005.

Refereed Journal Publications

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.

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.

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.

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.

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.

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.

Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem.
D. Baumeister and J. Rothe.
Fundamenta Informaticae, vol. 91, no. 1, pp. 35-51, January 2009.

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.

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

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

An Improved Exact Algorithm for the Domatic Number Problem.
T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto.
Information Processing Letters, vol. 101, no. 3, pp. 101-106, February 2007.

If P ≠ NP then Some Strongly Noninvertible Functions are Invertible.
L. Hemaspaandra, K. Pasanen, and J. Rothe.
Theoretical Computer Science, vol. 362, no. 1-3, pp. 54-62, October 2006. [pdf]

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.

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

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]

Exact Complexity of Exact-Four-Colorability.
J. Rothe.
Information Processing Letters, vol. 87, no. 1, pp. 7-12, July 2003. [pdf]

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]

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

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.

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.

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]

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.

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.

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

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.

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

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.

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.

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

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]

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.

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

Refereed Publications in Conference Proceedings

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

Complexity of Social Welfare Optimization in Multiagent Resource Allocation.
M. Roos and J. Rothe.
To appear in the proceedings of the 9th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada. International Foundation of Autonomous Agents and MultiAgent Systems (IFAAMAS), May 2010.

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

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.

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.

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 Computer Science 5783, pages 86-97, October 2009.

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

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

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.

Copeland Voting Fully Resists Constructive Control.
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM 2008), Shanghai, China.
Springer-Verlag Lecture Notes in Computer Science 5034, pages 165-176, June 2008.

The Three-Color and Two-Color Tantrix(TM) Rotation Puzzle Problems are NP-Complete via Parsimonious Reductions.
D. Baumeister and J. Rothe.
To appear in the 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.

Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem.
D. Baumeister and J. Rothe.
Proceedings of the Fifth Conference on Machines, Computations and Universality (MCU 2007), Orléans, France.
Springer-Verlag Lecture Notes in Computer Science 4664, pages 134-145, September 2007.

On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time.
G. Erdélyi, L. Hemaspaandra, J. Rothe, and H. Spakowski.
Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT 2007), Budapest, Hungary.
Springer-Verlag Lecture Notes in Computer Science 4639, pages 300-311, August 2007.

Llull and Copeland Voting Broadly Resist Bribery and Control.
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI 2007), Vancouver, Canada.
AAAI Press, pages 724-730, July 2007.

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.

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 2006), R. Niedermeier and O. Watanabe, editors, workshop notes, pages 53-58. Venice, Italy, July 2006.

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.
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Proceedings of the 20th National Conference on Artificial Intelligence (AAAI 2005), Pittsburgh, USA.
AAAI Press, pages 95-101, July 2005.

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem.
T. Riege and J. Rothe.
Proceedings of the 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.

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 (WCC 2002), 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.

Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions.
A. Große, J. Rothe, and G. Wechsung.
Proceedings of the Seventh International Italian Conference on Theoretical Computer Science (ICTCS 2001), Torino, Italy.
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.

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.

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.

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.

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.

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

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.

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.
Proceedings of the Sixth International Conference on Computing and Information (ICCI 1994), pages 92-107, Peterborough, Ontario, Canada, May 1994.

Refereed Contributions to Workshops

Llull and Copeland Voting Computationally Resist Bribery and Control.
P. Faliszewski, L. Hemaspaandra, E. Hemaspaandra, and J. Rothe.
Presented at the (refereed, but without copyrighted proceedings) 2nd International Workshop on Computational Social Choice (COMSOC 2008), U. Endriss and P. Goldberg, editors, workshop notes, pages 241-252. Liverpool, UK, September 2008.

Sincere-Strategy Preference-Based Approval Voting Fully Resists Constructive Control and Broadly Resists Destructive Control.
G. Erdélyi, M. Nowak, and J. Rothe.
Presented at the (refereed, but without copyrighted proceedings) 2nd International Workshop on Computational Social Choice (COMSOC 2008), U. Endriss and P. Goldberg, editors, workshop notes, pages 229-240. Liverpool, UK, September 2008.

On Determining Dodgson Winners by Frequently Self-Knowingly Correct Algorithms and in Average-Case Polynomial Time.
J. Rothe and H. Spakowski.
Presented at the (refereed, but without copyrighted proceedings) 1st International Workshop on Computational Social Choice (COMSOC 2006), U. Endriss and J. Lang, editors, workshop notes, pages 464-476. Amsterdam, The Netherlands, December 2006.

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control.
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Presented at the (refereed, but without copyrighted proceedings) 1st International Workshop on Computational Social Choice (COMSOC 2006), U. Endriss and J. Lang, editors, workshop notes, pages 234-247. Amsterdam, The Netherlands, December 2006.

Book Chapters

Computational Aspects of Approval Voting.
D. Baumeister, G. Erdélyi, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
In "Handbook of Approval Voting," J. Laslier and R. Sanver, editors. Springer, Berlin, Heidelberg, New York, to appear.

A Richer Understanding of the Complexity of Election Systems.
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Chapter 14 in "Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz," pp. 375-406, S. Ravi and S. Shukla, editors. Springer, Berlin, Heidelberg, New York, 2009.

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

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

Bonyolultságelmélet.
J. Rothe.
Chapter 4 in "Informatikai Algoritmusok I," pp. 125-160, A. Iványi, editor. ELTE Eötvös Kiadó, Budapest, 2004. In Hungarian.

Kriptográfia.
J. Rothe.
Chapter 3 in "Informatikai Algoritmusok I," pp. 94-124, A. Iványi, editor. ELTE Eötvös Kiadó, Budapest, 2004. In Hungarian.

Invited Contributions to Journals, Conferences, Workshops, etc.

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.

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.

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

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

Improving 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 2006), R. Niedermeier and O. Watanabe, editors, workshop notes, pages 65-76. Venice, Italy, July 2006.

Quantenkryptographie.
G. Erdélyi, T. Riege, and J. Rothe.
Invited talk at the Kutatasok 2005 az Eötvös Jozsef Föiskolan, Steinerne Molnar Judit, editor, pages 411-432. Baja, Hungary, November 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.

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.

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

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

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

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, vol. 25, no. 2, pp. 120-131, April 2002.

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.

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.

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, March 1996.

Additional Journal and Other Publications

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

Computational Challenges of Massive Data Sets and Randomness in Computation.
J. Rothe and H. Arimura.
Journal of Universal Computer Science, vol. 12, no. 6, pp. 579-580, June 2006.
Preface of the editors. J.UCS special issue on the First and Second Japanese-German Frontiers of Science Symposia (JaGFoS).

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.
In: "Computational Challenges of Massive Data Sets and Randomness in Computation," J. Rothe and H. Arimura, editors. J.UCS special issue on the First and Second Japanese-German Frontiers of Science Symposia (JaGFoS).

On Some Promise Classes in Structural Complexity Theory.
J. Rothe.
Dissertation Summaries in Mathematics, Khayyam Publishing Company (Athens, Ohio), vol. 1, no. 1-2, pp. 323-330, 1996.

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-Line Available Technical Reports since 2004

The Shield that Never Was: Societies with Single-Peaked Preferences are More Open to Manipulation and Control.
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Technical Report arXiv:0909.3257 [cs.GT], ACM Computing Research Repository (CoRR), 38 pages, September 2009.
Also appears as Technical Report TR 950, University of Rochester, Department of Computer Science, Rochester, NY, 38 pages, September 2009.

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

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

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

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

Degrees of Guaranteed Envy-Freeness in Finite Bounded Cake-Cutting Protocols.
C. Lindner and J. Rothe.
Technical Report arXiv:0902.0620v5 [cs.CC], ACM Computing Research Repository (CoRR), 37 pages, February 2009. Revised, October 2009.

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

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.

Llull and Copeland Voting Computationally Resist Bribery and Control.
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Technical Report arXiv:0809.4484v2 [cs.GT], ACM Computing Research Repository (CoRR), 77 pages, September 2008.
Also appears as Technical Report TR 933, University of Rochester, Department of Computer Science, Rochester, NY, 77 pages, April 2008. Revised, September 2008.

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

Copeland Voting Fully Resists Constructive Control.
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Technical Report arXiv:0711.4759v2 [cs.GT], ACM Computing Research Repository (CoRR), 15 pages, November 2007. Revised, December 2007.
Also appears as Technical Report TR 923, University of Rochester, Department of Computer Science, Rochester, NY, 15 pages, October 2007.

Satisfiability Parsimoniously Reduces to the Tantrix(TM) Rotation Puzzle Problem.
D. Baumeister and J. Rothe.
Technical Report arXiv:0705.0915v2 [cs.CC], ACM Computing Research Repository (CoRR), 13 pages, May 2007. Revised, 19 pages, June 2008.

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

Llull and Copeland Voting Broadly Resist Bribery and Control.
P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Technical Report TR 913, University of Rochester, Department of Computer Science, Rochester, NY, 13 pages, February 2007.

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

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

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

Improving Deterministic and Randomized 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.

An Improved Exact Algorithm for the Domatic Number Problem.
T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto.
Technical Report cs.CC/0603060, ACM Computing Research Repository (CoRR), 9 pages, March 2006.

Anyone But Him: The Complexity of Precluding an Alternative.
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.
Technical Report cs.GT/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.

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.
Revises Technical Report cs.CC/0106045, ACM Computing Research Repository (CoRR), 9 pages, February 2006.

An Exact 2.9416^n Algorithm for the Three Domatic Number Problem.
T. Riege and J. Rothe.
Technical Report cs.CC/0506090, ACM Computing Research Repository (CoRR), 20 pages, June 2005.

Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for 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, April 2005 and November 2007. Also appears as TR 854, University of Rochester, Department of Computer Science, Rochester, NY, December 2004. Revised, April 2005 and November 2007.

Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP.
E. Hemaspaandra, J. Rothe, and H. Spakowski.
Technical Report cs.CC/0110025, ACM Computing Research Repository (CoRR), 16 pages, October 2001. Revised, January 2005.

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

Habilitationsschrift

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

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

PhD Thesis

On Some Promise Classes in Structural Complexity Theory.
J. Rothe.
Friedrich-Schiller-Universität Jena, Jena, Germany, 113 pages, October 1995. Reviewed by U. Schöning in Zentralblatt für Mathematik, Springer-Verlag.

Diploma Thesis

Die Polynomialzeit-Hierarchie und Probabilistische Operatoren.
J. Rothe.
Friedrich-Schiller-Universität Jena, Jena, Germany, 65 pages, September 1991. In German.