The Closest Substring problem with small distances, Dániel Marx
A Characterization of the (natural) Graph Properties Testable with One-Sided
Error, Noga Alon and Asaf Shapira
Answering distance queries in directed graphs using fast matrix
multiplication, Raphael Yuster and Uri Zwick
Additive Approximation for Edge-Deletion Problems, Noga Alon and Asaf
Shapira and Benny Sudakov
Analysis and Prediction of the Long-Run Behavior of Probabilistic Sequential
Programs with Recursion, Tomas Brazdil and Javier Esparza and Antonin Kucera
Approximation Algorithms for Unique Games, Luca Trevisan
The Symmetric Group Defies Strong Fourier Sampling, Cristopher Moore and
Alexander Russell and Leonard J. Schulman
Almost Orthogonal Linear Codes are Locally
Testable, Tali Kaufman and Simon Litsyn
Cryptography in the Bounded Quantum-Storage Model, Ivan Damgaard and Serge
Fehr and Louis Salvail and Christian Schaffner
An algorithmic version of the hypergraph regularity method, P. Haxell and B.
Nagle and V. Rodl
A Recursive Greedy Algorithm for Walks in Directed Graphs, Chandra Chekuri
and Martin Pal
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications,
Avi Wigderson and David Xiao
Quantum Information and the PCP Theorem , Ran Raz
Structuring labeled trees for optimal succinctness, and beyond, P. Ferragina
and F. Luccio and G. Manzini and S. Muthukrishnan
Nonembeddability theorems via Fourier analysis, Subhash Khot and Assaf Naor
Safraless Decision Procedures, Orna Kupferman and Moshe Y. Vardi
Approximation Algorithms and Mechanism Design for Scheduling on Multiple
Machines, V. S. Anil Kumar and Madhav V. Marathe and Srinivasan
Parthasarathy and Aravind Srinivasan
Query Incentive Networks, Jon Kleinberg and Prabhakar Raghavan
An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree
Planar Graphs, Jon Kleinberg
The Complexity of Online Memory Checking, Moni Naor and Guy N. Rothblum
From optimal measurement to efficient quantum algorithms for the hidden
subgroup problem over semidirect product groups, Dave Bacon and Andrew M.
Childs and Wim van Dam
Noise stability of functions with low influences: invariance and optimality,
Elchanan Mossel and Ryan O'Donnell and Krzysztof Oleszkiewicz
Group-theoretic Algorithms for Matrix Multiplication, Henry Cohn and Robert
Kleinberg and Balazs Szegedy and Christopher Umans
Deterministic Extractors for Affine Sources over Large Fields, Ariel Gabizon
and Ran Raz
On the Complexity of Two-Player Win-Lose Games, Tim Abbott and Daniel Kane
and Paul Valiant
On the Complexity of Real Functions, Mark Braverman
A general lower bound for mixing of single-site dynamics on graphs, Thomas
P. Hayes and Alistair Sinclair
Metric Embeddings with Relaxed Guarantees, Ittai Abraham, Yair Bartal, T-H.
Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, Ofer Neiman, and
Aleksandrs Slivkins
Towards a Final Analysis of Pairing Heaps, Seth Pettie
On Learning Mixtures of Heavy-Tailed Distributions, Anirban Dasgupta and
John Hopcroft and Jon Kleinberg and Mark Sandler
Learning mixtures of product distributions over discrete domains, Jon
Feldman and Ryan O'Donnell and Rocco A. Servedio
Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring,
Erik D. Demaine and MohammadTaghi Hajiaghayi and Ken-ichi Kawarabayashi
A Tale of Two Dimensional Bin Packing, Nikhil Bansal and Andrea Lodi and
Maxim Sviridenko
The Unique Games Conjecture, Integrality Gap for Cut Problems and
Embeddability of Negative Type Metrics into $\ell_1$, Subhash Khot, Nisheeth
Vishnoi
Linear Lower Bounds on Real-World Implementations of Concurrent Objects,
Faith Ellen Fich, Danny Hendler, Nir Shavit
Sampling-based Approximation Algorithms for Multi-Stage Stochastic
Optimization, Chaitanya Swamy and David B. Shmoys
How To Play Almost Any Mental Game Over the Net
-Concurrent Composition via Super-Polynomial Simulation, Boaz Barak and Amit Sahai
Nash Equilibria in Random Games, Imre Barany and Santosh Vempala and Adrian
Vetta
Sink Equilibria and Convergence, Vahab Mirrokni and Adrian Vetta
Every decision tree has an influential variable , Ryan O'Donnell and Michael
Saks and Oded Schramm and Rocco Servedio
Truthful and Near-optimal Mechanism Design via Linear Programming, Ron Lavi
and Chaitanya Swamy
Agnostically Learning Halfspaces, Adam Kalai and Adam Klivans and Yishay
Mansour and Rocco Servedio
Hardness of Undirected Edge Disjoint Paths with Congestion, Matthew Andrews,
Julia Chuzhoy, Sanjeev Khanna, and Lisa Zhang
Concurrent Non-Malleable Commitments, Rafael Pass and Alon Rosen
The Parking Permit Problem, Adam Meyerson
Mechanism Design via Machine Learning, Maria-Florina Balcan and Avrim Blum
and Jason Hartline and Yishay Mansour
On the Impossibility of Obfuscation with Auxiliary Inputs, Shafi Goldwasser
and Yael Tauman Kalai
How to Pay, Come What May : Approximation Algorithms for Demand-Robust
Covering Problems, Kedar Dhamdhere and Vineet Goyal and R. Ravi and Mohit
Singh
Improved Smoothed Analysis of the Shadow Vertex Simplex Method, Amit
Deshpande and Daniel A. Spielman
Beyond VCG: Frugality of Truthful Mechanisms, Anna R. Karlin and David Kempe
and Tami Tamir
Fitting tree metrics: Hierarchical clustering and Phylogeny, Nir Ailon and
Moses Charikar
Error-Correcting Codes for Automatic Control, Rafail Ostrovsky and Yuval
Rabani and Leonard J. Schulman
On Non-Approximability for Quadratic Programs, Sanjeev Arora and Eli Berger
and Elad Hazan and Guy Kindler and Muli Safra
A linear-time approximation scheme for planar weighted TSP, Philip N. Klein
Fast Algorithms for Approximate Semidefinite Programming using the
Multiplicative Weights Update Method, Sanjeev Arora and Elad Hazan and
Satyen Kale
AdWords and Generalized On-line Matching, Aranyak Mehta and Amin Saberi and
Umesh Vazirani and Vijay Vazirani
Hardness of Approximating the Closest Vector Problem with Pre-Processing,
Mikhail Alekhnovich and Subhash A. Khot and Guy Kindler and Nisheeth K.
Vishnoi
Universal Mechanism Design, Sergei Izmalkov, Matt Lepinski and Silvio Micali
Lower-bounds for the noisy broadcast model, and for generalized
noisy-decision trees, Navin Goyal and Guy Kindler and Michael Saks
Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time,
Farzad Parvaresh and Alexander Vardy
On Delsarte's Linear Programming Bounds for Binary Codes, Michael Navon and
Alex Samorodnitsky
Error Correction via Linear Programming. Emmanuel J. Candes and Mark
Rudelson and Terence Tao and Roman Vershynin.