Jeffrey Scott Vitter, Lawrence L. Larmore, Frank Thomson Leighton
Proceedings of the 31st Annual ACM Symposium on Theory of Computing
STOC, 1999.

@proceedings{STOC-1999,
	address       = "Atlanta, Georgia, USA",
	editor        = "Jeffrey Scott Vitter and Lawrence L. Larmore and Frank Thomson Leighton",
	isbn          = "1-58113-067-8",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 31st Annual ACM Symposium on Theory of Computing}",
	year          = 1999,
}

Contents (86 items)

13 ×#approximate
13 ×#problem
10 ×#complexity
9 ×#algorithm
9 ×#bound
7 ×#polynomial
6 ×#performance
6 ×#quantum
5 ×#multi
5 ×#scheduling

STOC-1999-CharikarGTS #algorithm #approximate #problem

A Constant-Factor Approximation Algorithm for the k-Median Problem (MC, SG, ÉT, DBS), pp. 1–10.

STOC-1999-Wayne #algorithm #combinator #polynomial

A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow (KDW), pp. 11–18.

STOC-1999-GuruswamiKRSY #algorithm #approximate #problem

Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems (VG, SK, RR, FBS, MY), pp. 19–28.

STOC-1999-DinurFKRS #towards

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability (ID, EF, GK, RR, SS), pp. 29–40.

STOC-1999-ErgunKR #approximate #performance

Fast Approximate PCPs (FE, RK, RR), pp. 41–50.

STOC-1999-KiwiMS #approximate #fault #testing

Approximate Testing with Relative Error (MAK, FM, MS), pp. 51–60.

STOC-1999-Zwick

All Pairs Lightest Shortest Paths (UZ), pp. 61–69.

STOC-1999-GabowKT #algorithm

Unique Maximum Matching Algorithms (HNG, HK, RET), pp. 70–78.

STOC-1999-IshaiK #bound #information retrieval

Improved Upper Bounds on Information-Theoretic Private Information Retrieval (YI, EK), pp. 79–88.

STOC-1999-BeimelIKM #information retrieval

One-Way Functions Are Essential for Single-Server Private Information Retrieval (AB, YI, EK, TM), pp. 89–98.

STOC-1999-CharikarKRRT #markov #on the

On targeting Markov segments (MC, RK, PR, SR, AT), pp. 99–108.

STOC-1999-CohenK #web

Exploiting Regularities in Web Traffic Patterns for Cache Replacement (EC, HK), pp. 109–118.

STOC-1999-ChenKLW #bound

Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns (GHC, MYK, YDL, HKW), pp. 119–128.

STOC-1999-NisanR #algorithm #design

Algorithmic Mechanism Design (NN, AR), pp. 129–140.

STOC-1999-Trevisan #generative #pseudo #using

Construction of Extractors Using Pseudo-Random Generators (LT), pp. 141–148.

STOC-1999-RazRV #fault

Extracting all the Randomness and Reducing the Error in Trevisan’s Extractors (RR, OR, SPV), pp. 149–158.

STOC-1999-RazR #bound #on the

On Recycling the Randomness of States in Space Bounded Computation (RR, OR), pp. 159–168.

STOC-1999-CrescenzoI

Security-Preserving Hardness-Amplification for Any Regular One-Way Function (GDC, RI), pp. 169–178.

STOC-1999-Edmonds #scheduling

Scheduling in the Dark (JE), pp. 179–188.

STOC-1999-GoelHPT #data transfer #network #problem #scheduling #set

Scheduling Data Transfers in a Network and the Set Scheduling Problem (AG, MRH, SAP, ÉT), pp. 189–197.

STOC-1999-AwerbuchALR #migration

Minimizing the Flow Time Without Migration (BA, YA, SL, OR), pp. 198–205.

STOC-1999-Gamarnik #adaptation #network #policy

Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks (DG), pp. 206–214.

STOC-1999-ScheidelerV #performance #protocol

From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols (CS, BV), pp. 215–224.

STOC-1999-GoldreichRS #fault

Chinese Remaindering with Errors (OG, DR, MS), pp. 225–234.

STOC-1999-OlshevskyS #algebra #approach #geometry #performance

A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes (VO, MAS), pp. 235–244.

STOC-1999-NaorP #evaluation #polynomial

Oblivious Transfer and Polynomial Evaluation (MN, BP), pp. 245–254.

STOC-1999-CanettiO #question #what

Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (RC, RO), pp. 255–264.

STOC-1999-DinitzMR #complexity #symmetry

Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (YD, SM, SR), pp. 265–274.

STOC-1999-ChenLP #markov

Lifting Markov Chains to Speed up Mixing (FC, LL, IP), pp. 275–281.

STOC-1999-LovaszK #performance

Faster Mixing via Average Conductance (LL, RK), pp. 282–287.

STOC-1999-SchulmanV #approximate #problem

Majorizing Estimators and the Approximation of #P-Complete Problems (LJS, VVV), pp. 288–294.

STOC-1999-BeameF #bound #problem

Optimal Bounds for the Predecessor Problem (PB, FEF), pp. 295–304.

STOC-1999-ChakrabartiCGL #approximate #bound #complexity #nearest neighbour

A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube (AC, BC, BG, AL), pp. 305–311.

STOC-1999-BorodinOR #bound #nearest neighbour #problem

Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems (AB, RO, YR), pp. 312–321.

STOC-1999-SchulmanV99a #quantum #scalability

Molecular Scale Heat Engines and Scalable Quantum Computation (LJS, UVV), pp. 322–329.

STOC-1999-HalesH #fourier #quantum

Quantum Fourier Sampling Simplified (LH, SH), pp. 330–338.

STOC-1999-RussellSZ #bound

Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model (AR, MES, DZ), pp. 339–347.

STOC-1999-GalR #theorem

A Theorem on Sensitivity and Applications in Private Computation (AG, AR), pp. 348–357.

STOC-1999-Raz #communication #complexity #exponential #quantum

Exponential Separation of Quantum and Classical Communication Complexity (RR), pp. 358–367.

STOC-1999-AmanoI #automaton #finite #quantum

Undecidability on Quantum Finite Automata (MA, KI), pp. 368–375.

STOC-1999-AmbainisNTV #automaton #bound #quantum

Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata (AA, AN, ATS, UVV), pp. 376–383.

STOC-1999-NayakW #approximate #complexity #quantum #query #statistics

The Quantum Query Complexity of Approximating the Median and Related Statistics (AN, FW), pp. 384–393.

STOC-1999-JansenSS #approximate #polynomial

Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme (KJ, RSO, MS), pp. 394–399.

STOC-1999-SkutellaW #parallel

A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines (MS, GJW), pp. 400–407.

STOC-1999-JansenP #approximate #parallel #scheduling

Improved Approximation Schemes for Scheduling Unrelated Parallel Machines (KJ, LP), pp. 408–417.

STOC-1999-ChenM #approximate #multi #polynomial #scheduling

A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (JC, AM), pp. 418–427.

STOC-1999-Indyk #algorithm #metric #problem #sublinear

Sublinear Time Algorithms for Metric Space Problems (PI), pp. 428–434.

STOC-1999-BorodinOR99a #algorithm #approximate #clustering #problem

Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces (AB, RO, YR), pp. 435–444.

STOC-1999-KumarR

Covering Rectilinear Polygons with Axis-Parallel Rectangles (VSAK, HR), pp. 445–454.

STOC-1999-MuthukrishnanPSS #grid #multi #network

Compact Grid Layouts of Multi-Level Networks (SM, MP, SCS, TS), pp. 455–463.

STOC-1999-FederHKM #complexity #graph #problem

Complexity of Graph Partition Problems (TF, PH, SK, RM), pp. 464–472.

STOC-1999-LiMW #string

Finding Similar Regions in Many Strings (ML, BM, LW), pp. 473–482.

STOC-1999-FerraginaMB #approach #geometry #multi #problem #string

Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems (PF, SM, MdB), pp. 483–491.

STOC-1999-KingS #algorithm #maintenance #transitive

A Fully Dynamic Algorithm for Maintaining the Transitive Closure (VK, GS), pp. 492–498.

STOC-1999-AlstrupBR #worst-case

Worst-Case and Amortised Optimality in Union-Find (SA, AMBA, TR), pp. 499–506.

STOC-1999-PanC #complexity #matrix #problem

The Complexity of the Matrix Eigenproblem (VYP, ZQC), pp. 507–516.

STOC-1999-Ben-SassonW #proving

Short Proofs are Narrow — Resolution Made Simple (EBS, AW), pp. 517–526.

STOC-1999-Rojas #complexity #geometry #on the

On the Complexity of Diophantine Geometry in Low Dimensions (JMR), pp. 527–536.

STOC-1999-SudanTV #generative #pseudo

Pseudorandom Generators Without the XOR Lemma (MS, LT, SPV), pp. 537–546.

STOC-1999-BussGIP #calculus #linear #polynomial

Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (SRB, DG, RI, TP), pp. 547–556.

STOC-1999-AndrewsZ #requirements

Packet Routing with Arbitrary End-to-End Delay Requirements (MA, LZ), pp. 557–565.

STOC-1999-PanduranganU #evaluation

Static and Dynamic Evaluation of QoS Properties (GP, EU), pp. 566–573.

STOC-1999-GuhaMNS #performance

Efficient Recovery from Power Outage (SG, AM, JN, BS), pp. 574–582.

STOC-1999-Feige

Nonmonotonic Phenomena in Packet Routing (UF), pp. 583–591.

STOC-1999-Schaefer #graph #polynomial

Graph Ramsey Theory and the Polynomial Hierarchy (MS), pp. 592–601.

STOC-1999-PonzioRV #communication #complexity #pointer

The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling (SP, JR, SV), pp. 602–611.

STOC-1999-CohenKZ

Connection Caching (EC, HK, UZ), pp. 612–621.

STOC-1999-Bar-NoyGNS #approximate #multi #realtime #scheduling #throughput

Approximating the Throughput of Multiple Machines Under Real-Time Scheduling (ABN, SG, JN, BS), pp. 622–631.

STOC-1999-Ajtai #linear #nondeterminism

Determinism versus Non-Determinism for Linear Time RAMs (MA), pp. 632–641.

STOC-1999-Valiant #logic #robust

Robust Logics (LGV), pp. 642–651.

STOC-1999-Luks #equivalence #morphism

Hypergraph Isomorphism and Structural Equivalence of Boolean Functions (EML), pp. 652–658.

STOC-1999-KlivansM #graph #morphism #polynomial #proving

Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses (AK, DvM), pp. 659–667.

STOC-1999-KargerKSTY #algorithm #geometry #multi

Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut (DRK, PNK, CS, MT, NEY), pp. 668–678.

STOC-1999-Zwick99a #problem #programming

Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems (UZ), pp. 679–687.

STOC-1999-AroraK #approximate #latency #problem

Approximation Schemes for Minimum Latency Problems (SA, GK), pp. 688–693.

STOC-1999-Gupta #metric

Embedding Tree Metrics Into Low Dimensional Euclidean Spaces (AG), pp. 694–700.

STOC-1999-Servedio #complexity #learning

Computational Sample Complexity and Attribute-Efficient Learning (RAS), pp. 701–710.

STOC-1999-BlomerS #complexity #independence #on the

On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice (JB, JPS), pp. 711–720.

STOC-1999-Plandowski #equation #satisfiability #word

Satisfiability of Word Equations with Constants is in NEXPTIME (WP), pp. 721–725.

STOC-1999-CaiNS #probability #theorem

Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time (JyC, AN, DS), pp. 726–735.

STOC-1999-Indyk99a #combinator #design #symmetry

Inerpolation of Symmetric Functions and a New Type of Combinatorial Design (PI), pp. 736–740.

STOC-1999-CapalboK #graph

Small Universal Graphs (MRC, SRK), pp. 741–749.

STOC-1999-DodisK #bound #design #distance #network

Design Networks with Bounded Pairwise Distance (YD, SK), pp. 750–759.

STOC-1999-Schaeffer #random #scalability

Random Sampling of Large Planar Maps and Convex Polyhedra (GS), pp. 760–769.

STOC-1999-Kapoor #performance

Efficient Computation of Geodesic Shortest Paths (SK), pp. 770–779.

STOC-1999-Ben-AmramP

Backing Up in Singly Linked Lists (AMBA, HP), pp. 780–786.