Proceedings of the 20th Annual ACM Symposium on Theory of Computing
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
EDIT!
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter

Janos Simon
Proceedings of the 20th Annual ACM Symposium on Theory of Computing
STOC, 1988.

TCS
DBLP
Scholar
Full names Links ISxN
@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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.