| 2015 | Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic. | Marvin Knnemann, Bodo Manthey |
| 2015 | Algebraic Properties of Valued Constraint Satisfaction Problem. | Marcin Kozik, Joanna Ochremiak |
| 2015 | Nominal Kleene Coalgebra. | Dexter Kozen, Konstantinos Mamouras, Daniela Petrisan, Alexandra Silva |
| 2015 | Comparator Circuits over Finite Bounded Posets. | Balagopal Komarath, Jayalal Sarma, K. S. Sunil |
| 2015 | How Much Lookahead is Needed to Win Infinite Games? | Felix Klein, Martin Zimmermann |
| 2015 | Applicative Abstract Categorial Grammar. | Oleg Kiselyov |
| 2015 | Approximating CSPs Using LP Relaxation. | Subhash Khot, Rishi Saket |
| 2015 | Lower Bounds for Sums of Powers of Low Degree Univariates. | Neeraj Kayal, Pascal Koiran, Timothe Pecatte, Chandan Saha |
| 2015 | Finding a Path in Group-Labeled Graphs with Two Labels Forbidden. | Yasushi Kawase, Yusuke Kobayashi, Yutaro Yamaguchi |
| 2015 | Towards the Graph Minor Theorems for Directed Graphs. | Ken-ichi Kawarabayashi, Stephan Kreutzer |
| 2015 | A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set. | Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu |
| 2015 | An Algebraic Geometric Approach to Nivat's Conjecture. | Jarkko Kari, Michal Szabados |
| 2015 | Binary Pattern Tile Set Synthesis Is NP-hard. | Lila Kari, Steffen Kopecki, Pierre-tienne Meunier, Matthew J. Patitz, Shinnosuke Seki |
| 2015 | Normalization Phenomena in Asynchronous Networks. | Amin Karbasi, Johannes Lengler, Angelika Steger |
| 2015 | Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem. | Erez Kantor, Shay Kutten |
| 2015 | Near-Linear Query Complexity for Graph Inference. | Sampath Kannan, Claire Mathieu, Hang Zhou |
| 2015 | Query Complexity in Expectation. | Jedrzej Kaniewski, Troy Lee, Ronald de Wolf |
| 2015 | Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time. | Marcin Jurdzinski, Ranko Lazic, Sylvain Schmitz |
| 2015 | Local Reductions. | Hamid Jahanjou, Eric Miles, Emanuele Viola |
| 2015 | From Sequential Specifications to Eventual Consistency. | Radha Jagadeesan, James Riely |
| 2015 | Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities. | Sungjin Im, Benjamin Moseley |
| 2015 | Approximating the Expected Values for Combinatorial Optimization Problems over Stochastic Points. | Lingxiao Huang, Jian Li |
| 2015 | Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs. | Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai |
| 2015 | Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time. | Monika Henzinger, Sebastian Krinninger, Veronika Loitzenbauer |
| 2015 | Linear-Time List Recovery of High-Rate Expander Codes. | Brett Hemenway, Mary Wootters |