Larry J. Stockmeyer

According to our database, Larry J. Stockmeyer authored at least 76 papers between 1971 and 2006.

Collaborative distances:

• Dijkstra number of two.
• Erdős number of two.

2006

An Architecture for Provably Secure Computation.

Miklós Ajtai, Cynthia Dwork, Larry J. Stockmeyer

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

2004

A New Approach to Fault-Tolerant Wormhole Routing for Mesh-Connected Parallel Computers.

Ching-Tien Ho, Larry J. Stockmeyer

IEEE Trans. Computers, 2004

2003

In-Place Reconstruction of Version Differences.

Randal C. Burns, Larry J. Stockmeyer, Darrell D. E. Long

IEEE Trans. Knowl. Data Eng., 2003

Magic Functions.

Cynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer

J. ACM, 2003

2002

Links between complexity theory and constrained block coding.

Larry J. Stockmeyer, Dharmendra S. Modha

IEEE Trans. Inf. Theory, 2002

Cosmological lower bound on the circuit complexity of a small problem in logic.

Larry J. Stockmeyer, Albert R. Meyer

J. ACM, 2002

Compactly encoding unstructured inputs with differential compression.

Miklós Ajtai, Randal C. Burns, Ronald Fagin, Darrell D. E. Long, Larry J. Stockmeyer

J. ACM, 2002

2-round zero knowledge and proof auditors.

Cynthia Dwork, Larry J. Stockmeyer

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

Scalable Session Locking for a Distributed File System.

Randal C. Burns, Robert M. Rees, Larry J. Stockmeyer, Darrell D. E. Long

Clust. Comput., 2001

2000

The Closure of Monadic NP.

Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer

J. Comput. Syst. Sci., 2000

1998

Relaxing the Triangle Inequality in Pattern Matching.

Ronald Fagin, Larry J. Stockmeyer

Int. J. Comput. Vis., 1998

The Closure of Monadic NP (Extended Abstract).

Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Declustered Disk Array Architectures with Optimal and Near-Optimal Parallelism.

Guillermo A. Alvarez, Walter A. Burkhard, Larry J. Stockmeyer, Flaviu Cristian

Proceedings of the 25th Annual International Symposium on Computer Architecture, 1998

1996

The Complexity of PDL with Interleaving.

Alain J. Mayer, Larry J. Stockmeyer

Theor. Comput. Sci., 1996

Efficiently Extendible Mappings for Balanced Data Distribution.

David M. Choy, Ronald Fagin, Larry J. Stockmeyer

Algorithmica, 1996

1995

On Monadic NP vs. Monadic co-NP

Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi

Inf. Comput., July, 1995

What Can be Computed Locally?

Moni Naor, Larry J. Stockmeyer

SIAM J. Comput., 1995

Local Computations on Static and Dynamic Graphs (Preliminary Version).

Alain J. Mayer, Moni Naor, Larry J. Stockmeyer

Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

1994

The Complexity of Word Problems - This Time with Interleaving

Alain J. Mayer, Larry J. Stockmeyer

Inf. Comput., December, 1994

Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling.

Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer

Theor. Comput. Sci., 1994

Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty.

Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer

J. ACM, 1994

1993

On Monadic NP vs. Monadic co-NP (Extended Abstract).

Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

Finite State Verifiers II: Zero Knowledge.

Cynthia Dwork, Larry J. Stockmeyer

J. ACM, 1992

Finite State Verifiers I: The Power of Interaction.

Cynthia Dwork, Larry J. Stockmeyer

J. ACM, 1992

Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract)

Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1990

Flipping Persuasively in Constant Time.

Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer

SIAM J. Comput., 1990

A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata.

Cynthia Dwork, Larry J. Stockmeyer

SIAM J. Comput., 1990

1989

The Distributed Firing Squad Problem.

Brian A. Coan, Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer

SIAM J. Comput., 1989

On the Power of 2-Way Probabilistic Finite State Automata (Extended Abstract)

Cynthia Dwork, Larry J. Stockmeyer

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.

Cynthia Dwork, Paris C. Kanellakis, Larry J. Stockmeyer

SIAM J. Comput., 1988

Consensus in the presence of partial synchrony.

Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer

J. ACM, 1988

Zero-Knowledge With Finite State Verifiers.

Cynthia Dwork, Larry J. Stockmeyer

Proceedings of the Advances in Cryptology, 1988

1987

Classifying the Computational Complexity of Problems.

Larry J. Stockmeyer

J. Symb. Log., 1987

On the minimal synchronism needed for distributed consensus.

Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer

J. ACM, 1987

1986

Flipping Persuasively in Constant Expected Time (Preliminary Version)

Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985

Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions.

Ronald Fagin, Maria M. Klawe, Nicholas Pippenger, Larry J. Stockmeyer

Theor. Comput. Sci., 1985

On Approximation Algorithms for #P.

Larry J. Stockmeyer

SIAM J. Comput., 1985

Pseudorandom Number Generation and Space Complexity

Merrick L. Furst, Richard J. Lipton, Larry J. Stockmeyer

Inf. Control., 1985

Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report

Moshe Y. Vardi, Larry J. Stockmeyer

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

The Distributed Firing Squad Problem (Preliminary Version)

Brian A. Coan, Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

The Complexity of Backtrack Searches (Preliminary Version)

Larry Carter, Larry J. Stockmeyer, Mark N. Wegman

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

1984

Simulation of Parallel Random Access Machines by Circuits.

Larry J. Stockmeyer, Uzi Vishkin

SIAM J. Comput., 1984

Alternating Pushdown and Stack Automata.

Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer

SIAM J. Comput., 1984

Constant Depth Reducibility.

Ashok K. Chandra, Larry J. Stockmeyer, Uzi Vishkin

SIAM J. Comput., 1984

Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems.

Yuri Gurevich, Larry J. Stockmeyer, Uzi Vishkin

J. ACM, 1984

Alternation Bounded Auxiliary Pushdown Automata

Richard E. Ladner, Larry J. Stockmeyer, Richard J. Lipton

Inf. Control., 1984

Consensus in the Presence of Partial Synchrony (Preliminary Version).

Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer

Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, 1984

1983

Optimal Orientations of Cells in Slicing Floorplan Designs

Larry J. Stockmeyer

Inf. Control., 1983

The Complexity of Approximate Counting (Preliminary Version)

Larry J. Stockmeyer

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982

A Dictionary Machine (for VLSI).

Thomas Ottmann, Arnold L. Rosenberg, Larry J. Stockmeyer

IEEE Trans. Computers, 1982

NP-Completeness of Some Generalizations of the Maximum Matching Problem.

Larry J. Stockmeyer, Vijay V. Vazirani

Inf. Process. Lett., 1982

A Complexity Theory for Unbounded Fan-In Parallelism

Ashok K. Chandra, Larry J. Stockmeyer, Uzi Vishkin

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981

Alternation.

Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer

J. ACM, 1981

1980

Uniform Data Encodings.

Arnold L. Rosenberg, Larry J. Stockmeyer, Lawrence Snyder

Theor. Comput. Sci., 1980

1979

On the Number of Comparisons to Find the Intersection of Two Relations.

Larry J. Stockmeyer, C. K. Wong

SIAM J. Comput., 1979

Provably Difficult Combinatorial Games.

Larry J. Stockmeyer, Ashok K. Chandra

SIAM J. Comput., 1979

1978

Evaluation of Polynomials with Super-Preconditioning.

Richard J. Lipton, Larry J. Stockmeyer

J. Comput. Syst. Sci., 1978

Covering Edges by Cliques with Regard to Keyword Conflicts and Intersection Graphs.

Lawrence T. Kou, Larry J. Stockmeyer, C. K. Wong

Commun. ACM, 1978

Alternating Pushdown Automata (Preliminary Report)

Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer

Proceedings of the 19th Annual Symposium on Foundations of Computer Science, 1978

1977

On the Combinational Complexity of Certain Symmetric Boolean Functions.

Larry J. Stockmeyer

Math. Syst. Theory, 1977

Hashing Schemes for Extendible Arrays.

Arnold L. Rosenberg, Larry J. Stockmeyer

J. ACM, 1977

Storage Schemes for Boundedly Extendible Arrays.

Arnold L. Rosenberg, Larry J. Stockmeyer

Acta Informatica, 1977

1976

The Polynomial-Time Hierarchy.

Larry J. Stockmeyer

Theor. Comput. Sci., 1976

Some Simplified NP-Complete Graph Problems.

M. R. Garey, David S. Johnson, Larry J. Stockmeyer

Theor. Comput. Sci., 1976

A Characterization of the Power of Vector Machines.

Vaughan R. Pratt, Larry J. Stockmeyer

J. Comput. Syst. Sci., 1976

Alternation

Ashok K. Chandra, Larry J. Stockmeyer

Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

1975

Hashing Schemes for Extendible Arrays (Extended Arrays)

Arnold L. Rosenberg, Larry J. Stockmeyer

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

1974

The complexity of decision problems in automata theory and logic.

Larry J. Stockmeyer

PhD thesis, 1974

Fast On-Line Integer Multiplication.

Michael J. Fischer, Larry J. Stockmeyer

J. Comput. Syst. Sci., 1974

A Characterization of the Power of Vector Machines

Vaughan R. Pratt, Michael O. Rabin, Larry J. Stockmeyer

Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

Some Simplified NP-Complete Problems

M. R. Garey, David S. Johnson, Larry J. Stockmeyer

Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

1973

Planar 3-colorability is polynomial complete.

Larry J. Stockmeyer

SIGACT News, 1973

On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials.

Mike Paterson, Larry J. Stockmeyer

SIAM J. Comput., 1973

Word Problems Requiring Exponential Time: Preliminary Report

Larry J. Stockmeyer, Albert R. Meyer

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

Albert R. Meyer, Larry J. Stockmeyer

Proceedings of the 13th Annual Symposium on Switching and Automata Theory, 1972

1971

Bounds on the Evaluation Time for Rational Polynomials

Mike Paterson, Larry J. Stockmeyer

Proceedings of the 12th Annual Symposium on Switching and Automata Theory, 1971