Proceedings of the 29th 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

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

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

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.

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.