15 Explicit capacity-achieving list-decodable codes.
9 Gowers uniformity, influence of variables, and PCPs.
5 Sub-constant error low degree test of almost-linear size.
8 The Santa Claus problem.
10 On maximizing welfare when utility functions are subadditive.
7 A randomized polynomial-time simplex algorithm for linear programming.
22 Reducibility among equilibrium problems.
40 The complexity of computing a Nash equilibrium.
2 New trade-offs in cost-sharing mechanisms.
1 The effect of collusion in congestion games.
3 Black-box constructions for secure computation.
6 Information-theoretically secure protocols and security under composition.
2 Private approximation of search problems.
3 The changing face of web search: algorithms, auctions and advertising.
8 On the solution-space geometry of random constraint satisfaction problems.
7 Counting independent sets up to the tree threshold.
4 The DLT priority sampling is essentially optimal.
5 Optimal phylogenetic reconstruction.
1 Time-space tradeoffs for implementations of snapshots.
3 Byzantine agreement in the full-information model in O(log n) rounds.
1 Fast leader-election protocols with bounded cheaters' edge.
1 Pricing for fairness: distributed resource allocation for multiple objectives.
9 Near-optimal algorithms for unique games.
1 New approximation guarantee for chromatic number.
0 Finding a maximum weight triangle in n<sup>3-Delta</sup> time, with applications.
6 Time-space trade-offs for predecessor search.
26 The PCP theorem by gap amplification.
6 A combinatorial characterization of the testable graph properties: it's all about regularity.
6 Graph limits and parameter testing.
9 Advances in metric embedding theory.
8 Zero knowledge with efficient provers.
11 Zero-knowledge against quantum attacks.
2 Local zero knowledge.
3 A quasi-polynomial time approximation scheme for minimum weight triangulation.
0 Building triangulations using epsilon-nets.
3 The distance trisector curve.
16 Conditional hardness for approximate coloring.
8 Clique-width minimization is NP-hard.
2 Hardness of approximate two-level logic minimization and PAC learning with membership queries.
1 Can every randomized algorithm be derandomized?
0 Finding small balanced separators.
3 Graph partitioning using single commodity flows.
2 Linear time low tree-width partitions and algorithmic consequences.
0 Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs.
4 Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications.
25 A polynomial quantum algorithm for approximating the Jones polynomial.
7 On the fourier tails of bounded functions over the discrete cube.
9 Lattice problems and norm embeddings.
2 Pseudorandom walks on regular digraphs and the RL vs. L problem.
0 An efficient algorithm for solving word equations.
0 Online trading algorithms and robust option pricing.
1 On adequate performance measures for paging.
7 Extractors for a constant number of polynomially small min-entropy independent sources.
2 Narrow proofs may be spacious: separating space and width in resolution.
6 Logarithmic hardness of the directed congestion minimization problem.
3 Hardness of cut problems in directed graphs.
5 Integrality gaps for sparsest cut and minimum linear arrangement problems.
8 On earthmover distance, metric labeling, and 0-extension.
10 Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform.
2 On the importance of idempotence.
3 Searching dynamic point sets in spaces with bounded doubling dimension.
1 Learning a circuit by injecting values.
7 Bounded-error quantum state identification and exponential separations in communication complexity.
15 Limitations of quantum coset states for graph isomorphism.
2 A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs.
3 New upper and lower bounds for randomized and quantum local search.
10 Truthful randomized mechanisms for combinatorial auctions.
8 Fast convergence to Wardrop equilibria by adaptive sampling methods.
4 Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree.
5 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.
18 Linear degree extractors and the inapproximability of max clique and chromatic number.
3 Deterministic extractors for small-space sources.
6 On basing one-way functions on NP-hardness.
2 On the randomness complexity of efficient sampling.
1 A quasi-PTAS for unsplittable flow on line graphs.
0 Minimizing average flow time on related machines.
0 Provably near-optimal sampling-based algorithms for Stochastic inventory control models.
3 A subset spanner for Planar graphs, : with application to subset TSP.
4 Edge-disjoint paths in Planar graphs with constant congestion.