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)

10 ×#algorithm
6 ×#graph
6 ×#problem
4 ×#approximate
4 ×#multi
4 ×#random
3 ×#analysis
3 ×#complexity
3 ×#how
3 ×#on the

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.