20. STOC 1988: Chicago, Illinois, USA

• Michael Ben-Or, Shafi Goldwasser, Avi Wigderson:
  Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract). 1-10
  
• David Chaum, Claude Crépeau, Ivan Damgård:
  Multiparty Unconditionally Secure Protocols (Extended Abstract). 11-19
  
• Joe Kilian:
  Founding Cryptography on Oblivious Transfer. 20-31
  
• Mihir Bellare, Silvio Micali:
  How to Sign Given Any Trapdoor Function (Extended Abstract). 32-42
  
• David Peleg, Eli Upfal:
  A Tradeoff between Space and Efficiency for Routing Tables (Extended Abstract). 43-52
  
• Joseph Y. Halpern, Moshe Y. Vardi:
  Reasoning about Knowledge and Time in Asynchronous Systems. 53-65
  
• Piotr Berman, Janos Simon:
  Investigations of Fault-Tolerant Networks of Computers (Preliminary Version). 66-77
  
• Danny Dolev, Eli Gafni, Nir Shavit:
  Toward a Non-Atomic Era: \ell-Exclusion as a Test Case. 78-92
  
• Danny Krizanc, David Peleg, Eli Upfal:
  A Time-Randomness Tradeoff for Oblivious Routing (Extended Abstract). 93-102
  
• Manuel Blum, Paul Feldman, Silvio Micali:
  Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). 103-112
  
• Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson:
  Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions. 113-131
  
• Joseph Y. Halpern, Yoram Moses, Mark R. Tuttle:
  A Knowledge-Based Analysis of Zero Knowledge (Preliminary Report). 132-147
  
• Paul Feldman, Silvio Micali:
  Optimal Algorithms for Byzantine Agreement. 148-161
  
• Bernd Halstenberg, Rüdiger Reischuk:
  On Different Modes of Communication (Extended Abstract). 162-172
  
• Alok Aggarwal, Ashok K. Chandra:
  Virtual Memory Algorithms (Preliminary Version). 173-185
  
• András Hajnal, Wolfgang Maass, György Turán:
  On the Communication Complexity of Graph Properties. 186-191
  
• Sandeep N. Bhatt, Fan R. K. Chung, Jia-Wei Hong, Frank Thomson Leighton, Arnold L. Rosenberg:
  Optimal Simulations by Butterfly Networks (Preliminary Version). 192-204
  
• Alok Aggarwal, Ashok K. Chandra, Prabhakar Raghavan:
  Energy Consumption in VLSI Circuits (Preliminary Version). 205-216
  
• Ramarathnam Venkatesan, Leonid A. Levin:
  Random Instances of a Graph Coloring Problem Are Hard. 217-222
  
• Mihalis Yannakakis:
  Expressing Combinatorial Optimization Problems by Linear Programs (Extended Abstract). 223-228
  
• Christos H. Papadimitriou, Mihalis Yannakakis:
  Optimization, Approximation, and Complexity Classes (Extended Abstract). 229-234
  
• Mark Jerrum, Alistair Sinclair:
  Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version). 235-244
  
• Ker-I Ko:
  Relativized Polynominal Time Hierarchies Having Exactly K Levels. 245-253
  
• Michael Ben-Or, Richard Cleve:
  Computing Algebraic Formulas Using a Constant Number of Registers. 254-257
  
• Bala Kalyanasundaram, Georg Schnitger:
  On the Power of White Pebbles (Extended Abstract). 258-266
  
• Michael J. Kearns, Ming Li:
  Learning in the Presence of Malicious Errors (Extended Abstract). 267-280
  
• Yuri Gurevich, Saharon Shelah:
  Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space. 281-289
  
• Richard M. Karp, Yanjun Zhang:
  A Randomized Parallel Branch-and-Bound Procedure. 290-300
  
• Michael Ben-Or, Prasoon Tiwari:
  A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation (Extended Abstract). 301-309
  
• Howard J. Karloff, Prabhakar Raghavan:
  Randomized Algorithms and Pseudorandom Numbers. 310-321
  
• Mark S. Manasse, Lyle A. McGeoch, Daniel Dominic Sleator:
  Competitive Algorithms for On-line Problems. 322-333
  
• Sampath Kannan, Moni Naor, Steven Rudich:
  Implicit Representation of Graphs. 334-343
  
• Amos Fiat, Moni Naor, Alejandro A. Schäffer, Jeanette P. Schmidt, Alan Siegel:
  Storing and Searching a Multikey Table (Extended Abstract). 344-353
  
• George S. Lueker, Mariko Molodowitch:
  More Analysis of Double Hashing. 354-359
  
• Martin Loebl, Jaroslav Nesetril:
  Linearity and Unprovability of Set Union Problem Strategies. 360-366
  
• Amos Fiat, Moni Naor, Jeanette P. Schmidt, Alan Siegel:
  Non-Oblivious Hashing (Extended Abstract). 367-376
  
• James B. Orlin:
  A Faster Strongly Polynominal Minimum Cost Flow Algorithm. 377-387
  
• Andrew V. Goldberg, Robert Endre Tarjan:
  Finding Minimum-Cost Circulations by Canceling Negative Cycles. 388-397
  
• S. Rao Kosaraju, Gregory F. Sullivan:
  Detecting Cycles in Dynamic Graphs in Polynomial Time (Preliminary Version). 398-406
  
• Harold N. Gabow, Herbert H. Westermann:
  Forests, Frames and Games: Algorithms for Matroid Sums and Applications. 407-421
  
• Pravin M. Vaidya:
  Geometry Helps in Matching (Extended Abstract). 422-425
  
• Hubert de Fraysseix, János Pach, Richard Pollack:
  Small Sets Supporting Fáry Embeddings of Planar Graphs. 426-433
  
• Tomás Feder, Daniel H. Greene:
  Optimal Algorithms for Approximate Clustering. 434-444
  
• Steven Fortune, Gordon T. Wilfong:
  Planning Constrained Motion. 445-459
  
• John F. Canny:
  Some Algebraic and Geometric Computations in PSPACE. 460-467
  
• Valerie King:
  Lower Bounds on the Complexity of Graph Properties. 468-476
  
• Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, Moshe Y. Vardi:
  Decidable Optimization Problems for Database Logic Programs (Preliminary Report). 477-490
  
• Sorin Istrail:
  Polynomial Universal Traversing Sequences for Cycles Are Constructible (Extended Abstract). 491-503
  
• Janos Pintz, William L. Steiger, Endre Szemerédi:
  Two Infinite Sets of Primes with Fast Primality Tests. 504-509
  
• Christos H. Papadimitriou, Mihalis Yannakakis:
  Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract). 510-513
  
• Harold N. Gabow, Robert Endre Tarjan:
  Almost-Optimum Speed-ups of Algorithms for Bipartite Matching and Related Problems. 514-527
  
• Leonard M. Adleman, Kireeti Kompella:
  Using Smoothness to Achieve Parallelism (Abstract). 528-538
  
• Mauricio Karchmer, Avi Wigderson:
  Monotone Circuits for Connectivity Require Super-logarithmic Depth. 539-550
  
• Andrei Z. Broder: Errata to "How hard is to marry at random? (On the approximation of the permanent)". 551

Last update Sat May 18 19:50:30 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page