20. STOC 1988: Chicago, Illinois, USA
Janos Simon (Ed.): Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA. ACM 1988 ISBN 0-89791-264-0- 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
- 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 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
- Bernd Halstenberg, Rüdiger Reischuk: On Different Modes of Communication (Extended Abstract). 162-172
- 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
- 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
- Michael Ben-Or, Prasoon Tiwari: A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation (Extended Abstract). 301-309
- Mark S. Manasse, Lyle A. McGeoch, Daniel Dominic Sleator: Competitive Algorithms for On-line Problems. 322-333
- Amos Fiat, Moni Naor, Alejandro A. Schäffer, Jeanette P. Schmidt, Alan Siegel: Storing and Searching a Multikey Table (Extended Abstract). 344-353
- 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
- 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
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T214307 by the dblp team