Most of the recent papers from this list can be found, in their
technical report versions, in the UR CS technical report on-line
archive, which can be reached via my home page.
JOURNAL AND BOOK PUBLICATIONS (Last Updated: 11/96)
Lane A. Hemaspaandra
(born Lane
A. Hemachandra)
BOOKS IN PREPARATION OR TO APPEAR
The Complexity Theory Companion,
L. Hemaspaandra and M. Ogihara,
in preparation.
Semi-Feasible Computation,
L. Hemaspaandra and L. Torenvliet,
in preparation.
Complexity Theory Retrospective II,
L. Hemaspaandra and A. Selman, editors, Springer-Verlag,
to appear.
BOOK CHAPTERS
Witness-Isomorphic Reductions and Local Search,
S. Fischer, L. Hemaspaandra, and L. Torenvliet,
in Complexity, Logic and Recursion Theory,
ed. A. Sorbi, Marcel Dekker, Inc.,
to appear.
Complexity Classes, L. Hemaspaandra,
section in Handbook of Discrete and Combinatorial Mathematics,
ed. K. Rosen,
CRC Press, to appear.
Promises and Fault-Tolerant Database Access,
J. Cai, L. Hemachandra, and J. Vyskoc,
in Complexity Theory: Current Research,
eds. K. Ambos-Spies, S. Homer, and U. Schöning,
Cambridge University Press, pp. 101-146, 1993.
Reductions to Sets of Low Information
Content,
V. Arvind, Y. Han, L. Hemachandra, J. Köbler,
A. Lozano, M. Mundhenk, M. Ogiwara, U. Schöning,
R. Silvestri, and T. Thierauf,
in Complexity Theory: Current Research,
eds. K. Ambos-Spies, S. Homer, and U. Schöning,
Cambridge University Press, pp. 1-45, 1993.
Is #P Closed Under Subtraction?,
L. Hemachandra and M. Ogiwara,
in Current Trends in Theoretical Computer Science: Essays and
Tutorials,
eds. G. Rozenberg and A. Salomaa,
World Scientific Press, pp. 523-536, 1993.
REFEREED JOURNAL PUBLICATIONS
Easy Sets and Hard Certificate Schemes,
L. Hemaspaandra, J. Rothe, and G. Wechsung,
Acta Informatica,
accepted subject to minor revision.
Logspace Reducibility: Models
and Equivalences, L. Hemaspaandra and Z. Jiang,
International Journal of Foundations of Computer Science,
accepted subject to minor revision.
Query Order,
L. Hemaspaandra, H. Hempel, and G. Wechsung,
to appear in
SIAM Journal on Computing.
Threshold Computation and Cryptographic Security,
Y. Han, L. Hemaspaandra, and T. Thierauf,
to appear in
SIAM Journal on Computing.
Unambiguous Computation: Boolean Hierarchies and Sparse
Turing-Complete Sets, L. Hemaspaandra and J. Rothe,
to appear in
SIAM Journal on Computing.
Pseudorandom Generators and the Frequency of Simplicity,
Y. Han and L. Hemaspaandra,
Journal of Cryptology,
V. 9, #4, pp. 251-262, Autumn 1996.
Strong Self-Reducibility Precludes Strong Immunity,
L. Hemaspaandra and M. Zimand,
Mathematical Systems Theory,
V. 29, #5, pp. 535-548,
September/October 1996.
Computing Solutions Uniquely Collapses the Polynomial Hierarchy,
L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman,
SIAM Journal on Computing, V. 25, #4, pp. 697-708,
August 1996.
Reducibility Classes of P-Selective Sets,
L. Hemaspaandra, A. Hoene, and M. Ogihara,
Theoretical Computer Science, V. 155, #2, pp. 447-457,
March 1996.
Optimal Advice,
L. Hemaspaandra and L. Torenvliet,
Theoretical Computer Science, V. 154, #2, pp. 367-377,
February 1996.
Nondeterministically Selective Sets,
L. Hemaspaandra, A. Hoene, A. Naik,
M. Ogihara, A. Selman, T. Thierauf, and
J. Wang,
International Journal of Foundations of Computer Science,
V. 6, #4, pp. 403-416, December 1995.
Defying Upward and Downward Separation,
L. Hemaspaandra and S. Jha,
Information and Computation, V. 121, #1, pp. 1-13,
August 1995.
Easily Checked Generalized Self-Reducibility,
L. Hemaspaandra and R. Silvestri,
SIAM Journal on Computing, V. 24, #4, pp. 840-858,
August
1995.
P-Selectivity: Intersections and Indices,
L. Hemaspaandra and Z. Jiang,
Theoretical Computer Science, V. 145, #1-2, pp. 371-380, 1995.
Space-Efficient Recognition
of Sparse Self-Reducible Languages,
L. Hemaspaandra, M. Ogihara, and S. Toda,
Computational Complexity, V. 4, #3, pp. 262-296,
1994.
On the Complexity of Graph Reconstruction,
D. Kratsch and L. Hemaspaandra,
Mathematical Systems Theory,
V. 27, #3, pp. 257-273, May/June 1994.
Quasi-Injective Reductions,
E. Hemaspaandra and L. Hemaspaandra,
Theoretical Computer Science, V. 123, #2, pp. 407-413,
January 1994.
Banishing Robust Turing Completeness,
L. Hemaspaandra, S. Jain, and N. Vereshchagin,
International Journal of Foundations of Computer Science,
V. 4, #3, pp. 245-265, 1993.
On Checking Versus Evaluation of Multiple
Queries, W. Gasarch, L. Hemachandra,
and A. Hoene,
Information and Computation,
V. 105, #1, pp. 72-93, July 1993.
A Complexity Theory for Feasible Closure
Properties,
M. Ogiwara and L. Hemachandra,
Journal of Computer and System Sciences,
V. 46, #3, pp. 295-325, June 1993.
Collapsing Degrees Via Strong Computation,
L. Hemachandra and A. Hoene,
Journal of Computer and System Sciences,
V. 46, #3, pp. 363-380, June 1993.
Using Inductive Counting to Simulate Nondeterministic
Computation, G. Buntrock, L. Hemachandra,
and D. Siefkes,
Information and Computation,
V. 102, #1, pp. 102-117, 1993.
Polynomial-Time Compression,
J. Goldsmith, L. Hemachandra, and K. Kunen,
Computational Complexity,
V. 2, #1, pp. 18-39, 1992.
Relating Equivalence and Reducibility to
Sparse Sets, E. Allender,
L. Hemachandra, M. Ogiwara, and O. Watanabe,
SIAM Journal on Computing,
V. 21, #3, pp. 521-539,
June 1992.
Lower
Bounds for the Low Hierarchy,
E. Allender and L. Hemachandra,
Journal of the ACM, V. 39, #1, pp. 234-250,
January 1992.
Separating Complexity
Classes with Tally Oracles, L. Hemachandra and
R. Rubinstein,
Theoretical Computer Science, V. 92, #2, pp. 309-318,
January 1992.
Simultaneous Strong Separations of
Probabilistic and Unambiguous Complexity Classes,
D. Eppstein, L. Hemachandra,
J. Tisdall, and B. Yener,
Mathematical Systems Theory, V. 25, #1, pp. 23-36, 1992.
On Sets With Efficient Implicit Membership Tests, L. Hemachandra
and A. Hoene,
SIAM Journal on Computing, V. 20, #6, pp. 1148-1156,
December 1991.
On the Limitations of Locally Robust Positive
Reductions, L. Hemachandra and S. Jain,
International Journal of Foundations of Computer Science,
V. 2, #3, pp. 237-255, September 1991.
Near-Testable Sets,
J. Goldsmith, L. Hemachandra, D. Joseph, and P. Young,
SIAM Journal on Computing,
V. 20, #3, pp. 506-523, June 1991.
Kolmogorov Characterizations of Complexity Classes,
L. Hemachandra and G. Wechsung,
Theoretical Computer Science, V. 83, #2,
pp. 313-322,
June 1991.
A Note on Enumerative Counting,
J. Cai and L. Hemachandra,
Information Processing Letters, V. 38, #4,
pp. 215-219, May 1991.
One-Way Functions
and the Non-Isomorphism of NP-Complete Sets,
J. Hartmanis and L. Hemachandra,
Theoretical Computer Science, V. 81, #1, pp. 155-163,
April 1991.
On Sets Polynomially Enumerable By Iteration,
L. Hemachandra, A. Hoene, D. Siefkes, and P. Young,
Theoretical Computer Science, V. 80, #2,
pp. 203-225, March 1991.
Probabilistic
Polynomial Time is Closed Under
Parity Reductions,
R. Beigel, L. Hemachandra, and G. Wechsung,
Information Processing Letters, V. 37, #2,
pp. 91-94, January 1991.
On the Complexity of Ranking,
L. Hemachandra and S. Rudich,
Journal of Computer and System Sciences,
V. 41,
#2, pp. 251-271, October 1990.
Robust Machines Accept Easy Sets,
J. Hartmanis and L. Hemachandra,
Theoretical Computer Science,
V. 74, #2, pp. 217-226,
August 1990.
On the Power of Parity Polynomial Time,
J. Cai and L. Hemachandra,
Mathematical Systems Theory,
V. 23, #2, pp. 95-106, 1990.
The Strong Exponential
Hierarchy Collapses, L. Hemachandra,
Journal of Computer and System Sciences,
V. 39, #3, pp. 299-322, December 1989.
Enumerative Counting is Hard,
J. Cai and L. Hemachandra,
Information and Computation,
V. 92, #1,
pp. 34-44, July 1989.
The Boolean Hierarchy II: Applications,
J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner,
and G. Wechsung,
SIAM Journal on Computing, V. 18, #1,
pp. 95-111, February 1989.
The Boolean Hierarchy I: Structural Properties,
J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner,
and G. Wechsung,
SIAM Journal on
Computing, V. 17, #6, pp. 1232-1252, December 1988.
On Sparse Oracles Separating Feasible Complexity Classes,
J. Hartmanis and L. Hemachandra,
Information Processing Letters, V. 28, pp. 291-295,
August 1988.
Complexity Classes Without Machines: On Complete Languages
for UP, J. Hartmanis and L. Hemachandra,
Theoretical Computer Science, V. 58, pp. 129-142, 1988.
Using Simulated Annealing to Design Good Codes, A. El Gamel,
L. Hemachandra, I. Shperling, and V. Wei,
IEEE Transactions on Information Theory,
V. IT-33, #1, pp. 116-123, January 1987.