Suggested Papers

  • 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 Max-Min 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 Gurel-Gurevich, 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]
  • LP-Based Algorithms for Capacitated Facility Location (FOCS 2014)
    Hyung-Chan 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 (APPROX-RANDOM 2014)
    Thomas Steinke, Salil Vadhan and Andrew Wan
    [arXiv]
  • Gap Amplification for Small-Set Expansion via Random Walks (APPROX-RANDOM 2014)
    Prasad Raghavendra and Tselil Schramm
    [arXiv]
  • Discrepancy Without Partial Colorings (APPROX-RANDOM 2014)
    Nicholas Harvey, Roy Schwartz and Mohit Singh
    [Link]
  • Two Sides of the Coin Problem (APPROX-RANDOM 2014)
    Gil Cohen, Anat Ganor and Ran Raz
    [ECCC]
  • Deterministic Coupon Collection and Better Strong Dispersers (APPROX-RANDOM 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 Sum-of-Squares 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 Kadison-Singer 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 Affine-invariant 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 Small-Set 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