Larry J. Stockmeyer

Publication Activity (10 Years)

Years Active: 1971-2006
Publications (10 Years): 0

Publications

Miklós Ajtai, Cynthia Dwork, Larry J. Stockmeyer
An Architecture for Provably Secure Computation. LATIN (2006)
Ching-Tien Ho, Larry J. Stockmeyer
A New Approach to Fault-Tolerant Wormhole Routing for Mesh-Connected Parallel Computers. IEEE Trans. Computers 53 (4) (2004)
Cynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer
Magic Functions. J. ACM 50 (6) (2003)
Randal C. Burns, Larry J. Stockmeyer, Darrell D. E. Long
In-Place Reconstruction of Version Differences. IEEE Trans. Knowl. Data Eng. 15 (4) (2003)
Miklós Ajtai, Randal C. Burns, Ronald Fagin, Darrell D. E. Long, Larry J. Stockmeyer
Compactly encoding unstructured inputs with differential compression. J. ACM 49 (3) (2002)
Larry J. Stockmeyer, Dharmendra S. Modha
Links between complexity theory and constrained block coding. IEEE Trans. Inf. Theory 48 (1) (2002)
Ching-Tien Ho, Larry J. Stockmeyer
A New Approach to Fault-Tolerant Wormhole Routing for Mesh-Connected Parallel Computers. IPDPS (2002)
Larry J. Stockmeyer, Albert R. Meyer
Cosmological lower bound on the circuit complexity of a small problem in logic. J. ACM 49 (6) (2002)
Cynthia Dwork, Larry J. Stockmeyer
2-round zero knowledge and proof auditors. STOC (2002)
Larry J. Stockmeyer, Dharmendra S. Modha
Links Between Complexity Theory and Constrained Block Coding. Computational Complexity Conference (2001)
Randal C. Burns, Robert M. Rees, Larry J. Stockmeyer, Darrell D. E. Long
Scalable Session Locking for a Distributed File System. Clust. Comput. 4 (4) (2001)
Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer
The Closure of Monadic NP. J. Comput. Syst. Sci. 60 (3) (2000)
Cynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer
Magic Functions. FOCS (1999)
Guillermo A. Alvarez, Walter A. Burkhard, Larry J. Stockmeyer, Flaviu Cristian
Declustered Disk Array Architectures with Optimal and Near-Optimal Parallelism. ISCA (1998)
Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer
The Closure of Monadic NP (Extended Abstract). STOC (1998)
Ronald Fagin, Larry J. Stockmeyer
Relaxing the Triangle Inequality in Pattern Matching. Int. J. Comput. Vis. 30 (3) (1998)
Alain J. Mayer, Larry J. Stockmeyer
The Complexity of PDL with Interleaving. Theor. Comput. Sci. 161 (1&2) (1996)
David M. Choy, Ronald Fagin, Larry J. Stockmeyer
Efficiently Extendible Mappings for Balanced Data Distribution. Algorithmica 16 (2) (1996)
Alain J. Mayer, Moni Naor, Larry J. Stockmeyer
Local Computations on Static and Dynamic Graphs (Preliminary Version). ISTCS (1995)
Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi
On Monadic NP vs. Monadic co-NP Inf. Comput. 120 (1) (1995)
Moni Naor, Larry J. Stockmeyer
What Can be Computed Locally? SIAM J. Comput. 24 (6) (1995)
Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer
Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty. J. ACM 41 (1) (1994)
Alain J. Mayer, Larry J. Stockmeyer
The Complexity of Word Problems - This Time with Interleaving Inf. Comput. 115 (2) (1994)
Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer
Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling. Theor. Comput. Sci. 130 (1) (1994)
Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi
On Monadic NP vs. Monadic co-NP (Extended Abstract). Computational Complexity Conference (1993)
Moni Naor, Larry J. Stockmeyer
What can be computed locally? STOC (1993)
Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer
Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract) FOCS (1992)
Cynthia Dwork, Larry J. Stockmeyer
Finite State Verifiers II: Zero Knowledge. J. ACM 39 (4) (1992)
Cynthia Dwork, Larry J. Stockmeyer
Finite State Verifiers I: The Power of Interaction. J. ACM 39 (4) (1992)
Hagit Attiya, Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer
Bounds on the Time to Reach Agreement in the Presence of Timing Uncertainty STOC (1991)
Cynthia Dwork, Larry J. Stockmeyer
A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata. SIAM J. Comput. 19 (6) (1990)
Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer
Flipping Persuasively in Constant Time. SIAM J. Comput. 19 (3) (1990)
Brian A. Coan, Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer
The Distributed Firing Squad Problem. SIAM J. Comput. 18 (5) (1989)
Cynthia Dwork, Larry J. Stockmeyer
On the Power of 2-Way Probabilistic Finite State Automata (Extended Abstract) FOCS (1989)
Cynthia Dwork, Larry J. Stockmeyer
Zero-Knowledge With Finite State Verifiers. CRYPTO (1988)
Cynthia Dwork, Paris C. Kanellakis, Larry J. Stockmeyer
Parallel Algorithms for Term Matching. SIAM J. Comput. 17 (4) (1988)
Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer
Consensus in the presence of partial synchrony. J. ACM 35 (2) (1988)
Larry J. Stockmeyer
Classifying the Computational Complexity of Problems. J. Symb. Log. 52 (1) (1987)
Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer
On the minimal synchronism needed for distributed consensus. J. ACM 34 (1) (1987)
Cynthia Dwork, Paris C. Kanellakis, Larry J. Stockmeyer
Parallel Algorithms for Term Matching. CADE (1986)
Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer
Flipping Persuasively in Constant Expected Time (Preliminary Version) FOCS (1986)
Merrick L. Furst, Richard J. Lipton, Larry J. Stockmeyer
Pseudorandom Number Generation and Space Complexity Inf. Control. 64 (1-3) (1985)
Ronald Fagin, Maria M. Klawe, Nicholas Pippenger, Larry J. Stockmeyer
Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions. Theor. Comput. Sci. 36 (1985)
Brian A. Coan, Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer
The Distributed Firing Squad Problem (Preliminary Version) STOC (1985)
Moshe Y. Vardi, Larry J. Stockmeyer
Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report STOC (1985)
Larry Carter, Larry J. Stockmeyer, Mark N. Wegman
The Complexity of Backtrack Searches (Preliminary Version) STOC (1985)
Larry J. Stockmeyer
On Approximation Algorithms for #P. SIAM J. Comput. 14 (4) (1985)
Larry J. Stockmeyer, Uzi Vishkin
Simulation of Parallel Random Access Machines by Circuits. SIAM J. Comput. 13 (2) (1984)
Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer
Consensus in the Presence of Partial Synchrony (Preliminary Version). PODC (1984)
Yuri Gurevich, Larry J. Stockmeyer, Uzi Vishkin
Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems. J. ACM 31 (3) (1984)
Richard E. Ladner, Larry J. Stockmeyer, Richard J. Lipton
Alternation Bounded Auxiliary Pushdown Automata Inf. Control. 62 (2/3) (1984)
Ashok K. Chandra, Larry J. Stockmeyer, Uzi Vishkin
Constant Depth Reducibility. SIAM J. Comput. 13 (2) (1984)
Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer
Alternating Pushdown and Stack Automata. SIAM J. Comput. 13 (1) (1984)
Merrick L. Furst, Richard J. Lipton, Larry J. Stockmeyer
Pseudorandom Number Generation and Space Complexity. FCT (1983)
Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer
On the Minimal Synchronism Needed for Distributed Consensus FOCS (1983)
Larry J. Stockmeyer
Optimal Orientations of Cells in Slicing Floorplan Designs Inf. Control. 57 (2/3) (1983)
Larry J. Stockmeyer
The Complexity of Approximate Counting (Preliminary Version) STOC (1983)
Larry J. Stockmeyer, Vijay V. Vazirani
NP-Completeness of Some Generalizations of the Maximum Matching Problem. Inf. Process. Lett. 15 (1) (1982)
Thomas Ottmann, Arnold L. Rosenberg, Larry J. Stockmeyer
A Dictionary Machine (for VLSI). IEEE Trans. Computers 31 (9) (1982)
Ashok K. Chandra, Larry J. Stockmeyer, Uzi Vishkin
A Complexity Theory for Unbounded Fan-In Parallelism FOCS (1982)
Ashok K. Chandra, Dexter Kozen, Larry J. Stockmeyer
Alternation. J. ACM 28 (1) (1981)
Arnold L. Rosenberg, Larry J. Stockmeyer, Lawrence Snyder
Uniform Data Encodings. Theor. Comput. Sci. 11 (1980)
Larry J. Stockmeyer, Ashok K. Chandra
Provably Difficult Combinatorial Games. SIAM J. Comput. 8 (2) (1979)
Larry J. Stockmeyer, C. K. Wong
On the Number of Comparisons to Find the Intersection of Two Relations. SIAM J. Comput. 8 (3) (1979)
Lawrence T. Kou, Larry J. Stockmeyer, C. K. Wong
Covering Edges by Cliques with Regard to Keyword Conflicts and Intersection Graphs. Commun. ACM 21 (2) (1978)
Richard J. Lipton, Larry J. Stockmeyer
Evaluation of Polynomials with Super-Preconditioning. J. Comput. Syst. Sci. 16 (2) (1978)
Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer
Alternating Pushdown Automata (Preliminary Report) FOCS (1978)
Arnold L. Rosenberg, Larry J. Stockmeyer
Storage Schemes for Boundedly Extendible Arrays. Acta Informatica 7 (1977)
Larry J. Stockmeyer
On the Combinational Complexity of Certain Symmetric Boolean Functions. Math. Syst. Theory 10 (1977)
Arnold L. Rosenberg, Larry J. Stockmeyer
Hashing Schemes for Extendible Arrays. J. ACM 24 (2) (1977)
Ashok K. Chandra, Larry J. Stockmeyer
Alternation FOCS (1976)
M. R. Garey, David S. Johnson, Larry J. Stockmeyer
Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1 (3) (1976)
Richard J. Lipton, Larry J. Stockmeyer
Evaluation of Polynomials with Super-Preconditioning STOC (1976)
Larry J. Stockmeyer
The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3 (1) (1976)
Vaughan R. Pratt, Larry J. Stockmeyer
A Characterization of the Power of Vector Machines. J. Comput. Syst. Sci. 12 (2) (1976)
Arnold L. Rosenberg, Larry J. Stockmeyer
Hashing Schemes for Extendible Arrays (Extended Arrays) STOC (1975)
M. R. Garey, David S. Johnson, Larry J. Stockmeyer
Some Simplified NP-Complete Problems STOC (1974)
Vaughan R. Pratt, Michael O. Rabin, Larry J. Stockmeyer
A Characterization of the Power of Vector Machines STOC (1974)
Michael J. Fischer, Larry J. Stockmeyer
Fast On-Line Integer Multiplication. J. Comput. Syst. Sci. 9 (3) (1974)
Mike Paterson, Larry J. Stockmeyer
On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials. SIAM J. Comput. 2 (1) (1973)
Michael J. Fischer, Larry J. Stockmeyer
Fast On-Line Integer Multiplication STOC (1973)
Larry J. Stockmeyer
Planar 3-colorability is polynomial complete. SIGACT News 5 (3) (1973)
Larry J. Stockmeyer, Albert R. Meyer
Word Problems Requiring Exponential Time: Preliminary Report STOC (1973)
Albert R. Meyer, Larry J. Stockmeyer
The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space SWAT (1972)
Mike Paterson, Larry J. Stockmeyer
Bounds on the Evaluation Time for Rational Polynomials SWAT (1971)