Oded Goldreich
In a world of P = BPP
http://www.eccc.uni-trier.de/report/2010/135/
Or Meir
IP = PSPACE using error-correcting codes
http://www.eccc.uni-trier.de/report/2010/137/
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian
Sohler
Finding Cycles and Trees in Sublinear Time
http://arxiv.org/abs/1007.4230
Bansal
Constructive Algorithms for Discrepancy Minimization
http://arxiv.org/abs/1002.2259
Trevisan
Max Cut and the Smallest Eigenvalue
http://arxiv.org/abs/0806.1978
Arora, Barak, Steurer
Subexponential Algorithms for Unique Games and Related Problems
http://www.cs.princeton.edu/~dsteurer/subexpug.pdf
Sisper, Spielman
Expander Codes
http://www-math.mit.edu/~spielman/PAPERS/expandersIT.pdf
Björklund
Determinant Sums for Undirected Hamiltonicity
http://arxiv.org/abs/1008.0541
Moser, Tardos
A constructive proof of the general Lovasz Local Lemma
http://arxiv.org/abs/0903.0544
Khandekar, Rao, Vazirani
Graph Partitioning using Single Commodity Flows
http://portal.acm.org/ft_gateway.cfm?id=1538903&type=pdf&coll=ACM&dl=ACM&CFID=43242870&CFTOKEN=54600076
(introduce a game to construct expanders, which is crucial in the new edge
disjoint path paper)
Sly
Computational Transition at the Uniqueness Threshold
http://arxiv.org/abs/1005.5584