| 2015 | A Multiprover Interactive Proof System for the Local Hamiltonian Problem. Joseph F. Fitzsimons, Thomas Vidick |
| 2015 | A New Approach to the Sensitivity Conjecture. Justin Gilmer, Michal Koucký, Michael E. Saks |
| 2015 | A Physically Universal Cellular Automaton. Luke Schaeffer |
| 2015 | Accuracy for Sale: Aggregating Data with a Variance Constraint. Rachel Cummings, Katrina Ligett, Aaron Roth, Zhiwei Steven Wu, Juba Ziani |
| 2015 | Arithmetic Cryptography: Extended Abstract. Benny Applebaum, Jonathan Avron, Christina Brzuska |
| 2015 | Better Outcomes from More Rationality. Jing Chen, Silvio Micali, Rafael Pass |
| 2015 | Communication with Imperfectly Shared Randomness. Clément Louis Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan |
| 2015 | Complex Contagions in Kleinberg's Small World Model. Roozbeh Ebrahimi, Jie Gao, Golnaz Ghasemiesfeh, Grant Schoenebeck |
| 2015 | Deterministic Extractors for Additive Sources: Extended Abstract. Abhishek Bhowmick, Ariel Gabizon, Thái Hoàng Lê, David Zuckerman |
| 2015 | Deterministic Rateless Codes for BSC. Benny Applebaum, Liron David, Guy Even |
| 2015 | Direct Sum Testing. Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar |
| 2015 | Dynamic Models of Reputation and Competition in Job-Market Matching. Jon M. Kleinberg, Sigal Oren |
| 2015 | Fractal Structures in Adversarial Prediction. Rina Panigrahy, Preyas Popat |
| 2015 | Homophily and the Glass Ceiling Effect in Social Networks. Chen Avin, Barbara Keller, Zvi Lotker, Claire Mathieu, David Peleg, Yvonne-Anne Pignolet |
| 2015 | Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH. Mohammad Bavarian, Peter W. Shor |
| 2015 | Interactive Coding for Multiparty Protocols. Abhishek Jain, Yael Tauman Kalai, Allison Bishop Lewko |
| 2015 | It'll Probably Work Out: Improved List-Decoding Through Random Operations. Atri Rudra, Mary Wootters |
| 2015 | Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback. Klim Efremenko, Ran Gelles, Bernhard Haeupler |
| 2015 | Mechanism Design with Strategic Mediators. Moshe Babaioff, Moran Feldman, Moshe Tennenholtz |
| 2015 | Monotone Properties of k-Uniform Hypergraphs are Weakly Evasive. Timothy Black |
| 2015 | Natural Selection as an Inhibitor of Genetic Diversity: Multiplicative Weights Updates Algorithm and a Conjecture of Haploid Genetics [Working Paper Abstract]. Ruta Mehta, Ioannis Panageas, Georgios Piliouras |
| 2015 | Non-Interactive Proofs of Proximity. Tom Gur, Ron D. Rothblum |
| 2015 | On Learning Mixture Models for Permutations. Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi |
| 2015 | On Multiplicative Weight Updates for Concave and Submodular Function Maximization. Chandra Chekuri, T. S. Jayram, Jan Vondrák |
| 2015 | On Sample-Based Testers. Oded Goldreich, Dana Ron |
| 2015 | On the Communication Complexity of Secure Function Evaluation with Long Output. Pavel Hubácek, Daniel Wichs |
| 2015 | Privacy-Preserving Public Information for Sequential Games. Avrim Blum, Jamie Morgenstern, Ankit Sharma, Adam D. Smith |
| 2015 | Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015 Tim Roughgarden |
| 2015 | Relax, No Need to Round: Integrality of Clustering Formulations. Pranjal Awasthi, Afonso S. Bandeira, Moses Charikar, Ravishankar Krishnaswamy, Soledad Villar, Rachel A. Ward |
| 2015 | Restricted Distribution Automatizability in PAC-Semantics. Brendan Juba |
| 2015 | Robust Hierarchical k-Center Clustering. Silvio Lattanzi, Stefano Leonardi, Vahab S. Mirrokni, Ilya P. Razenshteyn |
| 2015 | Separation between Estimation and Approximation. Uriel Feige, Shlomo Jozeph |
| 2015 | Simulating Noisy Channel Interaction. Mark Braverman, Jieming Mao |
| 2015 | Sketching Cuts in Graphs and Hypergraphs. Dmitry Kogan, Robert Krauthgamer |
| 2015 | Standard Simplices and Pluralities are Not the Most Noise Stable. Steven Heilman, Elchanan Mossel, Joe Neeman |
| 2015 | Sunflowers and Testing Triangle-Freeness of Functions. Ishay Haviv, Ning Xie |
| 2015 | The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data. Brynmor Chapman, Ryan Williams |
| 2015 | The Computational Benefit of Correlated Instances. Irit Dinur, Shafi Goldwasser, Huijia Lin |
| 2015 | The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults. Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, Vassilis Zikas |
| 2015 | Uniform Sampling for Matrix Approximation. Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, Aaron Sidford |
| 2015 | Verifiably Truthful Mechanisms. Simina Brânzei, Ariel D. Procaccia |
| 2015 | Very Sparse Additive Spanners and Emulators. Gregory Bodwin, Virginia Vassilevska Williams |
| 2015 | Voting with Coarse Beliefs. Samantha Leung, Edward Lui, Rafael Pass |
| 2015 | Why are Images Smooth? Uriel Feige |
| 2015 | Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Mika Göös, Toniann Pitassi, Thomas Watson |