| 2015 | A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization. Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong |
| 2015 | A Holant Dichotomy: Is the FKT Algorithm Universal? Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams |
| 2015 | A Light Metric Spanner. Lee-Ad Gottlieb |
| 2015 | A Robust Sparse Fourier Transform in the Continuous Setting. Eric Price, Zhao Song |
| 2015 | An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles. Nicholas J. A. Harvey, Jan Vondrák |
| 2015 | An Average-Case Depth Hierarchy Theorem for Boolean Circuits. Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan |
| 2015 | An O(1)-Approximation for Minimum Spanning Tree Interdiction. Rico Zenklusen |
| 2015 | Approximate Modularity. Flavio Chierichetti, Abhimanyu Das, Anirban Dasgupta, Ravi Kumar |
| 2015 | Approximately Counting Triangles in Sublinear Time. Talya Eden, Amit Levi, Dana Ron, C. Seshadhri |
| 2015 | Approximating ATSP by Relaxing Connectivity. Ola Svensson |
| 2015 | Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums. Anindya De |
| 2015 | Black-Box Garbled RAM. Sanjam Garg, Steve Lu, Rafail Ostrovsky |
| 2015 | Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment. Tsvi Kopelowitz, Ely Porat |
| 2015 | Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery. Emmanuel Abbe, Colin Sandon |
| 2015 | Competitive Flow Time Algorithms for Polyhedral Scheduling. Sungjin Im, Janardhan Kulkarni, Kamesh Munagala |
| 2015 | Compressing and Teaching for Low VC-Dimension. Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff |
| 2015 | Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time. Yin Tat Lee, He Sun |
| 2015 | Deterministic Communication vs. Partition Number. Mika Göös, Toniann Pitassi, Thomas Watson |
| 2015 | Deterministic Divisibility Testing via Shifted Partial Derivatives. Michael A. Forbes |
| 2015 | Differentially Private Release and Learning of Threshold Functions. Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan |
| 2015 | Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. Nima Anari, Shayan Oveis Gharan |
| 2015 | Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. Yin Tat Lee, Aaron Sidford |
| 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 | Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable. Helmut Seidl, Sebastian Maneth, Gregor Kemper |
| 2015 | FO Model Checking on Posets of Bounded Width. Jakub Gajarský, Petr Hlinený, Daniel Lokshtanov, Jan Obdrzálek, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh |
| 2015 | Guaranteed Matrix Completion via Nonconvex Factorization. Ruoyu Sun, Zhi-Quan Luo |
| 2015 | Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. Dominic W. Berry, Andrew M. Childs, Robin Kothari |
| 2015 | Hardness of Approximation in PSPACE and Separation Results for Pebble Games. Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals |
| 2015 | Hashing for Statistics over K-Partitions. Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup |
| 2015 | Heavy-Tailed Independent Component Analysis. Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher |
| 2015 | How to Refute a Random CSP. Sarah R. Allen, Ryan O'Donnell, David Witmer |
| 2015 | IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015 Venkatesan Guruswami |
| 2015 | If the Current Clique Algorithms are Optimal, So is Valiant's Parser. Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams |
| 2015 | Incidences between Points and Lines in R^4. Micha Sharir, Noam Solomon |
| 2015 | Indistinguishability Obfuscation from Functional Encryption. Nir Bitansky, Vinod Vaikuntanathan |
| 2015 | Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption. Craig Gentry, Allison Bishop Lewko, Amit Sahai, Brent Waters |
| 2015 | Input Sparsity and Hardness for Robust Subspace Approximation. Kenneth L. Clarkson, David P. Woodruff |
| 2015 | Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. Adam W. Marcus, Daniel A. Spielman, Nikhil Srivastava |
| 2015 | Isomorphism Testing for Graphs of Bounded Rank Width. Martin Grohe, Pascal Schweitzer |
| 2015 | Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems. Barna Saha |
| 2015 | Limits on the Power of Indistinguishability Obfuscation and Functional Encryption. Gilad Asharov, Gil Segev |
| 2015 | Local Correlation Breakers and Applications to Three-Source Extractors and Mergers. Gil Cohen |
| 2015 | Lower Bounds for Clique vs. Independent Set. Mika Göös |
| 2015 | Mixture Selection, Mechanism Design, and Signaling. Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng |
| 2015 | Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness. Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette |
| 2015 | New Unconditional Hardness Results for Dynamic and Online Problems. Raphaël Clifford, Allan Grønlund, Kasper Green Larsen |
| 2015 | No Small Linear Program Approximates Vertex Cover within a Factor 2 - e. Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, Ola Svensson |
| 2015 | Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs. Charles Bordenave, Marc Lelarge, Laurent Massoulié |
| 2015 | On Monotonicity Testing and Boolean Isoperimetric Type Theorems. Subhash Khot, Dor Minzer, Muli Safra |
| 2015 | On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms. Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis |
| 2015 | On the Cryptographic Hardness of Finding a Nash Equilibrium. Nir Bitansky, Omer Paneth, Alon Rosen |
| 2015 | On the Structure, Covering, and Learning of Poisson Multinomial Distributions. Constantinos Daskalakis, Gautam Kamath, Christos Tzamos |
| 2015 | Online Buy-at-Bulk Network Design. Alina Ene, Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Debmalya Panigrahi |
| 2015 | Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin |
| 2015 | Optimal Auctions vs. Anonymous Pricing. Saeed Alaei, Jason D. Hartline, Rad Niazadeh, Emmanouil Pountourakis, Yang Yuan |
| 2015 | Optimal Induced Universal Graphs and Adjacency Labeling for Trees. Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen |
| 2015 | Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k. Radu Curticapean, Mingji Xia |
| 2015 | Pattern-Avoiding Access in Binary Search Trees. Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, Thatchaphol Saranurak |
| 2015 | Planar Reachability in Linear Space and Constant Time. Jacob Holm, Eva Rotenberg, Mikkel Thorup |
| 2015 | Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem. F. Bruce Shepherd, Adrian Vetta, Gordon T. Wilfong |
| 2015 | Probabilistic Polynomials and Hamming Nearest Neighbors. Josh Alman, Ryan Williams |
| 2015 | Pseudorandomness via the Discrete Fourier Transform. Parikshit Gopalan, Daniel M. Kane, Raghu Meka |
| 2015 | Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. Karl Bringmann, Marvin Künnemann |
| 2015 | Quantum Expander Codes. Anthony Leverrier, Jean-Pierre Tillich, Gilles Zémor |
| 2015 | Random Matrices: l1 Concentration and Dictionary Learning with Few Samples. Kyle Luh, Van Vu |
| 2015 | Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line. Amir Nayyeri, Benjamin Raichel |
| 2015 | Robust Testing of Lifted Codes with Applications to Low-Degree Testing. Alan Guo, Elad Haramaty, Madhu Sudan |
| 2015 | Robust Traceability from Trace Amounts. Cynthia Dwork, Adam D. Smith, Thomas Steinke, Jonathan R. Ullman, Salil P. Vadhan |
| 2015 | Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8. Mikkel Thorup |
| 2015 | Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. Konstantin Makarychev, Yury Makarychev, Yuan Zhou |
| 2015 | Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again! Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz |
| 2015 | Symbolic Integration and the Complexity of Computing Averages. Leonard J. Schulman, Alistair Sinclair, Piyush Srivastava |
| 2015 | Talagrand's Convolution Conjecture on Gaussian Space. Ronen Eldan, James R. Lee |
| 2015 | The Average Sensitivity of Bounded-Depth Formulas. Benjamin Rossman |
| 2015 | The Complexity of General-Valued CSPs. Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek |
| 2015 | The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication. Erez Kantor, Zvi Lotker, Merav Parter, David Peleg |
| 2015 | The Power of Asymmetry in Constant-Depth Circuits. Alexander A. Sherstov |
| 2015 | The Submodular Secretary Problem Goes Linear. Moran Feldman, Rico Zenklusen |
| 2015 | Three-Source Extractors for Polylogarithmic Min-Entropy. Xin Li |
| 2015 | Tight Bounds for Online Vector Scheduling. Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi |
| 2015 | Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions. Vitaly Feldman, Jan Vondrák |
| 2015 | Tight Hardness Results for LCS and Other Sequence Similarity Measures. Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams |
| 2015 | Tight Hardness of the Non-commutative Grothendieck Problem. Jop Briët, Oded Regev, Rishi Saket |
| 2015 | Towards an Optimal Method for Dynamic Planar Point Location. Timothy M. Chan, Yakov Nekrich |
| 2015 | Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability. Eldar Fischer, Oded Lachish, Yadu Vasudev |
| 2015 | Uniform Generation of Random Regular Graphs. Pu Gao, Nicholas C. Wormald |
| 2015 | Welfare Maximization with Limited Interaction. Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein |