| 2015 | Planar Reachability in Linear Space and Constant Time. | Jacob Holm, Eva Rotenberg, Mikkel Thorup |
| 2015 | An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles. | Nicholas J. A. Harvey, Jan Vondrk |
| 2015 | Robust Testing of Lifted Codes with Applications to Low-Degree Testing. | Alan Guo, Elad Haramaty, Madhu Sudan |
| 2015 | Isomorphism Testing for Graphs of Bounded Rank Width. | Martin Grohe, Pascal Schweitzer |
| 2015 | A Light Metric Spanner. | Lee-Ad Gottlieb |
| 2015 | Pseudorandomness via the Discrete Fourier Transform. | Parikshit Gopalan, Daniel M. Kane, Raghu Meka |
| 2015 | Deterministic Communication vs. Partition Number. | Mika Gs, Toniann Pitassi, Thomas Watson |
| 2015 | Lower Bounds for Clique vs. Independent Set. | Mika Gs |
| 2015 | Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption. | Craig Gentry, Allison Bishop Lewko, Amit Sahai, Brent Waters |
| 2015 | Black-Box Garbled RAM. | Sanjam Garg, Steve Lu, Rafail Ostrovsky |
| 2015 | Uniform Generation of Random Regular Graphs. | Pu Gao, Nicholas C. Wormald |
| 2015 | FO Model Checking on Posets of Bounded Width. | Jakub Gajarsk, Petr Hlinen, Daniel Lokshtanov, Jan Obdrzlek, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh |
| 2015 | Deterministic Divisibility Testing via Shifted Partial Derivatives. | Michael A. Forbes |
| 2015 | Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability. | Eldar Fischer, Oded Lachish, Yadu Vasudev |
| 2015 | The Submodular Secretary Problem Goes Linear. | Moran Feldman, Rico Zenklusen |
| 2015 | Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions. | Vitaly Feldman, Jan Vondrk |
| 2015 | Online Buy-at-Bulk Network Design. | Alina Ene, Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Debmalya Panigrahi |
| 2015 | Talagrand's Convolution Conjecture on Gaussian Space. | Ronen Eldan, James R. Lee |
| 2015 | Approximately Counting Triangles in Sublinear Time. | Talya Eden, Amit Levi, Dana Ron, C. Seshadhri |
| 2015 | Robust Traceability from Trace Amounts. | Cynthia Dwork, Adam D. Smith, Thomas Steinke, Jonathan R. Ullman, Salil P. Vadhan |
| 2015 | Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. | Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin |
| 2015 | Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums. | Anindya De |
| 2015 | On the Structure, Covering, and Learning of Poisson Multinomial Distributions. | Constantinos Daskalakis, Gautam Kamath, Christos Tzamos |
| 2015 | Hashing for Statistics over K-Partitions. | Sren Dahlgaard, Mathias Bk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup |
| 2015 | Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k. | Radu Curticapean, Mingji Xia |