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