 Sketching and Embedding are Equivalent for Norms (STOC 2015)
Alexandr Andoni, Robert Krauthgamer, Ilya Razenshteyn [arXiv]
 Lower bounds on the size of semidefinite programming relaxations (STOC 2015)
James R. Lee, Prasad Raghavendra, David Steurer
[arXiv]
 Combinatorial Algorithm for Restricted MaxMin Fair Allocation (SODA 2015)
Chidambaram Annamalai, Christos Kalaitzis, Ola Svensson
[arXiv]
 Approximating Hereditary Discrepancy via Small Width Ellipsoids (SODA 2015)
Aleksandar Nikolov and Kunal Talwar
[arXiv]
 Finding Hidden Cliques in Linear Time with High Probability (Combinatorics, Probability & Computing, 23 (1), 2014) Yael Dekel, Ori GurelGurevich, Yuval Peres [arXiv]
 Random Walks that Find Perfect Objects and the Lovasz Local Lemma (FOCS 2014)
Dimitris Achlioptas, Fotis Iliopoulos
[arXiv]
 Parallel Repetition from Fortification (FOCS 2014)
Dana Moshkovitz
[Link]
 On the AC0 Complexity of Subgraph Isomorphism (FOCS 2014)
Yuan Li, Alexander Razborov, Benjamin Rossman
[Link]
 Shrinkage of De Morgan Formulae from Quantum Query Complexity (FOCS 2014)
Avishay Tal
[ECCC]
 LPBased Algorithms for Capacitated Facility Location (FOCS 2014)
HyungChan An, Mohit Singh, Ola Svensson
[arXiv]
 List and Unique Decoding for Interactive Communication in the Presence of Adversarial Noise (FOCS 2014)
Mark Braverman, Klim Efermenko
[ECCC]
 Exponential Separation of Information and Communication (FOCS 2014)
Anat Ganor, Gillat Kol, Ran Raz
[ECCC]
 Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs (APPROXRANDOM 2014)
Thomas Steinke, Salil Vadhan and Andrew Wan
[arXiv]
 Gap Amplification for SmallSet Expansion via Random Walks (APPROXRANDOM 2014)
Prasad Raghavendra and Tselil Schramm
[arXiv]
 Discrepancy Without Partial Colorings (APPROXRANDOM 2014)
Nicholas Harvey, Roy Schwartz and Mohit Singh
[Link]
 Two Sides of the Coin Problem (APPROXRANDOM 2014)
Gil Cohen, Anat Ganor and Ran Raz
[ECCC]
 Deterministic Coupon Collection and Better Strong Dispersers (APPROXRANDOM 2014)
Omer Reingold, Raghu Meka and Yuan Zhou
[Link]
 On the Power of Symmetric LP and SDP relaxations (CCC 2014)
James R. Lee, Prasad Raghavendra, David Steurer, Ning Tan
[Link]
 On the Boundedness of Bernoulli processes (Annals Of Mathematics, Vol. 180, Issue 3, 2014)
Witold Bednorz and Rafal Latala
[arXiv]
 Rounding SumofSquares Relaxations (STOC 2014)
Boaz Barak, Jonathan Kelner, David Steurer
[arXiv]
 Entropy, Optimization and Counting (STOC 2014)
Mohit Singh and Nisheeth Vishnoi
[arXiv]
 Efficient Deterministic Approximate Counting for Low Degree Polynomial Threshold Functions (STOC 2014)
Anindya De and Rocco Servedio
[arXiv]
 Interlacing Families II: Mixed Characteristic Polynomials and the KadisonSinger Problem (to appear, Annals of Mathematics)
Adam Marcus, Daniel A. Spielman, Nikhil Srivastava
[arXiv]
 Constant Factor Approximation for Balanced Cut in the PIE Model (STOC 2014)
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
[arXiv]
 A Characterization of Locally Testable Affineinvariant Properties via Decomposition Theorems (STOC 2014)
Yuichi Yoshida
[arXiv]
 Interlacing Families I: Bipartite Ramanujan Graphs of All Degree (FOCS 2013)
Adam Marcus, Daniel A. Spielman, Nikhil Srivastava
[arXiv]
 Towards a better approximation for sparsest cut? (FOCS 2013)
Sanjeev Arora, Rong Ge, Ali Kemal Sinop
[arXiv]
 Improved ARV Rounding in SmallSet Expanders and Graphs of Bounded Threshold Rank (2013)
Shayan Oveis Gharan, Luca Trevisan
[arXiv]
 Analysis of Spectral Partitioning through Higher Order Spectral Gap (STOC 2013)
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
[arXiv]
 Approximation Limits of Linear Programs (Beyond Hierarchies) (FOCS 2012)
Gabor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer
[arXiv]

