[22] Recognizing string graphs in NP.
[7] Dynamic subgraph connectivity with geometric applications.
[50] New results on monotone dualization and generating hypergraph transversals.
[31] Combinatorial optimization problems in self-assembly.
[95] The importance of being biased.
[7] On the advantage over a random assignment.
[10] The complexity of choosing an H-colouring (nearly) uniformly at random.
[8] Random sampling in residual graphs.
[106] On the complexity of equilibria.
[80] Competitive generalized auctions.
[29] Competitive recommendation systems.
[0] The Glauber dynamics on colourings of a graph with high girth and maximum degree.
[8] Clairvoyant scheduling of random walks.
[28] Solving convex programs by random walks.
[3] The Joy of Theory.
[18] Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths.
[5] Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines.
[18] On randomized online scheduling.
[19] On the complexity of matrix product.
[40] Near-optimal sparse fourier representations via sampling.
[3] Fitting algebraic curves to noisy data.
[18] A new average case analysis for completion time scheduling.
[12] A unified analysis of hot video schedulers.
[40] Optimal rate-based scheduling on multiprocessors.
[28] Almost all graphs with average degree 4 are 3-colorable.
[15] Models and thresholds for random constraint satisfaction problems.
[0] Reimer's inequality and tardos' conjecture.
[11] Clifford algebras and approximating the permanent.
[40] Random sampling and approximation of MAX-CSP problems.
[11] A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant.
[81] Approximate clustering via core-sets.
[7] On paging with locality of reference.
[47] Cache-oblivious priority queue and graph algorithm applications.
[8] Average case analysis for batched disk scheduling and increasing subsequences.
[64] Selfish traffic allocation for server farms.
[33] Approximation schemes for preemptive weighted flow time.
[46] Approximation algorithms for minimum-cost k-vertex connected subgraphs.
[28] Equitable cost allocations via primal-dual-type algorithms.
[13] 2-round zero knowledge and proof auditors.
[24] Concurrent zero-knowledge with timing, revisited.
[16] Tight security proofs for the bounded-storage model.
[36] Hardness results for approximate hypergraph coloring.
[30] Space lower bounds for distance approximation in the data stream model.
[24] Approximate counting of inversions in a data stream.
[60] Similarity estimation techniques from rounding algorithms.
[122] Fast, small-space algorithms for approximate histogram maintenance.
[19] Stability of load balancing algorithms in dynamic adversarial systems.
[60] Tradeoffs in probabilistic packet marking for IP traceback.
[17] Crawling on web graphs.
[117] The price of anarchy is independent of the network topology.
[15] Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem.
[10] An exponential separation between regular and general resolution.
[11] Size space tradeoffs for resolution.
[8] Exact learning of DNF formulas using DNF hypotheses.
[35] Monotonicity testing over general poset domains.
[33] Strict polynomial-time in simulation and extraction.
[94] Universally composable two-party and multi-party secure computation.
[5] The invasiveness of off-line memory checking.
[28] On the composition of authenticated byzantine agreement.
[27] Wait-free consensus with infinite arrivals.
[81] Relations between average case complexity and approximation complexity.
[0] Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon.
[44] Resolution lower bounds for the weak pigeonhole principle.
[14] Hard examples for bounded depth frege.
[11] Meldable heaps and boolean union-find.
[14] Optimal finger search trees in the pointer machine.
[18] Verifying candidate matches in sparse and wildcard matching.
[24] Deterministic sorting in O(nlog log n) time and linear space.
[15] Improved cryptographic hash functions with worst-case/average-case connection.
[17] Algorithmic derandomization via complexity theory.
[38] Pseudo-random generators for all hardnesses.
[67] Quantum lower bound for the collision problem.
[20] Secure multi-party quantum computation.
[78] Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem.
[32] Randomness conductors and constant-degree lossless expanders.
[10] Expanders from symmetric codes.
[9] The complexity of approximating entropy.
[26] Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems.
[12] On communication over an entanglement-assisted quantum channel.
[17] Girth and euclidean distortion.
[0] Computing the betti numbers of arrangements.
[15] Space-efficient approximate Voronoi diagrams.
[95] A new greedy approach for facility location problems.
[117] Finding nearest neighbors in growth-restricted metrics.
[9] Hardness amplification within NP.
[0] 3-manifold knot genus is NP-complet.
[74] On the power of unique 2-prover 1-round games.
[0] Learnability beyond AC0.
[12] Huffman coding with unequal letter costs.
[26] Approximating the smallest grammar: Kolmogorov complexity in natural models.
[8] Limits to list decodability of linear codes.
[33] Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets.

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