Publications

Sort by  |  Author

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]

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]

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.

2003

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]

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.

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.

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.

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.

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.

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.

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.