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