[0] Zero-Knowledge.
[10] Randomness Extractors and their Many Guises.
[30] Locally Testable Codes and PCPs of Almost-Linear Length.
[21] Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs.
[20] The Hardness of 3 - Uniform Hypergraph Coloring.
[57] Minimizing Congestion in General Networks.
[11] Small Induced-Universal Graphs and Compact Implicit Graph Representations.
[28] Deterministic Broadcasting Time in Radio Networks of Unknown Topology.
[9] Explicit Unique-Neighbor Expanders.
[22] Abstract Combinatorial Programs and Efficient Property Testers.
[23] A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs.
[15] Testing Juntas.
[17] A Spectral Algorithm for Learning Mixtures of Distributions.
[14] Equivalence between Priority Queues and Sorting.
[18] Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space.
[12] Implicit B-Trees: New Results for the Dictionary Problem.
[2] An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree.
[3] PAC = PAExact and Other Equivalent Models in Learning.
[29] Learning Intersections and Thresholds of Halfspaces.
[19] On-Line Confidence Machines Are Well-Calibrated.
[7] Learning a Hidden Matching.
[41] An Information Statistics Approach to Data Stream and Communication Complexity.
[3] Static Optimality Theorem for External Memory String Access.
[7] A Simple Algorithmic Characterization of Uniform Solvability.
[98] Correlation Clustering.
[15] Decoding Turbo-Like Codes via Linear Programming.
[41] Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval.
[218] LT Codes.
[6] Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers.
[11] Scheduling Over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data.
[11] On-Line End-to-End Congestion Control.
[29] Proving Integrality Gaps without Knowing the Linear Program.
[25] Dependent Rounding in Bipartite Graphs.
[25] A Constant-Factor Approximation Algorithm for the Multicommodity.
[48] Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model.
[11] Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions.
[33] Concurrent Zero Knowledge with Logarithmic Round-Complexity.
[15] On the (non)Universality of the One-Time Pad.
[70] Market Equilibrium via a Primal-Dual-Type Algorithm.
[8] On the Hardness of Optimal Auctions.
[34] Auctions with Severely Bounded Communication.
[60] Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions.
[17] Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States.
[7] Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes.
[51] Authentication of Quantum Messages.
[19] imits on the Power of Quantum Statistical Zero-Knowledge.
[26] Protocols and Impossibility Results for Gossip-Based Communication Mechanisms.
[17] Covering Problems with Hard Capacities.
[29] Packing 2-Dimensional Bins in Harmony.
[11] Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems.
[50] Quantum Lower Bounds for the Collision and the Element Distinctness Problems.
[46] Quantum Computation and Lattice Problems.
[13] On the Decidability of Self-Assembly of Infinite Ribbons.
[18] The Parameterized Complexity of Counting Problems.
[6] Dimension Reduction in the ell _1 Norm.
[5] On Approximating the Radii of Point Sets in High Dimensions.
[21] Low-Dimensional Linear Programming with Violations.
[5] Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
[24] Satisfiability, Branch-Width and Tseitin Tautologies.
[20] A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution.
[38] Dynamic Planar Convex Hull.
[23] Optimal System of Loops on an Orientable Surface.
[12] The Partition Technique for Overlays of Envelopes.
[89] A Dichotomy Theorem for Constraints on a Three-Element Set.
[8] Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps.
[15] Power from Random Strings.
[14] Improved Dynamic Reachability Algorithms for Directed Graphs.
[25] Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks.
[6] Global Information from Local Observation.
[19] Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows.
[13] Spectral Gap and log-Sobolev Constant for Balanced Matroids.
[0] Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties.
[21] Graph Isomorphism is in SPP.
[34] Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection.
[17] Forbidden Information.
[26] The 3-XORSAT Threshold.
[39] The Asymptotic Order of the Random k -SAT Threshold.
[8] On Random Symmetric Travelling Salesman Problems.
[12] Load Balancing with Memory.
[4] Erratum to "Vickrey Pricing and Shortest Paths: What is an Edge Worth?".

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