| 2015 | Secretary Problems with Non-Uniform Arrival Order. | Thomas Kesselheim, Robert D. Kleinberg, Rad Niazadeh |
| 2015 | Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time. | Ken-ichi Kawarabayashi, Mikkel Thorup |
| 2015 | Beyond the Euler Characteristic: Approximating the Genus of General Graphs. | Ken-ichi Kawarabayashi, Anastasios Sidiropoulos |
| 2015 | The Directed Grid Theorem. | Ken-ichi Kawarabayashi, Stephan Kreutzer |
| 2015 | Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. | Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak |
| 2015 | Tight Bounds for Learning a Mixture of Two Gaussians. | Moritz Hardt, Eric Price |
| 2015 | An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm. | Thomas Dueholm Hansen, Uri Zwick |
| 2015 | How Well Can Graphs Represent Wireless Interference? | Magns M. Halldrsson, Tigran Tonoyan |
| 2015 | Greedy Algorithms for Steiner Forest. | Anupam Gupta, Amit Kumar |
| 2015 | Computing with Tangles. | Martin Grohe, Pascal Schweitzer |
| 2015 | The communication complexity of interleaved group products. | Timothy Gowers, Emanuele Viola |
| 2015 | Leveled Fully Homomorphic Signatures from Standard Lattices. | Sergey Gorbunov, Vinod Vaikuntanathan, Daniel Wichs |
| 2015 | Rectangles Are Nonnegative Juntas. | Mika Gs, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman |
| 2015 | Test-and-Set in Optimal Space. | George Giakkoupis, Maryam Helmi, Lisa Higham, Philipp Woelfel |
| 2015 | Learning Mixtures of Gaussians in High Dimensions. | Rong Ge, Qingqing Huang, Sham M. Kakade |
| 2015 | Garbled RAM From One-Way Functions. | Sanjam Garg, Steve Lu, Rafail Ostrovsky, Alessandra Scafuro |
| 2015 | Exponential Separation of Information and Communication for Boolean Functions. | Anat Ganor, Gillat Kol, Ran Raz |
| 2015 | A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. | Kyle Fox, Philip N. Klein, Shay Mozes |
| 2015 | On the Complexity of Random Satisfiability Problems with Planted Solutions. | Vitaly Feldman, Will Perkins, Santosh S. Vempala |
| 2015 | The Complexity of the Simplex Method. | John Fearnley, Rahul Savani |
| 2015 | Prioritized Metric Structures and Embedding. | Michael Elkin, Arnold Filtser, Ofer Neiman |
| 2015 | Preserving Statistical Validity in Adaptive Data Analysis. | Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth |
| 2015 | 2-Server PIR with Sub-Polynomial Communication. | Zeev Dvir, Sivakanth Gopi |
| 2015 | Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition. | Irit Dinur, Prahladh Harsha, Guy Kindler |
| 2015 | Proof of the Satisfiability Conjecture for Large k. | Jian Ding, Allan Sly, Nike Sun |