| 2015 | 2-Server PIR with Sub-Polynomial Communication. Zeev Dvir, Sivakanth Gopi |
| 2015 | A Characterization of the Capacity of Online (causal) Binary Channels. Zitan Chen, Sidharth Jaggi, Michael Langberg |
| 2015 | A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds. Amirali Abdullah, Suresh Venkatasubramanian |
| 2015 | A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. Kyle Fox, Philip N. Klein, Shay Mozes |
| 2015 | Adjacency Labeling Schemes and Induced-Universal Graphs. Stephen Alstrup, Haim Kaplan, Mikkel Thorup, Uri Zwick |
| 2015 | Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract. Pravesh K. Kothari, Raghu Meka |
| 2015 | An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm. Thomas Dueholm Hansen, Uri Zwick |
| 2015 | An Interactive Information Odometer and Applications. Mark Braverman, Omri Weinstein |
| 2015 | Analysis of a Classical Matrix Preconditioning Algorithm. Leonard J. Schulman, Alistair Sinclair |
| 2015 | Approximate Distance Oracles with Improved Bounds. Shiri Chechik |
| 2015 | Approximate k-flat Nearest Neighbor Search. Wolfgang Mulzer, Huy L. Nguyên, Paul Seiferth, Yannik Stein |
| 2015 | Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem. Siddharth Barman |
| 2015 | Approximating the Nash Social Welfare with Indivisible Items. Richard Cole, Vasilis Gkatzelis |
| 2015 | Beyond the Euler Characteristic: Approximating the Genus of General Graphs. Ken-ichi Kawarabayashi, Anastasios Sidiropoulos |
| 2015 | Boolean Function Monotonicity Testing Requires (Almost) n Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan |
| 2015 | Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm. Benjamin Cousins, Santosh S. Vempala |
| 2015 | Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity. Ittai Abraham, Danny Dolev |
| 2015 | Clustered Integer 3SUM via Additive Combinatorics. Timothy M. Chan, Moshe Lewenstein |
| 2015 | Computing with Tangles. Martin Grohe, Pascal Schweitzer |
| 2015 | Consistency Thresholds for the Planted Bisection Model. Elchanan Mossel, Joe Neeman, Allan Sly |
| 2015 | Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time. Ken-ichi Kawarabayashi, Mikkel Thorup |
| 2015 | Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. Boaz Barak, Jonathan A. Kelner, David Steurer |
| 2015 | Dimensionality Reduction for k-Means Clustering and Low Rank Approximation. Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, Madalina Persu |
| 2015 | Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). Arturs Backurs, Piotr Indyk |
| 2015 | Efficiently Learning Ising Models on Arbitrary Graphs. Guy Bresler |
| 2015 | Excluded Grid Theorem: Improved and Simplified. Julia Chuzhoy |
| 2015 | Exponential Separation of Information and Communication for Boolean Functions. Anat Ganor, Gillat Kol, Ran Raz |
| 2015 | FPTAS for #BIS with Degree Bounds on One Side. Jingcheng Liu, Pinyan Lu |
| 2015 | Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method. Andris Ambainis, Yuval Filmus, François Le Gall |
| 2015 | Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract. Xiaorui Sun, John Wilmes |
| 2015 | Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Scott Aaronson, Andris Ambainis |
| 2015 | From Independence to Expansion and Back Again. Tobias Christiani, Rasmus Pagh, Mikkel Thorup |
| 2015 | Garbled RAM From One-Way Functions. Sanjam Garg, Steve Lu, Rafail Ostrovsky, Alessandra Scafuro |
| 2015 | Greedy Algorithms for Steiner Forest. Anupam Gupta, Amit Kumar |
| 2015 | Hardness of Graph Pricing Through Generalized Max-Dicut. Euiwoong Lee |
| 2015 | High Parallel Complexity Graphs and Memory-Hard Functions. Joël Alwen, Vladimir Serbinenko |
| 2015 | How Well Can Graphs Represent Wireless Interference? Magnús M. Halldórsson, Tigran Tonoyan |
| 2015 | Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms. Anand Louis |
| 2015 | Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions. Shachar Lovett, Jiapeng Zhang |
| 2015 | Inapproximability of Combinatorial Problems via Small LPs and SDPs. Gábor Braun, Sebastian Pokutta, Daniel Zink |
| 2015 | Inapproximability of Nash Equilibrium. Aviad Rubinstein |
| 2015 | Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension. Amit Daniely, Michael Schapira, Gal Shahaf |
| 2015 | Indistinguishability Obfuscation for Turing Machines with Unbounded Memory. Venkata Koppula, Allison Bishop Lewko, Brent Waters |
| 2015 | L Michael B. Cohen, Richard Peng |
| 2015 | Learning Arbitrary Statistical Mixtures of Discrete Distributions. Jian Li, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy |
| 2015 | Learning Mixtures of Gaussians in High Dimensions. Rong Ge, Qingqing Huang, Sham M. Kakade |
| 2015 | Leveled Fully Homomorphic Signatures from Standard Lattices. Sergey Gorbunov, Vinod Vaikuntanathan, Daniel Wichs |
| 2015 | Local, Private, Efficient Protocols for Succinct Histograms. Raef Bassily, Adam D. Smith |
| 2015 | Lower Bounds on the Size of Semidefinite Programming Relaxations. James R. Lee, Prasad Raghavendra, David Steurer |
| 2015 | Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. Amir Abboud, Virginia Vassilevska Williams, Huacheng Yu |
| 2015 | Minimizing Flow-Time on Unrelated Machines. Nikhil Bansal, Janardhan Kulkarni |
| 2015 | Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs. Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev |
| 2015 | Nearly-Linear Time Positive LP Solver with Faster Convergence Rate. Zeyuan Allen Zhu, Lorenzo Orecchia |
| 2015 | Non-malleable Reductions and Applications. Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, Maciej Obremski |
| 2015 | On the Complexity of Nash Equilibria in Anonymous Games. Xi Chen, David Durfee, Anthi Orfanou |
| 2015 | On the Complexity of Random Satisfiability Problems with Planted Solutions. Vitaly Feldman, Will Perkins, Santosh S. Vempala |
| 2015 | On the Lovász Theta function for Independent Sets in Sparse Graphs. Nikhil Bansal, Anupam Gupta, Guru Guruganesh |
| 2015 | Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order. Nitish Korula, Vahab S. Mirrokni, Morteza Zadimoghaddam |
| 2015 | Optimal Data-Dependent Hashing for Approximate Near Neighbors. Alexandr Andoni, Ilya P. Razenshteyn |
| 2015 | Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition. Irit Dinur, Prahladh Harsha, Guy Kindler |
| 2015 | Preserving Statistical Validity in Adaptive Data Analysis. Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth |
| 2015 | Prioritized Metric Structures and Embedding. Michael Elkin, Arnold Filtser, Ofer Neiman |
| 2015 | Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 Rocco A. Servedio, Ronitt Rubinfeld |
| 2015 | Proof of the Satisfiability Conjecture for Large k. Jian Ding, Allan Sly, Nike Sun |
| 2015 | Quantum Information Complexity. Dave Touchette |
| 2015 | Quantum Spectrum Testing. Ryan O'Donnell, John Wright |
| 2015 | Random Permutations using Switching Networks. Artur Czumaj |
| 2015 | Randomized Composable Core-sets for Distributed Submodular Maximization. Vahab S. Mirrokni, Morteza Zadimoghaddam |
| 2015 | Randomized Rounding for the Largest Simplex Problem. Aleksandar Nikolov |
| 2015 | Rectangles Are Nonnegative Juntas. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman |
| 2015 | Reed-Muller Codes for Random Erasures and Errors. Emmanuel Abbe, Amir Shpilka, Avi Wigderson |
| 2015 | Secretary Problems with Non-Uniform Arrival Order. Thomas Kesselheim, Robert D. Kleinberg, Rad Niazadeh |
| 2015 | Sketching and Embedding are Equivalent for Norms. Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn |
| 2015 | Small Value Parallel Repetition for General Games. Mark Braverman, Ankit Garg |
| 2015 | Solving the Shortest Vector Problem in 2 Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz |
| 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 | Sparse Quantum Codes from Quantum Circuits. Dave Bacon, Steven T. Flammia, Aram W. Harrow, Jonathan Shi |
| 2015 | Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates. Zeyuan Allen Zhu, Zhenyu Liao, Lorenzo Orecchia |
| 2015 | Succinct Garbling and Indistinguishability Obfuscation for RAM Programs. Ran Canetti, Justin Holmgren, Abhishek Jain, Vinod Vaikuntanathan |
| 2015 | Succinct Randomized Encodings and their Applications. Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, Sidharth Telang |
| 2015 | Sum of Squares Lower Bounds from Pairwise Independence. Boaz Barak, Siu On Chan, Pravesh K. Kothari |
| 2015 | Sum-of-squares Lower Bounds for Planted Clique. Raghu Meka, Aaron Potechin, Avi Wigderson |
| 2015 | Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices. Ankur Moitra |
| 2015 | Test-and-Set in Optimal Space. George Giakkoupis, Maryam Helmi, Lisa Higham, Philipp Woelfel |
| 2015 | Testing Cluster Structure of Graphs. Artur Czumaj, Pan Peng, Christian Sohler |
| 2015 | The Complexity of the Simplex Method. John Fearnley, Rahul Savani |
| 2015 | The Directed Grid Theorem. Ken-ichi Kawarabayashi, Stephan Kreutzer |
| 2015 | The List Decoding Radius of Reed-Muller Codes over Small Fields. Abhishek Bhowmick, Shachar Lovett |
| 2015 | The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree. Jakub Lacki, Jakub Ocwieja, Marcin Pilipczuk, Piotr Sankowski, Anna Zych |
| 2015 | The communication complexity of interleaved group products. Timothy Gowers, Emanuele Viola |
| 2015 | Tight Bounds for Learning a Mixture of Two Gaussians. Moritz Hardt, Eric Price |
| 2015 | Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms. Kasper Green Larsen, Jelani Nelson, Huy L. Nguyên |
| 2015 | Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space. Jean Bourgain, Sjoerd Dirksen, Jelani Nelson |
| 2015 | Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak |