| 2015 | Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension. | Amit Daniely, Michael Schapira, Gal Shahaf |
| 2015 | Testing Cluster Structure of Graphs. | Artur Czumaj, Pan Peng, Christian Sohler |
| 2015 | Random Permutations using Switching Networks. | Artur Czumaj |
| 2015 | Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm. | Benjamin Cousins, Santosh S. Vempala |
| 2015 | L | Michael B. Cohen, Richard Peng |
| 2015 | Dimensionality Reduction for k-Means Clustering and Low Rank Approximation. | Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu |
| 2015 | Excluded Grid Theorem: Improved and Simplified. | Julia Chuzhoy |
| 2015 | From Independence to Expansion and Back Again. | Tobias Christiani, Rasmus Pagh, Mikkel Thorup |
| 2015 | A Characterization of the Capacity of Online (causal) Binary Channels. | Zitan Chen, Sidharth Jaggi, Michael Langberg |
| 2015 | Boolean Function Monotonicity Testing Requires (Almost) n | Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan |
| 2015 | On the Complexity of Nash Equilibria in Anonymous Games. | Xi Chen, David Durfee, Anthi Orfanou |
| 2015 | Approximate Distance Oracles with Improved Bounds. | Shiri Chechik |
| 2015 | Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs. | Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev |
| 2015 | Clustered Integer 3SUM via Additive Combinatorics. | Timothy M. Chan, Moshe Lewenstein |
| 2015 | Succinct Garbling and Indistinguishability Obfuscation for RAM Programs. | Ran Canetti, Justin Holmgren, Abhishek Jain, Vinod Vaikuntanathan |
| 2015 | Efficiently Learning Ising Models on Arbitrary Graphs. | Guy Bresler |
| 2015 | An Interactive Information Odometer and Applications. | Mark Braverman, Omri Weinstein |
| 2015 | Small Value Parallel Repetition for General Games. | Mark Braverman, Ankit Garg |
| 2015 | Inapproximability of Combinatorial Problems via Small LPs and SDPs. | Gbor Braun, Sebastian Pokutta, Daniel Zink |
| 2015 | Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space. | Jean Bourgain, Sjoerd Dirksen, Jelani Nelson |
| 2015 | Succinct Randomized Encodings and their Applications. | Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, Sidharth Telang |
| 2015 | Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams. | Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Charalampos E. Tsourakakis |
| 2015 | Local, Private, Efficient Protocols for Succinct Histograms. | Raef Bassily, Adam D. Smith |
| 2015 | Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem. | Siddharth Barman |
| 2015 | Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. | Boaz Barak, Jonathan A. Kelner, David Steurer |