## Publications

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

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

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.

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.

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

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.

L. Hemaspaandra, E. 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.

L. Hemaspaandra, E. 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.

L. Hemaspaandra, E. 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.

L. Hemaspaandra, E. 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.