Publications

Sort by  |  Author

1999

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.

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.

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.

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]

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.

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.

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.