## Janos Simon

*Proceedings of the 20th Annual ACM Symposium on Theory of Computing*

STOC, 1988.

@proceedings{STOC-1988, address = "Chicago, Illinois, USA", editor = "Janos Simon", isbn = "0-89791-264-0", publisher = "{ACM}", title = "{Proceedings of the 20th Annual ACM Symposium on Theory of Computing}", year = 1988, }

### Contents (54 items)

- STOC-1988-Ben-OrGW #distributed #fault tolerance #theorem
- Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (MBO, SG, AW), pp. 1–10.
- STOC-1988-ChaumCD #multi #protocol
- Multiparty Unconditionally Secure Protocols (DC, CC, ID), pp. 11–19.
- STOC-1988-Kilian #encryption
- Founding Cryptography on Oblivious Transfer (JK), pp. 20–31.
- STOC-1988-BellareM #how
- How to Sign Given Any Trapdoor Function (MB, SM), pp. 32–42.
- STOC-1988-PelegU #performance #trade-off
- A Tradeoff between Space and Efficiency for Routing Tables (DP, EU), pp. 43–52.
- STOC-1988-HalpernV #reasoning
- Reasoning about Knowledge and Time in Asynchronous Systems (JYH, MYV), pp. 53–65.
- STOC-1988-BermanS #fault tolerance #network
- Investigations of Fault-Tolerant Networks of Computers (PB, JS), pp. 66–77.
- STOC-1988-DolevGS #testing #towards
- Toward a Non-Atomic Era: 𝓁-Exclusion as a Test Case (DD, EG, NS), pp. 78–92.
- STOC-1988-KrizancPU #trade-off
- A Time-Randomness Tradeoff for Oblivious Routing (DK, DP, EU), pp. 93–102.
- STOC-1988-BlumFM
- Non-Interactive Zero-Knowledge and Its Applications (MB, PF, SM), pp. 103–112.
- STOC-1988-Ben-OrGKW #how #interactive #multi #proving
- Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions (MBO, SG, JK, AW), pp. 113–131.
- STOC-1988-HalpernMT #analysis #knowledge-based
- A Knowledge-Based Analysis of Zero Knowledge (JYH, YM, MRT), pp. 132–147.
- STOC-1988-FeldmanM #algorithm
- Optimal Algorithms for Byzantine Agreement (PF, SM), pp. 148–161.
- STOC-1988-HalstenbergR #communication #on the
- On Different Modes of Communication (BH, RR), pp. 162–172.
- STOC-1988-AggarwalC #algorithm #memory management
- Virtual Memory Algorithms (AA, AKC), pp. 173–185.
- STOC-1988-HajnalMT #communication #complexity #graph #on the
- On the Communication Complexity of Graph Properties (AH, WM, GT), pp. 186–191.
- STOC-1988-BhattCHLR #network #simulation
- Optimal Simulations by Butterfly Networks (SNB, FRKC, JWH, FTL, ALR), pp. 192–204.
- STOC-1988-AggarwalCR #energy
- Energy Consumption in VLSI Circuits (AA, AKC, PR), pp. 205–216.
- STOC-1988-VenkatesanL #graph #problem #random
- Random Instances of a Graph Coloring Problem Are Hard (RV, LAL), pp. 217–222.
- STOC-1988-Yannakakis #combinator #linear #optimisation #problem #source code
- Expressing Combinatorial Optimization Problems by Linear Programs (MY), pp. 223–228.
- STOC-1988-PapadimitriouY88a #approximate #complexity #optimisation
- Optimization, Approximation, and Complexity Classes (CHP, MY), pp. 229–234.
- STOC-1988-JerrumS #agile #approximate #markov
- Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (MJ, AS), pp. 235–244.
- STOC-1988-Ko
- Relativized Polynominal Time Hierarchies Having Exactly K Levels (KIK), pp. 245–253.
- STOC-1988-Ben-OrC #algebra #constant #using
- Computing Algebraic Formulas Using a Constant Number of Registers (MBO, RC), pp. 254–257.
- STOC-1988-KalyanasundaramS #on the #power of
- On the Power of White Pebbles (BK, GS), pp. 258–266.
- STOC-1988-KearnsL #fault #learning
- Learning in the Presence of Malicious Errors (MJK, ML), pp. 267–280.
- STOC-1988-GurevichS #linear #nondeterminism #sublinear
- Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space (YG, SS), pp. 281–289.
- STOC-1988-KarpZ #bound #parallel #random
- A Randomized Parallel Branch-and-Bound Procedure (RMK, YZ), pp. 290–300.
- STOC-1988-Ben-OrT #algorithm #multi
- A Deterministic Algorithm for Sparse Multivariate Polynominal Interpolation (MBO, PT), pp. 301–309.
- STOC-1988-KarloffR #algorithm #pseudo #random
- Randomized Algorithms and Pseudorandom Numbers (HJK, PR), pp. 310–321.
- STOC-1988-ManasseMS #algorithm #online #problem
- Competitive Algorithms for On-line Problems (MSM, LAM, DDS), pp. 322–333.
- STOC-1988-KannanNR #graph #representation
- Implicit Representation of Graphs (SK, MN, SR), pp. 334–343.
- STOC-1988-FiatNSSS #multi
- Storing and Searching a Multikey Table (AF, MN, AAS, JPS, AS), pp. 344–353.
- STOC-1988-LuekerM #analysis
- More Analysis of Double Hashing (GSL, MM), pp. 354–359.
- STOC-1988-LoeblN #problem #set
- Linearity and Unprovability of Set Union Problem Strategies (ML, JN), pp. 360–366.
- STOC-1988-FiatNSS
- Non-Oblivious Hashing (AF, MN, JPS, AS), pp. 367–376.
- STOC-1988-Orlin #algorithm #performance
- A Faster Strongly Polynominal Minimum Cost Flow Algorithm (JBO), pp. 377–387.
- STOC-1988-GoldbergT #low cost
- Finding Minimum-Cost Circulations by Canceling Negative Cycles (AVG, RET), pp. 388–397.
- STOC-1988-KosarajuS #detection #graph #polynomial
- Detecting Cycles in Dynamic Graphs in Polynomial Time (SRK, GFS), pp. 398–406.
- STOC-1988-GabowW #algorithm #game studies
- Forests, Frames and Games: Algorithms for Matroid Sums and Applications (HNG, HHW), pp. 407–421.
- STOC-1988-Vaidya #geometry
- Geometry Helps in Matching (PMV), pp. 422–425.
- STOC-1988-FraysseixPP #graph #set
- Small Sets Supporting Fáry Embeddings of Planar Graphs (HdF, JP, RP), pp. 426–433.
- STOC-1988-FederG #algorithm #approximate #clustering
- Optimal Algorithms for Approximate Clustering (TF, DHG), pp. 434–444.
- STOC-1988-FortuneW
- Planning Constrained Motion (SF, GTW), pp. 445–459.
- STOC-1988-Canny #algebra #geometry
- Some Algebraic and Geometric Computations in PSPACE (JFC), pp. 460–467.
- STOC-1988-King #bound #complexity #graph
- Lower Bounds on the Complexity of Graph Properties (VK), pp. 468–476.
- STOC-1988-CosmadakisGKV #database #decidability #logic programming #optimisation #problem #source code
- Decidable Optimization Problems for Database Logic Programs (SSC, HG, PCK, MYV), pp. 477–490.
- STOC-1988-Istrail #polynomial #sequence #traversal
- Polynomial Universal Traversing Sequences for Cycles Are Constructible (SI), pp. 491–503.
- STOC-1988-PintzSS #infinity #performance #testing
- Two Infinite Sets of Primes with Fast Primality Tests (JP, WLS, ES), pp. 504–509.
- STOC-1988-PapadimitriouY88b #algorithm #analysis #architecture #independence #parallel #towards
- Towards an Architecture-Independent Analysis of Parallel Algorithms (CHP, MY), pp. 510–513.
- STOC-1988-GabowT #algorithm #problem
- Almost-Optimum Speed-ups of Algorithms for Bipartite Matching and Related Problems (HNG, RET), pp. 514–527.
- STOC-1988-AdlemanK #parallel #using
- Using Smoothness to Achieve Parallelism (LMA, KK), pp. 528–538.
- STOC-1988-KarchmerW
- Monotone Circuits for Connectivity Require Super-logarithmic Depth (MK, AW), pp. 539–550.
- STOC-1988-Broder #approximate #how #random
- Errata to “How hard is to marry at random? (On the approximation of the permanent)” (AZB), p. 551.

10 ×#algorithm

6 ×#graph

6 ×#problem

4 ×#approximate

4 ×#multi

4 ×#random

3 ×#analysis

3 ×#complexity

3 ×#how

3 ×#on the

6 ×#graph

6 ×#problem

4 ×#approximate

4 ×#multi

4 ×#random

3 ×#analysis

3 ×#complexity

3 ×#how

3 ×#on the