| 2015 | Fast Lattice Point Enumeration with Minimal Overhead. | Daniele Micciancio, Michael Walter |
| 2015 | Online Stochastic Matching with Unequal Probabilities. | Aranyak Mehta, Bo Waggoner, Morteza Zadimoghaddam |
| 2015 | Robust randomized matchings. | Jannik Matuschke, Martin Skutella, Jos A. Soto |
| 2015 | An exact characterization of tractable demand patterns for maximum disjoint path problems. | Dniel Marx, Paul Wollan |
| 2015 | Zigzag Persistence via Reflections and Transpositions. | Clment Maria, Steve Y. Oudot |
| 2015 | Robust Probabilistic Inference. | Yishay Mansour, Aviad Rubinstein, Moshe Tennenholtz |
| 2015 | Approximate Nearest Line Search in High Dimensions. | Sepideh Mahabadi |
| 2015 | Fast Generation of Random Spanning Trees and the Effective Resistance Metric. | Aleksander Madry, Damian Straszak, Jakub Tarnawski |
| 2015 | FPTAS for Counting Monotone CNF. | Jingcheng Liu, Pinyan Lu |
| 2015 | On the Quickest Flow Problem in Dynamic Networks - A Parametric Min-Cost Flow Approach. | Maokai Lin, Patrick Jaillet |
| 2015 | The Parameterized Complexity of | Bingkai Lin |
| 2015 | On Uniform Capacitated | Shi Li |
| 2015 | Robust Price of Anarchy Bounds via LP and Fenchel Duality. | Janardhan Kulkarni, Vahab S. Mirrokni |
| 2015 | Internal Pattern Matching Queries in a Text and Applications. | Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen |
| 2015 | Distributed Computation of Large-scale Graph Problems. | Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Peter Robinson |
| 2015 | Streaming Lower Bounds for Approximating MAX-CUT. | Michael Kapralov, Sanjeev Khanna, Madhu Sudan |
| 2015 | The amortized cost of finding the minimum. | Haim Kaplan, Or Zamir, Uri Zwick |
| 2015 | The size of the core in assignment markets. | Yash Kanoria, Daniela Sabn, Jay Sethuraman |
| 2015 | Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy). | Sampath Kannan, Jamie Morgenstern, Aaron Roth, Zhiwei Steven Wu |
| 2015 | Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. | Bart M. P. Jansen, Dniel Marx |
| 2015 | New Approximations for Broadcast Scheduling via Variants of α-point Rounding. | Sungjin Im, Maxim Sviridenko |
| 2015 | A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]. | Sungjin Im, Shi Li, Benjamin Moseley, Eric Torng |
| 2015 | Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovsz Local Lemma. | David G. Harris |
| 2015 | Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. | Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang |
| 2015 | Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. | Venkatesan Guruswami, Euiwoong Lee |