Larry Stockmeyer's Home Page

Email: stock@acm.org

Research Interests

Computational complexity
Interactive proof systems
Parallel and distributed computing
Storage systems

More Information

Recent papers
Computational complexity
Interactive proof systems
Parallel and distributed computing
Storage systems
Additional online publications
Survey papers
Brief biography


Recent Papers

Computational Complexity

Cosmological lower bound on the circuit complexity of a small problem in logic, L. Stockmeyer and A. R. Meyer, J. ACM 49 (2002), pp. 753-784.
[ps] [abstract]

Links between complexity theory and constrained block coding, L. Stockmeyer and D. S. Modha, IEEE Trans. on Information Theory 48, 1 (2002), pp. 59-88.
[pdf] [abstract]

The closure of monadic NP, M. Ajtai, R. Fagin, and L. Stockmeyer, J. Comput. System Sci. 60 (2000), pp. 660-716.
[pdf] [abstract]

Interactive Proof Systems

2-round zero knowledge and proof auditors, C. Dwork and L. Stockmeyer. Extended abstract appears in Proc. 34th ACM Symp. on Theory of Computing, May 2002.
[ps] [abstract]

Magic functions, C. Dwork, M. Naor, O. Reingold, and L. Stockmeyer, J. ACM 50 (2003), pp. 852-921.
[ps] [abstract]

Parallel and Distributed Computing

A new approach to fault-tolerant wormhole routing for mesh-connected parallel computers, C.-T. Ho and L. Stockmeyer, IEEE Trans. on Computers, to appear. Full version, IBM Research Report RJ 10265, Nov. 2002; revised Sept. 2003.
[ps] [abstract]

Storage Systems

In-place reconstruction of version differences, R. Burns, L. Stockmeyer, and D. D. E. Long, IEEE Trans. on Knowledge and Data Engineering, 15, 4 (2003), pp. 973-984.
[pdf] [abstract]

Compactly encoding unstructured inputs with differential compression, M. Ajtai, R. C. Burns, R. Fagin, D. D. E. Long, and L. Stockmeyer, J. ACM 49 (2002), pp. 318-367.
[pdf] [abstract]

Scalable session locking for a distributed file system, R. C. Burns, R. M. Rees, L. J. Stockmeyer, and D. D. E. Long, Cluster Computing 4 (2001), pp. 295-306.
[ps] [abstract]

Simulations of the age-threshold and fitness free space collection algorithms on a long trace, L. Stockmeyer, IBM Research Report RJ10222, Oct. 2001.
[ps] [abstract]

Survey Papers

Computational complexity, L. Stockmeyer, in: Handbooks in Operations Research and Management Science, Volume 3, Computing, E.G. Coffman, Jr., J.K. Lenstra, and A.H.G. Rinnooy Kan, eds., North-Holland, 1992, pp. 455-517.

Classifying the computational complexity of problems, L. Stockmeyer, J. Symbolic Logic 52 (1987), pp. 1-43.
[pdf] [table of contents]

Intrinsically difficult problems, L. J. Stockmeyer and A. K. Chandra, Scientific American 240 (May, 1979), pp. 140-159; reprinted in Trends in Computing, Scientific American Inc., 1988, pp. 88-97.


Last modified: January 8, 2004 1