| 2015 | Longest Gapped Repeats and Palindromes. | Marius Dumitran, Florin Manea |
| 2015 | Weighted Automata and Logics on Graphs. | Manfred Droste, Stefan Dck |
| 2015 | Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus. | Catalin Dima, Bastien Maubert, Sophie Pinchinat |
| 2015 | Classes of Languages Generated by the Kleene Star of a Word. | Laure Daviaud, Charles Paperman |
| 2015 | Locally Chain-Parsable Languages. | Stefano Crespi-Reghizzi, Violetta Lonati, Dino Mandrioli, Matteo Pradella |
| 2015 | Efficient Computations over Encrypted Data Blocks. | Giovanni Di Crescenzo, Brian A. Coan, Jonathan Kirsch |
| 2015 | Oblivious Transfer from Weakly Random Self-Reducible Public-Key Cryptosystem. | Claude Crpeau, Raza Ali Kazmi |
| 2015 | Network Creation Games: Think Global - Act Local. | Andreas Cord-Landwehr, Pascal Lenzner |
| 2015 | Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem. | Daniyar Chumbalov, Andrei Romashchenko |
| 2015 | Optimal Algorithms and a PTAS for Cost-Aware Scheduling. | Lin Chen, Nicole Megow, Roman Rischke, Leen Stougie, Jos Verschae |
| 2015 | Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases. | Ruiwen Chen |
| 2015 | Mutual Dimension and Random Sequences. | Adam Case, Jack H. Lutz |
| 2015 | Optimal Bounds for Estimating Entropy with PMF Queries. | Cafer Caferov, Baris Kaya, Ryan O'Donnell, A. C. Cem Say |
| 2015 | A Circuit Complexity Approach to Transductions. | Michal Cadilhac, Andreas Krebs, Michael Ludwig, Charles Paperman |
| 2015 | Phase Transition for Local Search on Planted SAT. | Andrei A. Bulatov, Evgeny S. Skvortsov |
| 2015 | New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory. | Vladimir Braverman, Zaoxing Liu, Tejasvam Singh, N. V. Vinodchandran, Lin F. Yang |
| 2015 | Bounding the Clique-Width of H-free Chordal Graphs. | Andreas Brandstdt, Konrad K. Dabrowski, Shenwei Huang, Danil Paulusma |
| 2015 | Exponential-Size Model Property for PDL with Separating Parallel Composition. | Joseph Boudou |
| 2015 | Equality, Revisited. | Ralph Bottesch, Dmitry Gavinsky, Hartmut Klauck |
| 2015 | Minimal and Monotone Minimal Perfect Hash Functions. | Paolo Boldi |
| 2015 | Recurrence Function on Sturmian Words: A Probabilistic Study. | Valrie Berth, Eda Cesaratto, Pablo Rotondo, Brigitte Valle, Alfredo Viola |
| 2015 | Algebraic Synchronization Criterion and Computing Reset Words. | Mikhail V. Berlinkov, Marek Szykula |
| 2015 | Metric Dimension of Bounded Width Graphs. | Rmy Belmonte, Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan |
| 2015 | On Dynamic DFS Tree in Directed Graphs. | Surender Baswana, Keerti Choudhary |
| 2015 | Almost All Functions Require Exponential Energy. | Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato |