| | Annual ACM Symposium on Theory of Computing archiveProceedings of the fourteenth annual ACM symposium on Theory of computing 1982, San Francisco, California, United States May 05 - 07, 1982 | | | | Front matter  Pdf(204 KB) front matter material | | |
| | | Table of Contents | | | | Two tapes are better than one for nondeterministic machines
Pavol Dûriš, Zvi Galil
Pages: 1 - 7
Full text available: Pdf(465 KB) | | | | The tight deterministic time hierarchy
Martin Fürer
Pages: 8 - 16
Full text available: Pdf(480 KB) | | | | Probabilistic simulations (Preliminary Version)
Nicholas Pippenger
Pages: 17 - 26
Full text available: Pdf(490 KB) | | | | Real-time simulation of multicounters by oblivious one-tape turing machines (Preliminary Draft)
Paul M.B. Vitányi
Pages: 27 - 36
Full text available: Pdf(894 KB) | | | | Two-dimensional alternating Turing machines
Katsushi Inoue, Itsuo Takanami, Hiroshi Taniguchi
Pages: 37 - 46
Full text available: Pdf(809 KB) | | | | Ensembles reconnaissables de mots biinfinis
Maurice Nivat, Dominique Perrin
Pages: 47 - 59
Full text available: Pdf(686 KB) | | | | Trees, automata, and games
Yuri Gurevich, Leo Harrington
Pages: 60 - 65
Full text available: Pdf(504 KB) | | | | The theory of signature testing for VLSI
J. Lawrence Carter
Pages: 66 - 76
Full text available: Pdf(699 KB) | | | | How to assemble tree machines (Extended Abstract)
Sandeep N. Bhatt, Charles E. Leiserson
Pages: 77 - 84
Full text available: Pdf(687 KB) | | | | A layout strategy for VLSI which is provably good (Extended Abstract)
Frank Thomson Leighton
Pages: 85 - 98
Full text available: Pdf(1.25 MB) | | | | Measuring energy consumption in VLSI circuits: A foundation
Gloria Kissin
Pages: 99 - 104
Full text available: Pdf(434 KB) | | | | How to reuse a "write - once " memory (Preliminary Version)
Ronald L. Rivest, Adi Shamir
Pages: 105 - 113
Full text available: Pdf(680 KB) | | | | Maintaining dense sequential files in a dynamic environment (Extended Abstract)
Dan E. Willard
Pages: 114 - 121
Full text available: Pdf(538 KB) | | | | Maintaining order in a linked list
Paul F. Dietz
Pages: 122 - 127
Full text available: Pdf(308 KB) | | | | Space-time tradeoff for answering range queries (Extended Abstract)
Andrew C. Yao
Pages: 128 - 136
Full text available: Pdf(602 KB) | | | | The complexity of relational query languages (Extended Abstract)
Moshe Y. Vardi
Pages: 137 - 146
Full text available: Pdf(513 KB) | | | | Relational queries computable in polynomial time (Extended Abstract)
Neil Immerman
Pages: 147 - 152
Full text available: Pdf(431 KB) | | | | Denotational semantics of concurrency
J. W. de Bakker, J. I. Zucker
Pages: 153 - 158
Full text available: Pdf(565 KB) | | | | The complexity of propositional linear temporal logics
A. P. Sistla, E. M. Clarke
Pages: 159 - 168
Full text available: Pdf(560 KB) | | | | Decision procedures and expressiveness in the temporal logic of branching time
E. Allen Emerson, Joseph Y. Halpern
Pages: 169 - 180
Full text available: Pdf(812 KB) | | | | A probabilistic dynamic logic
Yishai A. Feldman, David Harel
Pages: 181 - 195
Full text available: Pdf(959 KB) | | | | Communication complexity
Christos H. Papadimitriou, Michael Sipser
Pages: 196 - 200
Full text available: Pdf(418 KB) | | | | Symmetric complementation
John H. Reif
Pages: 201 - 214
Full text available: Pdf(1.17 MB) | | | | Space-bounded hierarchies and probabilistic computations
Walter L. Ruzzo, Janos Simon, Martin Tompa
Pages: 215 - 223
Full text available: Pdf(495 KB) | | | | On the random oracle hypothesis
Stuart A. Kurtz
Pages: 224 - 230
Full text available: Pdf(311 KB) | | | | Bounds on the time for parallel RAM's to compute simple functions
Stephen Cook, Cynthia Dwork
Pages: 231 - 233
Full text available: Pdf(192 KB) | | | | Probabilistic, nondeterministic, and alternating decision trees (Preliminary Version)
Udi Manber, Martin Tompa
Pages: 234 - 244
Full text available: Pdf(601 KB) | | | | Edge-deletion and edge-contraction problems
Takao Asano, Tomio Hirata
Pages: 245 - 254
Full text available: Pdf(648 KB) | | | | The complexity of facets (and some facets of complexity)
C. H. Papadimitriou, M. Yannakakis
Pages: 255 - 260
Full text available: Pdf(358 KB) | | | | A polynomial reduction from multivariate to bivariate integral polynomial factorization.
Erich Kaltofen
Pages: 261 - 266
Full text available: Pdf(421 KB) | | | | Decidability of reachability in vector addition systems (Preliminary Version)
S. Rao Kosaraju
Pages: 267 - 281
Full text available: Pdf(848 KB) | | | | Finding extremal polygons
James E. Boyce, David P. Dobkin, Robert L.(Scot) Drysdale, III, Leo J. Guibas
Pages: 282 - 289
Full text available: Pdf(659 KB) | | | | Fast algorithms under the extended riemann hypothesis: A concrete estimate
Eric Bach
Pages: 290 - 295
Full text available: Pdf(419 KB) | | | | Notes on merging networks (Prelimiary Version)
Zhu Hong, Robert Sedgewick
Pages: 296 - 302
Full text available: Pdf(508 KB) | | | | On approximating a vertex cover for planar graphs
R. Bar-Yehuda, S. Even
Pages: 303 - 309
Full text available: Pdf(384 KB) | | | | Isomorphism of graphs with bounded eigenvalue multiplicity
László Babai, D. Yu. Grigoryev, David M. Mount
Pages: 310 - 324
Full text available: Pdf(965 KB) | | | | A new approximate graph coloring algorithm
Avi Wigderson
Pages: 325 - 329
Full text available: Pdf(269 KB) | | | | Las Vegas is better than determinism in VLSI and distributed computing (Extended Abstract)
Kurt Mehlhorn, Erik M. Schmidt
Pages: 330 - 337
Full text available: Pdf(428 KB) | | | | Routing, merging and sorting on parallel models of computation
A. Borodin, J. E. Hopcroft
Pages: 338 - 344
Full text available: Pdf(581 KB) | | | | Graph problems on a mesh-connected processor array (Preliminary Version)
Mikhail J. Atallah, S. Rao Kosaraju
Pages: 345 - 353
Full text available: Pdf(657 KB) | | | | On the time complexity of broadcast communication schemes (Preliminary Version)
Albert G. Greenberg
Pages: 354 - 364
Full text available: Pdf(661 KB) | | | | Probabilistic encryption & how to play mental poker keeping secret all partial information
Shafi Goldwasser, Silvio Micali
Pages: 365 - 377
Full text available: Pdf(1.21 MB) | | | | A technique for proving lower bounds for distributed maximum-finding algorithms (Preliminary Version)
Jan K. Pachl, E. Korach, D. Rotem
Pages: 378 - 382
Full text available: Pdf(359 KB) | | | | Cryptographic protocols
Richard A. DeMillo, Nancy A. Lynch, Michael J. Merritt
Pages: 383 - 400
Full text available: Pdf(1.34 MB) | | | | Polynomial algorithms for multiple processor agreement
Danny Dolev, H. Raymond Strong
Pages: 401 - 407
Full text available: Pdf(604 KB) | |
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
