Andrej Bogdanov and Emanuele Viola
Pseudorandom bits for polynomials via the Gowers norm

Zeev Dvir, Ariel Gabizon and Avi Wigderson
Extractors and rank extractors for polynomial sources

Louay Bazzi
Polylogarithmic independence can fool DNF formulas

Qi Cheng
Derandomization of sparse cyclotomic integer zero testing

Constantinos Daskalakis and Christos Papadimitriou
Computing equilibria in anonymous games

Frank McSherry and Kunal Talwar
Mechanism design via differential privacy

Nicole Immorlica, Anna Karlin, Mohammad Mahdian and Kunal Talwar
Balloon popping with applications to ascending auctions

Kousha Etessami and Mihalis Yannakakis
On the complexity of Nash equilibria and other fixed points

Xi Chen and Shang-Hua Teng
Paths beyond local search: a tight bound for randomized fixed-point computation

Philipp Hertel and Toniann Pitassi
Exponential time/space speedups for resolution and the PSPACE-completeness of black-white pebbling

Stefan Dantchev, Barnaby Martin and Stefan Szeider
Parameterized proof complexity

Eyal Lubetzky and Uri Stav
Non-linear index coding outperforming the linear optimum

Dániel Marx
Can you beat treewidth?

Daniel Štefankovic, Santosh Vempala and Eric Vigoda
Adaptive simulated annealing: a near-optimal connection between sampling and counting

Antoine Gerschenfeld and Andrea Montanari
Reconstruction for models on random graphs

Yun Long, Asaf Nachmias and Yuval Peres
Mixing time power laws at criticality

Jeong Han Kim, Ravi Montenegro and Prasad Tetali
A near optimal bound for Pollard's Rho to solve discrete log

Stefan Dziembowski and Krzysztof Pietrzak
Intrusion-resilient secret sharing

Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky and Amit Sahai
Covert multi-party computation

Ran Canetti, Rafael Pass and Abhi Shelat
Cryptography from sunspots: how to use an imperfect reference string

Nancy Lynch
Distributed computing theory: algorithms, impossibility results, models and proofs

Mihai Patrašcu and Mikkel Thorup
Planning for fast connectivity updates

Guy Blelloch and Daniel Golovin
Strongly history-independent hashing with applications

Vladimir Braverman and Rafail Ostrovsky
Smooth histograms for sliding windows

Anna Gál and Parikshit Gopalan
Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence

Per Austrin
Towards sharp inapproximability for any 2-CSP

Subhash Khot and Assaf Naor
Linear equations modulo 2 and the L₁ diameter of convex bodies

Christoph Ambühl, Monaldo Mastrolilli and Ola Svensson
Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling

Dániel Marx
On the optimality of planar and geometric approximation schemes

Parikshit Gopalan, Subhash Khot and Rishi Saket
Hardness of reconstructing multivariate polynomials over finite fields

Andris Ambainis, Andrew Childs, Ben Reichardt, Robert Spalek and Shengyu Zhang
Any AND-OR formula of size N can be evaluated in time N^1/2+o(1) on a quantum computer

Dorit Aharonov, Daniel Gottesman, Sandy Irani and Julia Kempe
The power of quantum systems on a line

Oded Regev and Ben Toner
Simulating quantum correlations with finite communication

Andrew Childs, Leonard Schulman and Umesh Vazirani
Quantum algorithms for hidden nonlinear structures

Uriel Feige
Refuting smoothed 3CNF formulas

Andrej Bogdanov and Muli Safra
Hardness amplification for errorless heuristics

Emanuele Viola and Avi Wigderson
One-way multi-party communication lower bound for pointer jumping with applications

Ran Raz, Amir Shpilka and Amir Yehudayoff
A lower bound for the size of syntactically multilinear arithmetic circuits

Arkadev Chattopadhyay
Discrepancy and the power of bottom fan-in in depth-three circuits

Uriel Feige, Vahab Mirrokni and Jan Vondrák
Maximizing non-monotone submodular functions

Jonathan Kelner and Evdokia Nikolova
On the hardness and smoothed complexity of quasi-concave minimization

Sudipto Guha and Kamesh Munagala
Approximation algorithms for partial-information based stochastic control with Markovian rewards

Christos Koufogiannakis and Neal Young
A fast approximation algorithm for large packing and covering linear programs

Nikhil Bansal, Niv Buchbinder and Seffi Naor
A primal-dual randomized algorithm for weighted paging

Noga Alon and Michael Capalbo
Finding disjoint paths in expanders deterministically and online

Esther Ezra and Micha Sharir
Almost tight bound for the union of fat tetrahedra in three dimensions

Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer and Dmitriy Morozov
Inferring local homology from sampled stratified spaces

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio and Andrew Wan
Testing for concise representations

Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam Smith
Strong lower bounds for approximating distribution support size and the distinct elements problem

Artur Czumaj and Christian Sohler
Testing expansion in bounded-degree graphs

Arie Matsliah, Eldar Fischer and Asaf Shapira
Approximate hypergraph partitioning and applications

Madhu Sudan and Tali Kaufman
Sparse random linear codes are locally decodable and testable

Naveen Garg and Amit Kumar
Minimizing average flow-time: upper and lower bounds

Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Baruch Schieber and Clifford Stein
Non-preemptive min-sum scheduling with resource augmentation

Moses Charikar, Konstantin Makarychev and Yury Makarychev
On the advantage over random for maximum acyclic subgraph

Spyridon Antonakopoulos, Chandra Chekuri, Bruce Shepherd and Lisa Zhang
Buy-at-bulk network design with protection

Dan Boneh, Craig Gentry and Mike Hamburg
Space-efficient identity based encryption without pairings

Juan Garay, Jonathan Katz, Chiu-Yuen Koo and Rafail Ostrovsky
Round complexity of authenticated broadcast with a dishonest majority

Iftach Haitner, Jonathan Hoch, Omer Reingold and Gil Segev
Finding collisions in interactive protocols: a tight lower bound on the round complexity of statistically-hiding commitments

Boaz Barak and Mohammad Mahmoody-Ghidary
Lower bounds on signatures from symmetric primitives

Eden Chlamtac
Approximation algorithms using hierarchies of semidefinite programming relaxations

Konstantinos Georgiou, Avner Magen, Toniann Pitassi and Iannis Tourlakis
Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovasz-Schrijver hierarchy

Moses Charikar, Konstantin Makarychev and Yury Makarychev
Tradeoffs between local and global distortions of metric spaces

Alexandr Andoni and Robert Krauthgamer
The computational hardness of estimating edit distance