Suggested Papers

  • Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning - Ran Raz @FOCS 2016 (arXiv)

  • Linear Hashing is Awesome - Mathias Baek Tejs Knudsen @FOCS 2016 (Link)

  • Towards Strong Reverse Minkowski-type Inequalities for Lattices - Daniel Dadush, Oded Regev @FOCS 2016 (arXiv)

  • Extension Complexity of Independent Set Polytopes - Mika Goos, Rahul Jain, Thomas Watson @FOCS 2016 (arXiv)
  • Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing - Elizabeth Crosson, Aram W. Harrow @FOCS 2016 (arXiv)
  • An Algorithm for Komlos Conjecture Matching Banaszczyk's bound - Nikhil Bansal, Daniel Dadush, Shashwat Garg @FOCS 2016 (arXiv)
  • Constrained Submodular Maximization: Beyond 1/e - Alina Ene, Huy L. Nguyen @FOCS 2016 (arXiv)
  • Random Walks and Evolving Sets: Faster Convergences and Limitations - Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau @SODA 2017 (arXiv)
  • On statistical learning via the lens of compression - Ofir David, Shay Moran, Amir Yehudayoff @NIPS 2016 (arXiv)
  • Local max-cut in smoothed polynomial time - Omer Angel, Sébastien Bubeck, Yuval Peres, Fan Wei (arXiv)
  • A group-theoretic approach to fast matrix multiplication - Henry Cohn, Christopher Umans @FOCS 2003 (arXiv)
  • Group-theoretic algorithms for matrix multiplication - Henry Cohn, Robert Kleinberg, Balazs Szegedy, Christopher Umans @FOCS 2005 (arXiv)
  • On cap sets and the group-theoretic approach to matrix multiplication - Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, Chris Umans (arXiv)