dblp.uni-trier.dewww.uni-trier.de

Larry J. Stockmeyer Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

*2006
84EEMiklós Ajtai, Cynthia Dwork, Larry J. Stockmeyer: An Architecture for Provably Secure Computation. LATIN 2006: 56-67
2004
83EEChing-Tien Ho, Larry J. Stockmeyer: A New Approach to Fault-Tolerant Wormhole Routing for Mesh-Connected Parallel Computers. IEEE Trans. Computers 53(4): 427-439 (2004)
2003
82EERandal C. Burns, Larry J. Stockmeyer, Darrell D. E. Long: In-Place Reconstruction of Version Differences. IEEE Trans. Knowl. Data Eng. 15(4): 973-984 (2003)
81EECynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer: Magic Functions. J. ACM 50(6): 852-921 (2003)
2002
80EEChing-Tien Ho, Larry J. Stockmeyer: A New Approach to Fault-Tolerant Wormhole Routing for Mesh-Connected Parallel Computers. IPDPS 2002
79EECynthia Dwork, Larry J. Stockmeyer: 2-round zero knowledge and proof auditors. STOC 2002: 322-331
78 Larry J. Stockmeyer, Dharmendra S. Modha: Links between complexity theory and constrained block coding. IEEE Transactions on Information Theory 48(1): 59-88 (2002)
77EEMikló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): 318-367 (2002)
76EELarry J. Stockmeyer, Albert R. Meyer: Cosmological lower bound on the circuit complexity of a small problem in logic. J. ACM 49(6): 753-784 (2002)
2001
75EELarry J. Stockmeyer, Dharmendra S. Modha: Links Between Complexity Theory and Constrained Block Coding. IEEE Conference on Computational Complexity 2001: 226-243
74 Randal C. Burns, Robert M. Rees, Larry J. Stockmeyer, Darrell D. E. Long: Scalable Session Locking for a Distributed File System. Cluster Computing 4(4): 295-306 (2001)
2000
73 Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer: The Closure of Monadic NP. J. Comput. Syst. Sci. 60(3): 660-716 (2000)
1999
72EECynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer: Magic Functions. FOCS 1999: 523-534
1998
71EEGuillermo A. Alvarez, Walter A. Burkhard, Larry J. Stockmeyer, Flaviu Cristian: Declustered Disk Array Architectures with Optimal and Near-Optimal Parallelism. ISCA 1998: 109-120
70EEMiklós Ajtai, Ronald Fagin, Larry J. Stockmeyer: The Closure of Monadic NP (Extended Abstract). STOC 1998: 309-318
69EERonald Fagin, Larry J. Stockmeyer: Relaxing the Triangle Inequality in Pattern Matching. International Journal of Computer Vision 30(3): 219-231 (1998)
1996
68 David M. Choy, Ronald Fagin, Larry J. Stockmeyer: Efficiently Extendible Mappings for Balanced Data Distribution. Algorithmica 16(2): 215-232 (1996)
67EEAlain J. Mayer, Larry J. Stockmeyer: The Complexity of PDL with Interleaving. Theor. Comput. Sci. 161(1&2): 109-122 (1996)
1995
66 Alain J. Mayer, Moni Naor, Larry J. Stockmeyer: Local Computations on Static and Dynamic Graphs (Preliminary Version). ISTCS 1995: 268-278
65 Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi: On Monadic NP vs. Monadic co-NP Inf. Comput. 120(1): 78-92 (1995)
64 Moni Naor, Larry J. Stockmeyer: What Can be Computed Locally? SIAM J. Comput. 24(6): 1259-1277 (1995)
1994
63 Alain J. Mayer, Larry J. Stockmeyer: Word Problems-This Time with Interleaving Inf. Comput. 115(2): 293-311 (1994)
62EEHagit 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): 122-152 (1994)
61 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): 175-201 (1994)
1993
60EEMoni Naor, Larry J. Stockmeyer: What can be computed locally? STOC 1993: 184-193
59 Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi: On Monadic NP vs. Monadic co-NP (Extended Abstract). Structure in Complexity Theory Conference 1993: 19-30
1992
58 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: 334-343
57EECynthia Dwork, Larry J. Stockmeyer: Finite State Verifiers I: The Power of Interaction. J. ACM 39(4): 800-828 (1992)
56EECynthia Dwork, Larry J. Stockmeyer: Finite State Verifiers II: Zero Knowledge. J. ACM 39(4): 829-858 (1992)
1991
55 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: 359-369
1990
54 Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer: Flipping Persuasively in Constant Time. SIAM J. Comput. 19(3): 472-499 (1990)
53 Cynthia Dwork, Larry J. Stockmeyer: A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata. SIAM J. Comput. 19(6): 1011-1023 (1990)
1989
52 Cynthia Dwork, Larry J. Stockmeyer: On the Power of 2-Way Probabilistic Finite State Automata (Extended Abstract) FOCS 1989: 480-485
51 Brian A. Coan, Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer: The Distributed Firing Squad Problem. SIAM J. Comput. 18(5): 990-1012 (1989)
1988
50EECynthia Dwork, Larry J. Stockmeyer: Zero-Knowledge With Finite State Verifiers. CRYPTO 1988: 71-75
49EECynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer: Consensus in the presence of partial synchrony. J. ACM 35(2): 288-323 (1988)
48 Cynthia Dwork, Paris C. Kanellakis, Larry J. Stockmeyer: Parallel Algorithms for Term Matching. SIAM J. Comput. 17(4): 711-731 (1988)
1987
47EEDanny Dolev, Cynthia Dwork, Larry J. Stockmeyer: On the minimal synchronism needed for distributed consensus. J. ACM 34(1): 77-97 (1987)
46 Larry J. Stockmeyer: Classifying the Computational Complexity of Problems. J. Symb. Log. 52(1): 1-43 (1987)
1986
45EECynthia Dwork, Paris C. Kanellakis, Larry J. Stockmeyer: Parallel Algorithms for Term Matching. CADE 1986: 416-430
44 Cynthia Dwork, David B. Shmoys, Larry J. Stockmeyer: Flipping Persuasively in Constant Expected Time (Preliminary Version) FOCS 1986: 222-232
1985
43 Moshe Y. Vardi, Larry J. Stockmeyer: Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report STOC 1985: 240-251
42 Brian A. Coan, Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer: The Distributed Firing Squad Problem (Preliminary Version) STOC 1985: 335-345
41 Larry Carter, Larry J. Stockmeyer, Mark N. Wegman: The Complexity of Backtrack Searches (Preliminary Version) STOC 1985: 449-457
40 Merrick L. Furst, Richard J. Lipton, Larry J. Stockmeyer: Pseudorandom Number Generation and Space Complexity Information and Control 64(1-3): 43-51 (1985)
39 Larry J. Stockmeyer: On Approximation Algorithms for #P. SIAM J. Comput. 14(4): 849-861 (1985)
38 Ronald Fagin, Maria M. Klawe, Nicholas Pippenger, Larry J. Stockmeyer: Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions. Theor. Comput. Sci. 36: 239-250 (1985)
1984
37 Cynthia Dwork, Nancy A. Lynch, Larry J. Stockmeyer: Consensus in the Presence of Partial Synchrony (Preliminary Version). PODC 1984: 103-118
36 Richard E. Ladner, Larry J. Stockmeyer, Richard J. Lipton: Alternation Bounded Auxiliary Pushdown Automata Information and Control 62(2/3): 93-108 (1984)
35EEYuri 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): 459-473 (1984)
34 Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer: Alternating Pushdown and Stack Automata. SIAM J. Comput. 13(1): 135-155 (1984)
33 Larry J. Stockmeyer, Uzi Vishkin: Simulation of Parallel Random Access Machines by Circuits. SIAM J. Comput. 13(2): 409-422 (1984)
32 Ashok K. Chandra, Larry J. Stockmeyer, Uzi Vishkin: Constant Depth Reducibility. SIAM J. Comput. 13(2): 423-439 (1984)
1983
31 Merrick L. Furst, Richard J. Lipton, Larry J. Stockmeyer: Pseudorandom Number Generation and Space Complexity. FCT 1983: 171-176
30 Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer: On the Minimal Synchronism Needed for Distributed Consensus FOCS 1983: 393-402
29 Larry J. Stockmeyer: The Complexity of Approximate Counting (Preliminary Version) STOC 1983: 118-126
28 Larry J. Stockmeyer: Optimal Orientations of Cells in Slicing Floorplan Designs Information and Control 57(2/3): 91-101 (1983)
1982
27 Ashok K. Chandra, Larry J. Stockmeyer, Uzi Vishkin: A Complexity Theory for Unbounded Fan-In Parallelism FOCS 1982: 1-13
26 Thomas Ottmann, Arnold L. Rosenberg, Larry J. Stockmeyer: A Dictionary Machine (for VLSI). IEEE Trans. Computers 31(9): 892-897 (1982)
25 Larry J. Stockmeyer, Vijay V. Vazirani: NP-Completeness of Some Generalizations of the Maximum Matching Problem. Inf. Process. Lett. 15(1): 14-19 (1982)
1981
24EEAshok K. Chandra, Dexter Kozen, Larry J. Stockmeyer: Alternation. J. ACM 28(1): 114-133 (1981)
1980
23 Arnold L. Rosenberg, Larry J. Stockmeyer, Lawrence Snyder: Uniform Data Encodings. Theor. Comput. Sci. 11: 145-165 (1980)
1979
22 Larry J. Stockmeyer, Ashok K. Chandra: Provably Difficult Combinatorial Games. SIAM J. Comput. 8(2): 151-174 (1979)
21 Larry J. Stockmeyer, C. K. Wong: On the Number of Comparisons to Find the Intersection of Two Relations. SIAM J. Comput. 8(3): 388-404 (1979)
1978
20 Richard E. Ladner, Richard J. Lipton, Larry J. Stockmeyer: Alternating Pushdown Automata (Preliminary Report) FOCS 1978: 92-106
19 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): 135-139 (1978)
18 Richard J. Lipton, Larry J. Stockmeyer: Evaluation of Polynomials with Super-Preconditioning. J. Comput. Syst. Sci. 16(2): 124-139 (1978)
1977
17 Arnold L. Rosenberg, Larry J. Stockmeyer: Storage Schemes for Boundedly Extendible Arrays Acta Inf. 7: 289-303 (1977)
16EEArnold L. Rosenberg, Larry J. Stockmeyer: Hashing Schemes for Extendible Arrays. J. ACM 24(2): 199-221 (1977)
15 Larry J. Stockmeyer: On the Combinational Complexity of Certain Symmetric Boolean Functions. Mathematical Systems Theory 10: 323-336 (1977)
1976
14 Ashok K. Chandra, Larry J. Stockmeyer: Alternation FOCS 1976: 98-108
13 Richard J. Lipton, Larry J. Stockmeyer: Evaluation of Polynomials with Super-Preconditioning STOC 1976: 174-180
12 Vaughan R. Pratt, Larry J. Stockmeyer: A Characterization of the Power of Vector Machines. J. Comput. Syst. Sci. 12(2): 198-221 (1976)
11 M. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237-267 (1976)
10 Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22 (1976)
1975
9 Arnold L. Rosenberg, Larry J. Stockmeyer: Hashing Schemes for Extendible Arrays (Extended Arrays) STOC 1975: 159-166
1974
8 Vaughan R. Pratt, Michael O. Rabin, Larry J. Stockmeyer: A Characterization of the Power of Vector Machines STOC 1974: 122-134
7 M. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Problems STOC 1974: 47-63
6 Michael J. Fischer, Larry J. Stockmeyer: Fast On-Line Integer Multiplication. J. Comput. Syst. Sci. 9(3): 317-331 (1974)
1973
5 Larry J. Stockmeyer, Albert R. Meyer: Word Problems Requiring Exponential Time: Preliminary Report STOC 1973: 1-9
4 Michael J. Fischer, Larry J. Stockmeyer: Fast On-Line Integer Multiplication STOC 1973: 67-72
3 Mike Paterson, Larry J. Stockmeyer: On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials. SIAM J. Comput. 2(1): 60-66 (1973)
1972
2 Albert R. Meyer, Larry J. Stockmeyer: The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space FOCS 1972: 125-129
1971
1 Mike Paterson, Larry J. Stockmeyer: Bounds on the Evaluation Time for Rational Polynomials FOCS 1971: 140-143

Coauthor Index

1Miklós Ajtai [70] [73] [77] [84]
2Noga Alon [58] [61]
3Guillermo A. Alvarez [71]
4Hagit Attiya (Chagit Attiya) [55] [62]
5Walter A. Burkhard [71]
6Randal C. Burns [74] [77] [82]
7Larry Carter [41]
8Ashok K. Chandra [14] [22] [24] [27] [32]
9David M. Choy [68]
10Brian A. Coan [42] [51]
11Flaviu Cristian [71]
12Danny Dolev [30] [42] [47] [51]
13Cynthia Dwork [30] [37] [42] [44] [45] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [62] [72] [79] [81] [84]
14Ronald Fagin [38] [59] [65] [68] [69] [70] [73] [77]
15Michael J. Fischer [4] [6]
16Merrick L. Furst [31] [40]
17M. R. Garey (Michael R. Garey) [7] [11]
18Yuri Gurevich [35]
19C. T. Howard Ho (Howard Ho, Ching-Tien Ho) [80] [83]
20David S. Johnson [7] [11]
21Gil Kalai [58] [61]
22Paris C. Kanellakis [45] [48]
23Maria M. Klawe [38]
24Lawrence T. Kou [19]
25Dexter Kozen [24]
26Richard E. Ladner [20] [34] [36]
27Richard J. Lipton [13] [18] [20] [31] [34] [36] [40]
28Darrell D. E. Long [74] [77] [82]
29Nancy A. Lynch [37] [49] [55] [62]
30Alain J. Mayer [63] [66] [67]
31Albert R. Meyer [2] [5] [76]
32Dharmendra S. Modha [75] [78]
33Moni Naor [60] [64] [66] [72] [81]
34Thomas Ottmann [26]
35Mike Paterson [1] [3]
36Nicholas Pippenger [38]
37Vaughan R. Pratt [8] [12]
38Michael O. Rabin [8]
39Robert M. Rees [74]
40Omer Reingold [72] [81]
41Moty Ricklin [58] [61]
42Arnold L. Rosenberg [9] [16] [17] [23] [26]
43David B. Shmoys [44] [54]
44Lawrence Snyder (Larry Snyder) [23]
45Moshe Y. Vardi [43] [59] [65]
46Vijay V. Vazirani [25]
47Uzi Vishkin [27] [32] [33] [35]
48Mark N. Wegman [41]
49Chak-Kuen Wong (C. K. Wong) [19] [21]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)