[1] Confronting hardness using a hybrid approach.
[2] A new approach to proving upper bounds for MAX-2-SAT.
[0] Measure and conquer: a simple O(2^0.288n) independent set algorithm.
[0] A polynomial algorithm to find an independent set of maximum weight in a fork-free graph.
[0] The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity.
[2] Local versus global properties of metric spaces.
[3] Directed metrics and directed graph partitioning problems.
[8] Improved embeddings of graph metrics into random trees.
[1] Small hop-diameter sparse spanners for doubling metrics.
[13] Metric cotype.
[10] On nash equilibria for a network creation game.
[6] Approximating unique games.
[5] Computing sequential equilibria for two-player games.
[13] A deterministic subexponential algorithm for solving parity games.
[0] Finding nucleolus of flow game.
[0] Predicting the "unpredictable".
[0] A near-tight approximation lower bound and algorithm for the kidnapped robot problem.
[2] An asymptotic approximation algorithm for 3D-strip packing.
[0] Facility location with hierarchical facility costs.
[13] Combination can be hard: approximability of the unique coverage problem.
[0] Computing steiner minimum trees in Hamming metric.
[2] Robust shape fitting via peeling and grating coresets.
[4] Tightening non-simple paths and cycles on surfaces.
[0] Anisotropic surface meshing.
[3] Simultaneous diagonal flips in plane triangulations.
[4] Morphing orthogonal planar graph drawings.
[0] Overhang.
[11] On the capacity of information networks.
[0] Lower bounds for asymmetric communication channels and distributed source coding.
[0] Self-improving algorithms.
[0] Cake cutting really is not a piece of cake.
[3] Testing triangle-freeness in general graphs.
[6] Constraint solving via fractional edge covers.
[0] Testing graph isomorphism.
[3] Efficient construction of unit circular-arc models.
[6] On the chromatic number of some geometric hypergraphs.
[2] A robust maximum completion time measure for scheduling.
[0] Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling.
[5] Improved approximation algorithms for broadcast scheduling.
[5] Distributed selfish load balancing.
[3] Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management.
[8] Rank/select operations on large alphabets: a tool for text indexing.
[0] O(log log n)-competitive dynamic binary search trees.
[2] The rainbow skip graph: a fault-tolerant constant-degree distributed data structure.
[1] Design of data structures for mergeable trees.
[0] Implicit dictionaries with O(1) modifications per update and fast search.
[8] Sampling binary contingency tables with a greedy start.
[0] Asymmetric balanced allocation with simple hash functions.
[2] Balanced allocation on graphs.
[5] Superiority and complexity of the spaced seeds.
[3] Solving random satisfiable 3CNF formulas in expected polynomial time.
[1] Analysis of incomplete data and an intrinsic-dimension Helly theorem.
[2] Finding large sticks and potatoes in polygons.
[1] Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting.
[2] Vertical ray shooting and computing depth orders for fat objects.
[6] On the number of plane graphs.
[0] All-pairs shortest paths for unweighted undirected graphs in o(mn) time.
[0] An O (n log n) algorithm for maximum st-flow in a directed planar graph.
[0] A simple GAP-canceling algorithm for the generalized maximum flow problem.
[4] Four point conditions and exponential neighborhoods for symmetric TSP.
[0] Upper degree-constrained partial orientations.
[1] On the tandem duplication-random loss model of genome rearrangement.
[3] Reducing tile complexity for self-assembly through temperature programming.
[4] Cache-oblivious string dictionaries.
[8] Cache-oblivious dynamic programming.
[8] A computational study of external-memory BFS algorithms.
[10] Tight approximation algorithms for maximum general assignment problems.
[2] Approximating the k-multicut problem.
[7] The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema.
[5] 8/7-approximation algorithm for (1, 2)-TSP.
[3] Improved lower and upper bounds for universal TSP in planar metrics.
[10] Leontief economies encode nonzero sum two-player games.
[2] Bottleneck links, variable demand, and the tragedy of the commons.
[9] The complexity of quantitative concurrent parity games.
[2] Equilibria for economies with production: constant-returns technologies and production planning constraints.
[1] Approximation algorithms for wavelet transform coding of data streams.
[5] Simpler algorithm for estimating frequency moments of data streams.
[8] Trading off space for passes in graph streaming problems.
[3] Maintaining significant stream statistics over sliding windows.
[9] Streaming and sublinear approximation of entropy and information distances.
[0] FPTAS for mixed-integer polynomial optimization with a fixed number of variables.
[3] Linear programming and unique sink orientations.
[5] Generating all vertices of a polyhedron is hard.
[6] A semidefinite programming approach to tensegrity theory and realizability of graphs.
[6] Ordering by weighted number of wins gives a good ranking for weighted tournaments.
[0] Weighted isotonic regression under the L₁ norm.
[2] Oblivious string embeddings and edit distance approximations.
[3] Spanners and emulators with sublinear distance errors.
[0] Certifying large branch-width.
[5] DAG-width: connectivity measure for directed graphs.
[0] On the diameter of Eulerian orientations of graphs.
[1] Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition.
[0] Subgraph characterization of Red/Blue-Split Graph and König Egerváry Graphs.
[3] Critical chromatic number and the complexity of perfect packings in graphs.
[10] On the number of crossing-free matchings, (cycles, and partitions).
[0] Slow mixing of glauber dynamics via topological obstructions.
[17] Quantum verification of matrix products.
[13] Counting without sampling: new algorithms for enumeration problems using statistical physics.
[1] Accelerating simulated annealing for the permanent and combinatorial counting problems.
[2] Query-efficient algorithms for polynomial interpolation over composites.
[0] New lower bounds for oblivious routing in undirected graphs.
[2] Anytime algorithms for multi-armed bandit problems.
[7] Robbing the bandit: less regret in online geometric optimization against an adaptive adversary.
[2] On the competitive ratio of evaluating priced functions.
[13] Randomized online algorithms for minimum metric bipartite matching.
[0] Random graphs.
[2] Analyzing BitTorrent and related peer-to-peer networks.
[3] Oblivious network design.
[11] The price of being near-sighted.
[2] Scalable leader election.
[9] Deterministic boundary recognition and topology extraction for large sensor networks.
[0] Improved lower bounds for embeddings into L₁.
[0] l²₂ spreading metrics for vertex ordering problems.
[4] Trees and Markov convexity.
[1] An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routing.
[2] A tight upper bound on the probabilistic embedding of series-parallel graphs.
[3] Single-value combinatorial auctions and implementation in undominated strategies.
[13] An improved approximation algorithm for combinatorial auctions with submodular bidders.
[5] Revenue maximization when bidders have budgets.
[12] Knapsack auctions.
[9] Single-minded unlimited supply pricing on sparse instances.
[0] The complexity of matrix completion.
[2] Relating singular values and discrepancy of weighted directed graphs.
[12] Matrix approximation and projective clustering via volume sampling.
[0] Sampling algorithms for l₂ regression and applications.
[3] The hunting of the bump: on maximizing statistical discrepancy.
[8] A general approach for incremental approximation and hierarchical clustering.
[3] The space complexity of pass-efficient algorithms for clustering.
[2] Correlation clustering with a fixed number of clusters.
[0] On k-Median clustering in high dimensions.
[3] Entropy based nearest neighbor search in high dimensions.
[5] A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries.
[1] Efficient algorithms for substring near neighbor problem.
[1] Many distances in planar graphs.
[0] Pattern matching with address errors: rearrangement distances.
[12] Squeezing succinct data structures into entropy bounds.

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