| 2015 | Local Correlation Breakers and Applications to Three-Source Extractors and Mergers. | Gil Cohen |
| 2015 | New Unconditional Hardness Results for Dynamic and Online Problems. | Raphal Clifford, Allan Grnlund, Kasper Green Larsen |
| 2015 | Input Sparsity and Hardness for Robust Subspace Approximation. | Kenneth L. Clarkson, David P. Woodruff |
| 2015 | Approximate Modularity. | Flavio Chierichetti, Abhimanyu Das, Anirban Dasgupta, Ravi Kumar |
| 2015 | Mixture Selection, Mechanism Design, and Signaling. | Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng |
| 2015 | On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms. | Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis |
| 2015 | Towards an Optimal Method for Dynamic Planar Point Location. | Timothy M. Chan, Yakov Nekrich |
| 2015 | Hardness of Approximation in PSPACE and Separation Results for Pebble Games. | Siu Man Chan, Massimo Lauria, Jakob Nordstrm, Marc Vinyals |
| 2015 | Pattern-Avoiding Access in Binary Search Trees. | Parinya Chalermsook, Mayank Goswami, Lszl Kozma, Kurt Mehlhorn, Thatchaphol Saranurak |
| 2015 | A Holant Dichotomy: Is the FKT Algorithm Universal? | Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams |
| 2015 | Differentially Private Release and Learning of Threshold Functions. | Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan |
| 2015 | Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. | Karl Bringmann, Marvin Knnemann |
| 2015 | Tight Hardness of the Non-commutative Grothendieck Problem. | Jop Brit, Oded Regev, Rishi Saket |
| 2015 | Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness. | Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette |
| 2015 | Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs. | Charles Bordenave, Marc Lelarge, Laurent Massouli |
| 2015 | Indistinguishability Obfuscation from Functional Encryption. | Nir Bitansky, Vinod Vaikuntanathan |
| 2015 | On the Cryptographic Hardness of Finding a Nash Equilibrium. | Nir Bitansky, Omer Paneth, Alon Rosen |
| 2015 | Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. | Dominic W. Berry, Andrew M. Childs, Robin Kothari |
| 2015 | No Small Linear Program Approximates Vertex Cover within a Factor 2 - e. | Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, Ola Svensson |
| 2015 | Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks. | John Augustine, Gopal Pandurangan, Peter Robinson, Scott T. Roche, Eli Upfal |
| 2015 | Limits on the Power of Indistinguishability Obfuscation and Functional Encryption. | Gilad Asharov, Gil Segev |
| 2015 | Heavy-Tailed Independent Component Analysis. | Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher |
| 2015 | Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. | Nima Anari, Shayan Oveis Gharan |
| 2015 | Optimal Induced Universal Graphs and Adjacency Labeling for Trees. | Stephen Alstrup, Sren Dahlgaard, Mathias Bk Tejs Knudsen |
| 2015 | Welfare Maximization with Limited Interaction. | Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein |