Frank Thomson Leighton, Peter W. Shor
Proceedings of the 29th Annual ACM Symposium on Theory of Computing
STOC, 1997.

@proceedings{STOC-1997,
	address       = "El Paso, Texas, USA",
	editor        = "Frank Thomson Leighton and Peter W. Shor",
	isbn          = "0-89791-888-6",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 29th Annual ACM Symposium on Theory of Computing}",
	year          = 1997,
}

Contents (79 items)

10 ×#algorithm
8 ×#approximate
6 ×#problem
6 ×#random
5 ×#bound
5 ×#graph
5 ×#multi
5 ×#proving
4 ×#complexity
4 ×#on the

STOC-1997-Hastad

Some Optimal Inapproximability Results (JH), pp. 1–10.

STOC-1997-KhannaSW #classification #constraints #problem

A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction (SK, MS, DPW), pp. 11–20.

STOC-1997-Trevisan #geometry

When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (LT), pp. 21–29.

STOC-1997-Reif #approximate #constant #evaluation #polynomial

Approximate Complex Polynomial Evaluation in Near Constant Work Per Point (JHR), pp. 30–39.

STOC-1997-BuhlerSS #fourier #integer #performance #precise #using

Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers (JB, MAS, VS), pp. 40–47.

STOC-1997-Beals #fourier #quantum #symmetry

Quantum Computation of Fourier Transforms over Symmetric Groups (RB), pp. 48–53.

STOC-1997-KaoLPST

General Techniques for Comparing Unrooted Evolutionary Trees (MYK, TWL, TMP, WKS, HFT), pp. 54–65.

STOC-1997-ColeH #pattern matching #random #set

Tree Pattern Matching and Subset Matching in Randomized O(n log3m) Time (RC, RH), pp. 66–75.

STOC-1997-GrigorievK #bound #random

Randomized Ω(n²) Lower Bound for Knapsack (DG, MK), pp. 76–85.

STOC-1997-PaturiSZ #bound #exponential

Exponential Lower Bounds for Depth 3 Boolean Circuits (RP, MES, FZ), pp. 86–91.

STOC-1997-Vardy #algorithm #complexity #distance #problem

Algorithmic Complexity in Coding Theory and the Minimum Distance Problem (AV), pp. 92–109.

STOC-1997-LeonardiR #approximate #parallel

Approximating Total Flow Time on Parallel Machines (SL, DR), pp. 110–119.

STOC-1997-EdmondsCBD #execution #multi #scheduling

Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (JE, DDC, TB, XD), pp. 120–129.

STOC-1997-Albers #bound #online #scheduling

Better Bounds for Online Scheduling (SA), pp. 130–139.

STOC-1997-PhillipsSTW #scheduling

Optimal Time-Critical Scheduling via Resource Augmentation (CAP, CS, ET, JW), pp. 140–149.

STOC-1997-LubyMSSS

Practical Loss-Resilient Codes (ML, MM, MAS, DAS, VS), pp. 150–159.

STOC-1997-LaffertyR

Spectral Techniques for Expander Codes (JDL, DNR), pp. 160–167.

STOC-1997-Pan #equation #performance

Faster Solution of the Key Equation for Decoding BCH Error-Correcting Codes (VYP), pp. 168–175.

STOC-1997-AharonovB #constant #fault tolerance #quantum

Fault-Tolerant Quantum Computation With Constant Error (DA, MBO), pp. 176–188.

STOC-1997-NaorR #on the #permutation #pseudo #revisited

On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (MN, OR), pp. 189–199.

STOC-1997-ChenK

Reducing Randomness via Irrational Numbers (ZZC, MYK), pp. 200–209.

STOC-1997-Mulmuley #algebra #exclamation #proving #question

Is There an Algebraic Proof for P != NC? (KM), pp. 210–219.

STOC-1997-ImpagliazzoW #exponential

P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma (RI, AW), pp. 220–229.

STOC-1997-ArmoniTWZ

SL <= L4/3 (RA, ATS, AW, SZ), pp. 230–239.

STOC-1997-Karger #graph #random #using

Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs (DRK), pp. 240–249.

STOC-1997-BelingV #combinator #complexity

Combinatorial Complexity of the Central Curve (PAB, SV), pp. 250–255.

STOC-1997-DuhF #approximate #optimisation

Approximation of k-Set Cover by Semi-Local Optimization (RcD, MF), pp. 256–264.

STOC-1997-ShmoysTA #algorithm #approximate #problem

Approximation Algorithms for Facility Location Problems (DBS, ÉT, KA), pp. 265–274.

STOC-1997-AsanoKTT #approximate #polynomial #towards

Covering Points in the Plane by k-Tours: Towards a Polynomial Time Approximation Scheme for General k (TA, NK, HT, TT), pp. 275–283.

STOC-1997-AjtaiD #equivalence #worst-case

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence (MA, CD), pp. 284–293.

STOC-1997-OstrovskyS

Private Information Storage (RO, VS), pp. 294–303.

STOC-1997-ChorG #information retrieval

Computationally Private Information Retrieval (BC, NG), pp. 304–313.

STOC-1997-AuerLS #approximate #learning #pseudo #set

Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets (PA, PML, AS), pp. 314–323.

STOC-1997-Ben-DavidBK #algorithm #composition #concept #geometry #learning #theorem

A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes (SBD, NHB, EK), pp. 324–333.

STOC-1997-FreundSSW #predict #using

Using and Combining Predictors That Specialize (YF, RES, YS, MKW), pp. 334–343.

STOC-1997-BermanC #algorithm #online #problem

On-Line Algorithms for Steiner Tree Problems (PB, CC), pp. 344–353.

STOC-1997-AwerbuchS #algorithm #multi #online

Online Algorithms for Selective Multicast and Maximal Dense Trees (BA, TS), pp. 354–362.

STOC-1997-ParnafesRW #communication #modelling #problem

Direct Product Results and the GCD Problem, in Old and New Communication Models (IP, RR, AW), pp. 363–372.

STOC-1997-Dietzfelbinger #communication #complexity #problem

The Linear-Array Problem in Communication Complexity Resolved (MD), pp. 373–382.

STOC-1997-Babai #formal method

Paul Erdös (1913-1996): His Influence on the Theory of Computing (LB), pp. 383–401.

STOC-1997-McCuaigRST

Permanents, Pfaffian Orientations, and Even Directed Circuits (WM, NR, PDS, RT), pp. 402–405.

STOC-1997-GoldreichR #bound #graph #testing

Property Testing in Bounded Degree Graphs (OG, DR), pp. 406–415.

STOC-1997-AlbersH

Exploring Unknown Environments (SA, MRH), pp. 416–425.

STOC-1997-He #graph #on the

On Floorplans of Planar Graphs (XH), pp. 426–435.

STOC-1997-CramerD #linear #performance #proving

Linear Zero-Knowledge — A Note on Efficient Zero-Knowledge Proofs and Arguments (RC, ID), pp. 436–445.

STOC-1997-Beaver #encryption

Commodity-Based Cryptography (DB), pp. 446–455.

STOC-1997-Micciancio #data type #encryption

Oblivious Data Structures: Applications to Cryptography (DM), pp. 456–464.

STOC-1997-AlonDMPT #linear #question

Is Linear Hashing Good? (NA, MD, PBM, EP, GT), pp. 465–474.

STOC-1997-RazS

A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP (RR, SS), pp. 475–484.

STOC-1997-AroraS #testing

Improved Low-Degree Testing and its Applications (SA, MS), pp. 485–495.

STOC-1997-KilianPT #proving

Probabilistically Checkable Proofs with Zero Knowledge (JK, EP, GT), pp. 496–505.

STOC-1997-FeigeK #game studies

Making Games Short (UF, JK), pp. 506–516.

STOC-1997-MaggsV #multi #sorting

Improved Routing and Sorting on Multibutterflies (BMM, BV), pp. 517–530.

STOC-1997-BroderFU #approach #graph #random

Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (AZB, AMF, EU), pp. 531–539.

STOC-1997-ArgeFGV #memory management #on the #sorting #string

On Sorting Strings in External Memory (LA, PF, RG, JSV), pp. 540–548.

STOC-1997-NisanB #concurrent #pointer

Pointer Jumping Requires Concurrent Read (NN, ZBY), pp. 549–558.

STOC-1997-Aspnes #bound #distributed #random

Lower Bounds for Distributed Coin-Flipping and Randomized Consensus (JA), pp. 559–568.

STOC-1997-MalkhiR

Byzantine Quorum Systems (DM, MKR), pp. 569–578.

STOC-1997-LoH #robust

All of Us are Smarter Than Any of Us: Wait-Free Hierarchies are not Robust (WKL, VH), pp. 579–588.

STOC-1997-HerlihyR #decidability #distributed

The Decidability of Distributed Decision Tasks (MH, SR), pp. 589–598.

STOC-1997-Kleinberg #algorithm #nearest neighbour

Two Algorithms for Nearest-Neighbor Search in High Dimensions (JMK), pp. 599–608.

STOC-1997-Clarkson #metric #nearest neighbour #query

Nearest Neighbor Queries in Metric Spaces (KLC), pp. 609–617.

STOC-1997-IndykMRV #multi

Locality-Preserving Hashing in Multidimensional Spaces (PI, RM, PR, SV), pp. 618–625.

STOC-1997-CharikarCFM #clustering #incremental #information management #information retrieval

Incremental Clustering and Dynamic Information Retrieval (MC, CC, TF, RM), pp. 626–635.

STOC-1997-SrinivasanT #algorithm #approximate

A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria (AS, CPT), pp. 636–643.

STOC-1997-OstrovskyR #algorithm

Universal O(Congestion + Dilation + log1+epsilonN) Local Control Packet Switching Algorithms (RO, YR), pp. 644–653.

STOC-1997-KargerLLPLL #consistency #distributed #protocol #random #web

Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web (DRK, EL, FTL, RP, MSL, DL), pp. 654–663.

STOC-1997-KleinbergRT

Allocating Bandwidth for Bursty Connections (JMK, YR, ÉT), pp. 664–673.

STOC-1997-GoreJ #process

The Swendsen-Wang Process Does Not Always Mix Rapidly (VG, MJ), pp. 674–681.

STOC-1997-LubyV #approximate

Approximately Counting Up To Four (ML, EV), pp. 682–687.

STOC-1997-Fill #algorithm #markov

An Interruptible Algorithm for Perfect Sampling via Markov Chains (JAF), pp. 688–695.

STOC-1997-KannanV

Sampling Lattice Points (RK, SV), pp. 696–700.

STOC-1997-Irani #multi #web

Page Replacement with Multi-Size Pages and Applications to Web Caching (SI), pp. 701–710.

STOC-1997-BartalBBT #algorithm

A polylog(n)-Competitive Algorithm for Metrical Task Systems (YB, AB, CB, AT), pp. 711–719.

STOC-1997-MacielP #on the #proving

On ACC0[pk] Frege Proofs (AM, TP), pp. 720–729.

STOC-1997-AgrawalAIPR #complexity #reduction

Reducing the Complexity of Reductions (MA, EA, RI, TP, SR), pp. 730–738.

STOC-1997-RazborovWY #branch #calculus #proving #source code

Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus (AAR, AW, ACCY), pp. 739–748.

STOC-1997-ChungY #graph

Eigenvalues, Flows and Separators of Graphs (FRKC, STY), p. 749.

STOC-1997-FortnowS #linear #probability

Retraction of Probabilistic Computation and Linear Time (LF, MS), p. 750.