175 A Constant-Factor Approximation Algorithm for the k-Median Problem.
21 A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow.
112 Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems.
20 PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.
30 Fast Approximate PCPs.
8 Approximate Testing with Relative Error.
9 All Pairs Lightest Shortest Paths.
13 Unique Maximum Matching Algorithms.
39 Improved Upper Bounds on Information-Theoretic Private Information Retrieval (Extended Abstract).
30 One-Way Functions Are Essential for Single-Server Private Information Retrieval.
10 On targeting Markov segments.
30 Exploiting Regularities in Web Traffic Patterns for Cache Replacement.
5 Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns.
427 Algorithmic Mechanism Design (Extended Abstract).
126 Construction of Extractors Using Pseudo-Random Generators (Extended Abstract).
69 Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
34 On Recycling the Randomness of States in Space Bounded Computation.
5 Security-Preserving Hardness-Amplification for Any Regular One-Way Function.
50 Scheduling in the Dark.
12 Scheduling Data Transfers in a Network and the Set Scheduling Problem.
47 Minimizing the Flow Time Without Migration.
42 Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks.
13 From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols.
42 Chinese Remaindering with Errors.
22 A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes.
209 Oblivious Transfer and Polynomial Evaluation.
9 Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract).
5 Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract).
12 Lifting Markov Chains to Speed up Mixing.
43 Faster Mixing via Average Conductance.
6 Majorizing Estimators and the Approximation of #P-Complete Problems.
99 Optimal Bounds for the Predecessor Problem.
26 A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube.
51 Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems.
25 Molecular Scale Heat Engines and Scalable Quantum Computation.
31 Quantum Fourier Sampling Simplified.
18 Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model.
12   A Theorem on Sensitivity and Applications in Private Computation.
86 Exponential Separation of Quantum and Classical Communication Complexity.
14 Undecidability on Quantum Finite Automata.
58 Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata.
65 The Quantum Query Complexity of Approximating the Median and Related Statistics.
26 Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme.
13 A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines.
42 Improved Approximation Schemes for Scheduling Unrelated Parallel Machines.
28 A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract).
65 Sublinear Time Algorithms for Metric Space Problems.
35 Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.
16 Covering Rectilinear Polygons with Axis-Parallel Rectangles.
12 Compact Grid Layouts of Multi-Level Networks.
36 Complexity of Graph Partition Problems.
90 Finding Similar Regions in Many Strings.
13 Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems.
44 A Fully Dynamic Algorithm for Maintaining the Transitive Closure.
14 Worst-Case and Amortised Optimality in Union-Find (Extended Abstract).
10 The Complexity of the Matrix Eigenproblem.
160 Short Proofs are Narrow - Resolution Made Simple.
2 On the Complexity of Diophantine Geometry in Low Dimensions (Extended Abstract).
129 Pseudorandom Generators Without the XOR Lemma (Extended Abstract).
25 Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes.
4 Packet Routing with Arbitrary End-to-End Delay Requirements.
0 Static and Dynamic Evaluation of QoS Properties.
4 Efficient Recovery from Power Outage (Extended Abstract).
15 Nonmonotonic Phenomena in Packet Routing.
19 Graph Ramsey Theory and the Polynomial Hierarchy.
19 The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling.
15 Connection Caching.
70 Approximating the Throughput of Multiple Machines Under Real-Time Scheduling.
19 Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract).
24 Robust Logics.
6 Hypergraph Isomorphism and Structural Equivalence of Boolean Functions.
94 Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.
43 Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut.
86 Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems.
21 Approximation Schemes for Minimum Latency Problems.
17 Embedding Tree Metrics Into Low Dimensional Euclidean Spaces.
7 Computational Sample Complexity and Attribute-Efficient Learning.
20 On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice.
22 Satisfiability of Word Equations with Constants is in NEXPTIME.
12 Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time.
1 Inerpolation of Symmetric Functions and a New Type of Combinatorial Design.
9 Small Universal Graphs.
32 Design Networks with Bounded Pairwise Distance.
33 Random Sampling of Large Planar Maps and Convex Polyhedra.
43 Efficient Computation of Geodesic Shortest Paths.
5 Backing Up in Singly Linked Lists.