| 2015 | Hollow Heaps. | Thomas Dueholm Hansen, Haim Kaplan, Robert Endre Tarjan, Uri Zwick |
| 2015 | The Odds of Staying on Budget. | Christoph Haase, Stefan Kiefer |
| 2015 | Fast Algorithms for Diameter-Optimally Augmenting Paths. | Ulrike Groe, Joachim Gudmundsson, Christian Knauer, Michiel H. M. Smid, Fabian Stehn |
| 2015 | On Logical Relations and Conservativity. | Philippe de Groote |
| 2015 | Adaptively Secure Coin-Flipping, Revisited. | Shafi Goldwasser, Yael Tauman Kalai, Sunoo Park |
| 2015 | Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract). | Oded Goldreich, Tom Gur, Ron D. Rothblum |
| 2015 | Approximately Counting Locally-Optimal Structures. | Leslie Ann Goldberg, Rob Gysel, John Lapinskas |
| 2015 | Uniform Kernelization Complexity of Hitting Forbidden Minors. | Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, Saket Saurabh |
| 2015 | Selling Two Goods Optimally. | Yiannis Giannakopoulos, Elias Koutsoupias |
| 2015 | Ground State Connectivity of Local Hamiltonians. | Sevag Gharibian, Jamie Sikora |
| 2015 | Distributed Broadcast Revisited: Towards Universal Optimality. | Mohsen Ghaffari |
| 2015 | 2-Vertex Connectivity in Directed Graphs. | Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, Nikos Parotsidis |
| 2015 | Optimal Encodings for Range Top- k k , Selection, and Min-Max. | Pawel Gawrychowski, Patrick K. Nicholson |
| 2015 | Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search. | Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2015 | Bidirectional Functional Semantics for Pregroup Grammars. | Gabriel Gaudreault |
| 2015 | Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets. | Serge Gaspers, Gregory B. Sorkin |
| 2015 | ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria. | Jugal Garg, Ruta Mehta, Vijay V. Vazirani, Sadra Yazdanbod |
| 2015 | Taylor Polynomial Estimator for Estimating Frequency Moments. | Sumit Ganguly |
| 2015 | Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard. | Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum |
| 2015 | Tight Bounds for Cost-Sharing in Weighted Congestion Games. | Martin Gairing, Konstantinos Kollias, Grammateia Kotsialou |
| 2015 | A Galois Connection for Valued Constraint Languages of Infinite Size. | Peter Fulla, Stanislav Zivn |
| 2015 | On the Diameter of Hyperbolic Random Graphs. | Tobias Friedrich, Anton Krohmer |
| 2015 | Relative Discrepancy Does not Separate Information and Communication Complexity. | Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurire, Jrmie Roland |
| 2015 | Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree. | Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh |
| 2015 | Lower Bounds for the Graph Homomorphism Problem. | Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin |