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