20. STOC 1988
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA. ACM 1988
- 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
- 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
- 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
Copyright © Mon Dec 7 20:10:41 2009
by Michael Ley (ley@uni-trier.de)
