[94] On the Limits of Non-Approximability of Lattice Problems.
[135] The Shortest Vector Problem in L₂ is NP-hard for Randomized Reductions (Extended Abstract).
[104] Quantum Circuits with Mixed States.
[25] Exact Sampling and Approximate Counting Techniques.
[12] A Polynomial Approximation Algorithm for the Minimum Fill-In Problem.
[56] An Improved Approximation Algorithm for Multiway Cut.
[91] A Framework for Fast Quantum Mechanical Algorithms.
[138] Quantum vs. Classical Communication and Computation.
[26] Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching.
[123] Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity.
[80] Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract).
[32] Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems.
[131] Approximation Schemes for Euclidean k-Medians and Related Problems.
[80] Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median.
[3] One Help Bit Doesn't Help.
[45] Perfectly One-Way Probabilistic Hash Functions (Preliminary Version).
[60] Non-Interactive and Non-Malleable Commitment.
[120] Protecting Data Privacy in Private Information Retrieval Schemes.
[200] On Approximating Arbitrary Metrices by Tree Metrics.
[12] Trees and Euclidean Metrics.
[3] Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness (Extended Abstract).
[20] Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners.
[28] Almost Optimal Dispersers.
[17] NP Might Not Be As Easy As Detecting Unique Solutions.
[340] The Random Oracle Methodology, Revisited (Preliminary Version).
[9] Randomized Complexity Lower Bounds.
[39] Weak Alternating Automata and Tree Automata Emptiness.
[23] Over Words, Two Variables Are as Powerful as One Quantifier Alternation.
[22] Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound.
[392] Analysis of Low Density Codes and Improved Designs Using Irregular Graphs.
[96] Spot-Checkers.
[55] The Power of a Pebble: Exploring and Mapping Directed Graphs.
[32] Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators.
[48] A Sublinear Bipartiteness Tester for Bunded Degree Graphs.
[27] Recycling Queries in PCPs and in Linearity Tests (Extended Abstract).
[26] The Closure of Monadic NP (Extended Abstract).
[0] Information Theoretic Implications for Pairing Heaps.
[142] Min-Wise Independent Permutations (Extended Abstract).
[19] The Approximability of NP-hard Problems.
[18] Algorithms for Capacitated Vehicle Routing.
[49] Adaptive Packet Routing for Bursty Adversarial Traffic.
[7] Stability Results for Networks with Input and Output Blocking.
[22] Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks.
[17] TCP Dynamic Acknowledgment Delay: Theory and Practice (Extended Abstract).
[47] Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge.
[182] Concurrent Zero-Knowledge.
[202] A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols (Extended Abstract).
[17] A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs.
[19] Checking Polynomial Identities over any Field: Towards a Derandomization?
[63] Multicasting in Heterogeneous Networks.
[53] Minimizing Stall Time in Single and Parallel Disk Systems.
[22] On Indexed Data Broadcast.
[74] Segmentation Problems.
[6] Computing Local Dimension of a Semialgebraic Set.
[24] Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations.
[0] A Black Box Approach to the Algebraic Set Decomposition Problem.
[14] Are Lower Bounds Easier over the Reals?
[39] Planar Map Graphs.
[36] Further Algorithmic Aspects of the Local Lemma.
[14] Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths Problem.
[71] Approximating Geometrical Graphs via "Spanners" and "Banyans".
[34] Finding Almost-Satisfying Assignments.
[81] On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas.
[5] K-sat on Groups and Undecidability.
[16] An Exponential Lower Bound for Depth 3 Arithmetic Circuits.
[6] A New Composition Theorem for Learning Algorithms.
[21] Adaptive versus Nonadaptive Attribute-Efficient Learning.
[131] On the Complexity of Protein Folding (Extended Abstract).
[414] Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.
[171] Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces.
[24] Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract).
[25] On Broadcast Disk Paging.
[49] A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents.
[25] On Separating the Read-k-Times Branching Program Hierarchy.
[102] Robust Efficient Distributed RSA-Key Generation.
[23] The Cost of the Missing Bit: Communication Complexity with Help.

Created by Piotr Indyk and Suresh Venkatasubramanian. Original idea by Michael Mitzenmacher.