Suggested Papers

  1. Computing Maximum Flow with Augmenting Electrical Flows by Aleksander Madry (FOCS'16)
  2. Algorithm for Komlos conjecture: matching Banaszczyk's bound by Nikhil Bansal, Daniel Dadush, and Shashwat Garg (FOCS'16)
  3. A New Framework for Distributed Submodular Maximization by Rafael da Ponte Barbosa, Alina Ene, Huy L Nguyen, and Justin Ward (FOCS'16)
  4. Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple by Rasmus Kyng and Sushant Sachdeva (FOCS'16)
  5. Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics by Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu (FOCS'16)
    (or: Local Search Yields a PTAS for k-Means in Doubling Metrics by Zachary Friggstad, Mohsen Rezapour, and Mohammad Salavatipour (FOCS'16))
  6. High rate locally-correctable and locally-testable codes with sub-polynomial query complexity bySwastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf (FOCS'16)
    (and the paper it merged with: High rate locally-correctable and locally-testable codes with sub-polynomial query complexity by Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf)
  7. Compressing Interactive Communication under Product Distributions by Alexander A. Sherstov (STOC'16)
  8. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths by Henzinger, Krinninger, and Nanongkai (STOC'16)
  9. New deterministic approximation algorithms for fully dynamic matching by Bhattacharya, Henzinger, and Nanongkai (STOC'16)
  10. The 4/3 Additive Spanner Exponent is Tight by Amir Abboud and Greg Bodwin (STOC'16)
  11. Reed-Muller Codes Achieve Capacity on Erasure Channels by Shrinivas Kudekar, Santhosh Kumar, Marco Mondelli, Henry D. Pfister, Eren Sasoglu, Ruediger Urbanke (STOC'16 Best Paper)
  12. Explicit Two-Source Extractors and Resilient Functions by Eshan Chattopadhyay, David Zuckerman (STOC'16 Best Paper)
  13. An Improved Distributed Algorithm for Maximal Independent Set by Mohsen Ghaffari (Best Paper SODA16)
  14. Expanders via Local Edge Flips by Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni, and Lorenzo Orecchia (SODA'16)
  15. Higher Lower Bounds from the 3SUM Conjecture by Tsvi Kopelowitz, Seth Pettie, and Ely Porat (SODA'16)
  16. Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities by Michael Cohen (SODA'16)
  17. Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model by Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev (SODA'16)
  18. A family of optimal locally recoverable codes by Itzhak Tamo, Alexander Barg (IT Society Best Paper Award 2015)
  19. Approximating ATSP by Relaxing Connectivity by Ola Svensson (FOCS'15)
    (there is also a follow-up by Svensson, Vegh and Tarnawsky)
  20. If the Current Clique Algorithms are Optimal, so is Valiant's Parser by Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams (FOCS'15)
  21. 2-Server PIR with Sub-Polynomial Communication by Sivakanth Gopi, and Zeev Dvir (STOC'15 Best Paper and JACM'16)
  22. Exponential Separation of Information and Communication for Boolean Functions by Anat Ganor, Gillat Kol, and Ran Raz (STOC'15 Best Paper and JACM'16)
  23. Excluded Grid Theorem: Improved and Simplified by Julia Chuzhoy (STOC'15)
  24. Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time by Ken-ichi Kawarabayashi, and Mikkel Thorup (STOC'15)
  25. From Independence to Expansion and Back Again by Tobias Christiani, Rasmus Pagh, and Mikkel Thorup (STOC'15)
  26. A Stable Marriage Requires Communication by Yannai Gonczarowski, Noam Nisan, Rafail Ostrovsky, and Will Rosenbaum (SODA'15)
  27. Online Network Design Algorithms via Hierarchical Decompositions by Seeun Umboh (SODA'15)
  28. The Cell Probe Complexity of Dynamic Range Counting by Kasper Green Larsen (Best Paper STOC'12)
  29. Constructive discrepancy minimization for convex sets by Thomas Rothvoss (FOCS'14)
    (related and also great: Constructive Discrepancy Minimization by Walking on The Edges)
  30. Improved Concentration Bounds for Count-Sketch by Gregory T. Minton and Eric Price (Best Student Paper SODA'14)