| 2015 | The Power of Asymmetry in Constant-Depth Circuits. | Alexander A. Sherstov |
| 2015 | Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem. | F. Bruce Shepherd, Adrian Vetta, Gordon T. Wilfong |
| 2015 | Incidences between Points and Lines in R^4. | Micha Sharir, Noam Solomon |
| 2015 | Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable. | Helmut Seidl, Sebastian Maneth, Gregor Kemper |
| 2015 | Symbolic Integration and the Complexity of Computing Averages. | Leonard J. Schulman, Alistair Sinclair, Piyush Srivastava |
| 2015 | Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems. | Barna Saha |
| 2015 | An Average-Case Depth Hierarchy Theorem for Boolean Circuits. | Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan |
| 2015 | The Average Sensitivity of Bounded-Depth Formulas. | Benjamin Rossman |
| 2015 | A Robust Sparse Fourier Transform in the Continuous Setting. | Eric Price, Zhao Song |
| 2015 | Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line. | Amir Nayyeri, Benjamin Raichel |
| 2015 | Compressing and Teaching for Low VC-Dimension. | Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff |
| 2015 | Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. | Adam W. Marcus, Daniel A. Spielman, Nikhil Srivastava |
| 2015 | Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. | Konstantin Makarychev, Yury Makarychev, Yuan Zhou |
| 2015 | Random Matrices: l1 Concentration and Dictionary Learning with Few Samples. | Kyle Luh, Van Vu |
| 2015 | Three-Source Extractors for Polylogarithmic Min-Entropy. | Xin Li |
| 2015 | Quantum Expander Codes. | Anthony Leverrier, Jean-Pierre Tillich, Gilles Zmor |
| 2015 | A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization. | Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong |
| 2015 | Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time. | Yin Tat Lee, He Sun |
| 2015 | Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. | Yin Tat Lee, Aaron Sidford |
| 2015 | Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment. | Tsvi Kopelowitz, Ely Porat |
| 2015 | The Complexity of General-Valued CSPs. | Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolnek |
| 2015 | On Monotonicity Testing and Boolean Isoperimetric Type Theorems. | Subhash Khot, Dor Minzer, Muli Safra |
| 2015 | The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication. | Erez Kantor, Zvi Lotker, Merav Parter, David Peleg |
| 2015 | Competitive Flow Time Algorithms for Polyhedral Scheduling. | Sungjin Im, Janardhan Kulkarni, Kamesh Munagala |
| 2015 | Tight Bounds for Online Vector Scheduling. | Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi |