| 2015 | Sum of Squares Lower Bounds from Pairwise Independence. | Boaz Barak, Siu On Chan, Pravesh K. Kothari |
| 2015 | Minimizing Flow-Time on Unrelated Machines. | Nikhil Bansal, Janardhan Kulkarni |
| 2015 | On the Lovsz Theta function for Independent Sets in Sparse Graphs. | Nikhil Bansal, Anupam Gupta, Guru Guruganesh |
| 2015 | Sparse Quantum Codes from Quantum Circuits. | Dave Bacon, Steven T. Flammia, Aram W. Harrow, Jonathan Shi |
| 2015 | Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). | Arturs Backurs, Piotr Indyk |
| 2015 | Optimal Data-Dependent Hashing for Approximate Near Neighbors. | Alexandr Andoni, Ilya P. Razenshteyn |
| 2015 | Sketching and Embedding are Equivalent for Norms. | Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn |
| 2015 | Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. | Andris Ambainis, Yuval Filmus, Franois Le Gall |
| 2015 | High Parallel Complexity Graphs and Memory-Hard Functions. | Jol Alwen, Vladimir Serbinenko |
| 2015 | Adjacency Labeling Schemes and Induced-Universal Graphs. | Stephen Alstrup, Haim Kaplan, Mikkel Thorup, Uri Zwick |
| 2015 | Solving the Shortest Vector Problem in 2 | Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz |
| 2015 | Non-malleable Reductions and Applications. | Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, Maciej Obremski |
| 2015 | Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity. | Ittai Abraham, Danny Dolev |
| 2015 | A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds. | Amirali Abdullah, Suresh Venkatasubramanian |
| 2015 | Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. | Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu |
| 2015 | Reed-Muller Codes for Random Erasures and Errors. | Emmanuel Abbe, Amir Shpilka, Avi Wigderson |
| 2015 | Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. | Scott Aaronson, Andris Ambainis |
| 2015 | The List Decoding Radius of Reed-Muller Codes over Small Fields. | Abhishek Bhowmick, Shachar Lovett |
| 2015 | Approximating the Nash Social Welfare with Indivisible Items. | Richard Cole, Vasilis Gkatzelis |
| 2014 | A characterization of locally testable affine-invariant properties via decomposition theorems. | Yuichi Yoshida |
| 2014 | Faster all-pairs shortest paths via circuit complexity. | Ryan Williams |
| 2014 | New algorithms and lower bounds for circuits with linear threshold gates. | Ryan Williams |
| 2014 | A strongly polynomial algorithm for generalized flow maximization. | Lszl A. Vgh |
| 2014 | From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics. | Shay Solomon |
| 2014 | Entropy, optimization and counting. | Mohit Singh, Nisheeth K. Vishnoi |