| 2015 | Streaming Algorithms for Submodular Function Maximization. | Chandra Chekuri, Shalmoli Gupta, Kent Quanrud |
| 2015 | The Range of Topological Effects on Communication. | Arkadev Chattopadhyay, Atri Rudra |
| 2015 | Edit Distance for Pushdown Automata. | Krishnendu Chatterjee, Thomas A. Henzinger, Rasmus Ibsen-Jensen, Jan Otop |
| 2015 | The Complexity of Synthesis from Probabilistic Components. | Krishnendu Chatterjee, Laurent Doyen, Moshe Y. Vardi |
| 2015 | Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms. | Bernadette Charron-Bost, Matthias Fgger, Thomas Nowak |
| 2015 | Unit Interval Editing is Fixed-Parameter Tractable. | Yixin Cao |
| 2015 | Big Data on the Rise? - Testing Monotonicity of Distributions. | Clment L. Canonne |
| 2015 | Algorithms and Complexity for Turaev-Viro Invariants. | Benjamin A. Burton, Clment Maria, Jonathan Spreer |
| 2015 | Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. | Mark Bun, Justin Thaler |
| 2015 | Ultra-Fast Load Balancing on Scale-Free Networks. | Karl Bringmann, Tobias Friedrich, Martin Hoefer, Ralf Rothenberger, Thomas Sauerwald |
| 2015 | On Reducing Linearizability to State Reachability. | Ahmed Bouajjani, Michael Emmi, Constantin Enea, Jad Hamza |
| 2015 | Analysis of Probabilistic Systems via Generating Functions and Pad Approximation. | Michele Boreale |
| 2015 | Containment of Monadic Datalog Programs via Bounded Clique-Width. | Mikolaj Bojanczyk, Filip Murlak, Adam Witkowski |
| 2015 | Constraint Satisfaction Problems over the Integers with Successor. | Manuel Bodirsky, Barnaby Martin, Antoine Mottet |
| 2015 | Spotting Trees with Few Leaves. | Andreas Bjrklund, Vikram Kamat, Lukasz Kowalik, Meirav Zehavi |
| 2015 | The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems. | Andreas Bjrklund, Holger Dell, Thore Husfeldt |
| 2015 | What Percentage of Programs Halt? | Laurent Bienvenu, Damien Desfontaines, Alexander Shen |
| 2015 | Design of Dynamic Algorithms via Primal-Dual Method. | Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano |
| 2015 | Maintaining Near-Popular Matchings. | Sayan Bhattacharya, Martin Hoefer, Chien-Chung Huang, Telikepalli Kavitha, Lisa Wagner |
| 2015 | Simultaneous Approximation of Constraint Satisfaction Problems. | Amey Bhangale, Swastik Kopparty, Sushant Sachdeva |
| 2015 | Feasible Interpolation for QBF Resolution Calculi. | Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla |
| 2015 | Fully Dynamic Matching in Bipartite Graphs. | Aaron Bernstein, Cliff Stein |
| 2015 | Limitations of Algebraic Approaches to Graph Isomorphism Testing. | Christoph Berkholz, Martin Grohe |
| 2015 | Language Emptiness of Continuous-Time Parametric Timed Automata. | Nikola Benes, Peter Bezdek, Kim Guldstrand Larsen, Jir Srba |
| 2015 | Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources. | Salman Beigi, Omid Etesami, Amin Gohari |