Larry J. Stockmeyer

According to our database1, Larry J. Stockmeyer
  • authored at least 84 papers between 1971 and 2006.
  • has a "Dijkstra number"2 of three.

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 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2006
An Architecture for Provably Secure Computation.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

2004
A New Approach to Fault-Tolerant Wormhole Routing for Mesh-Connected Parallel Computers.
IEEE Trans. Computers, 2004

2003
In-Place 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

2-round zero knowledge and proof auditors.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

A New Approach to Fault-Tolerant Wormhole Routing for Mesh-Connected 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 Near-Optimal 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 co-NP
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 Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

On Monadic NP vs. Monadic co-NP (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 Two-Way Probabilistic Finite-State Automata.
SIAM J. Comput., 1990

1989
The Distributed Firing Squad Problem.
SIAM J. Comput., 1989

On the Power of 2-Way 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

Zero-Knowledge 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
Bounded-Depth, Polynomial-Size 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 NP-Hard 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

NP-Completeness of Some Generalizations of the Maximum Matching Problem.
Inf. Process. Lett., 1982

A Complexity Theory for Unbounded Fan-In 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 Super-Preconditioning.
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 Polynomial-Time Hierarchy.
Theor. Comput. Sci., 1976

Some Simplified NP-Complete Graph Problems.
Theor. Comput. Sci., 1976

A Characterization of the Power of Vector Machines.
J. Comput. Syst. Sci., 1976

Evaluation of Polynomials with Super-Preconditioning
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 On-Line 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 NP-Complete 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 On-Line 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


  Loading...