Larry Stockmeyer's home page

Larry Stockmeyer died in 2004. This is an archive of his homepage as it existed at the time.

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

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