Larry J. Stockmeyer
According to our database^{1}, Larry J. Stockmeyer
Awards
ACM Fellow
ACM Fellow 1996, "For several fundamental contributions to computational complexity theory, which have significantly affected the course of this field.".
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at dl.acm.org
On csauthors.net:
Bibliography
2006
An Architecture for Provably Secure Computation.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006
2004
A New Approach to FaultTolerant Wormhole Routing for MeshConnected Parallel Computers.
IEEE Trans. Computers, 2004
2003
InPlace Reconstruction of Version Differences.
IEEE Trans. Knowl. Data Eng., 2003
Magic Functions.
J. ACM, 2003
2002
Links between complexity theory and constrained block coding.
IEEE Trans. Information Theory, 2002
Cosmological lower bound on the circuit complexity of a small problem in logic.
J. ACM, 2002
Compactly encoding unstructured inputs with differential compression.
J. ACM, 2002
2round zero knowledge and proof auditors.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
A New Approach to FaultTolerant Wormhole Routing for MeshConnected Parallel Computers.
Proceedings of the 16th International Parallel and Distributed Processing Symposium (IPDPS 2002), 2002
2001
Scalable Session Locking for a Distributed File System.
Cluster Computing, 2001
Links Between Complexity Theory and Constrained Block Coding.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001
2000
The Closure of Monadic NP.
J. Comput. Syst. Sci., 2000
1999
Magic Functions.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999
1998
Relaxing the Triangle Inequality in Pattern Matching.
International Journal of Computer Vision, 1998
The Closure of Monadic NP (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Declustered Disk Array Architectures with Optimal and NearOptimal Parallelism.
Proceedings of the 25th Annual International Symposium on Computer Architecture, 1998
1996
The Complexity of PDL with Interleaving.
Theor. Comput. Sci., 1996
Efficiently Extendible Mappings for Balanced Data Distribution.
Algorithmica, 1996
1995
On Monadic NP vs. Monadic coNP
Inf. Comput., July, 1995
What Can be Computed Locally?
SIAM J. Comput., 1995
Local Computations on Static and Dynamic Graphs (Preliminary Version).
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995
1994
The Complexity of Word Problems  This Time with Interleaving
Inf. Comput., December, 1994
Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling.
Theor. Comput. Sci., 1994
Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty.
J. ACM, 1994
1993
What can be computed locally?
Proceedings of the TwentyFifth Annual ACM Symposium on Theory of Computing, 1993
On Monadic NP vs. Monadic coNP (Extended Abstract).
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993
1992
Finite State Verifiers II: Zero Knowledge.
J. ACM, 1992
Finite State Verifiers I: The Power of Interaction.
J. ACM, 1992
Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
1991
Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991
1990
Flipping Persuasively in Constant Time.
SIAM J. Comput., 1990
A Time Complexity Gap for TwoWay Probabilistic FiniteState Automata.
SIAM J. Comput., 1990
1989
The Distributed Firing Squad Problem.
SIAM J. Comput., 1989
On the Power of 2Way Probabilistic Finite State Automata (Extended Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989
1988
Parallel Algorithms for Term Matching.
SIAM J. Comput., 1988
Consensus in the presence of partial synchrony.
J. ACM, 1988
ZeroKnowledge With Finite State Verifiers.
Proceedings of the Advances in Cryptology, 1988
1987
Classifying the Computational Complexity of Problems.
J. Symb. Log., 1987
On the minimal synchronism needed for distributed consensus.
J. ACM, 1987
1986
Flipping Persuasively in Constant Expected Time (Preliminary Version)
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986
Parallel Algorithms for Term Matching.
Proceedings of the 8th International Conference on Automated Deduction, Oxford, England, July 27, 1986
1985
BoundedDepth, PolynomialSize Circuits for Symmetric Functions.
Theor. Comput. Sci., 1985
On Approximation Algorithms for #P.
SIAM J. Comput., 1985
Pseudorandom Number Generation and Space Complexity
Information and Control, 1985
Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985
The Distributed Firing Squad Problem (Preliminary Version)
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985
The Complexity of Backtrack Searches (Preliminary Version)
Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985
1984
Simulation of Parallel Random Access Machines by Circuits.
SIAM J. Comput., 1984
Alternating Pushdown and Stack Automata.
SIAM J. Comput., 1984
Constant Depth Reducibility.
SIAM J. Comput., 1984
Solving NPHard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems.
J. ACM, 1984
Alternation Bounded Auxiliary Pushdown Automata
Information and Control, 1984
Consensus in the Presence of Partial Synchrony (Preliminary Version).
Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, 1984
1983
Optimal Orientations of Cells in Slicing Floorplan Designs
Information and Control, 1983
The Complexity of Approximate Counting (Preliminary Version)
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983
On the Minimal Synchronism Needed for Distributed Consensus
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983
Pseudorandom Number Generation and Space Complexity.
Proceedings of the Fundamentals of Computation Theory, 1983
1982
A Dictionary Machine (for VLSI).
IEEE Trans. Computers, 1982
NPCompleteness of Some Generalizations of the Maximum Matching Problem.
Inf. Process. Lett., 1982
A Complexity Theory for Unbounded FanIn Parallelism
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982
1981
Alternation.
J. ACM, 1981
1980
Uniform Data Encodings.
Theor. Comput. Sci., 1980
1979
On the Number of Comparisons to Find the Intersection of Two Relations.
SIAM J. Comput., 1979
Provably Difficult Combinatorial Games.
SIAM J. Comput., 1979
1978
Evaluation of Polynomials with SuperPreconditioning.
J. Comput. Syst. Sci., 1978
Covering Edges by Cliques with Regard to Keyword Conflicts and Intersection Graphs.
Commun. ACM, 1978
Alternating Pushdown Automata (Preliminary Report)
Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978
1977
On the Combinational Complexity of Certain Symmetric Boolean Functions.
Mathematical Systems Theory, 1977
Hashing Schemes for Extendible Arrays.
J. ACM, 1977
Storage Schemes for Boundedly Extendible Arrays.
Acta Inf., 1977
1976
The PolynomialTime Hierarchy.
Theor. Comput. Sci., 1976
Some Simplified NPComplete Graph Problems.
Theor. Comput. Sci., 1976
A Characterization of the Power of Vector Machines.
J. Comput. Syst. Sci., 1976
Evaluation of Polynomials with SuperPreconditioning
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976
Alternation
Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976
1975
Hashing Schemes for Extendible Arrays (Extended Arrays)
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975
1974
Fast OnLine Integer Multiplication.
J. Comput. Syst. Sci., 1974
A Characterization of the Power of Vector Machines
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974
Some Simplified NPComplete Problems
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974
1973
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials.
SIAM J. Comput., 1973
Word Problems Requiring Exponential Time: Preliminary Report
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30, 1973
Fast OnLine Integer Multiplication
Proceedings of the 5th Annual ACM Symposium on Theory of Computing, April 30, 1973
1972
The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space
Proceedings of the 13th Annual Symposium on Switching and Automata Theory, 1972
1971
Bounds on the Evaluation Time for Rational Polynomials
Proceedings of the 12th Annual Symposium on Switching and Automata Theory, 1971