| 2017 | Sensitivity Conjecture and Log-Rank Conjecture for Functions with Small Alternating Numbers. | Chengyu Lin, Shengyu Zhang |
| 2017 | The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights. | Jiabao Lin, Hanpin Wang |
| 2017 | Improved Algorithms for MST and Metric-TSP Interdiction. | Andr Linhares, Chaitanya Swamy |
| 2017 | Improved Hardness for Cut, Interdiction, and Firefighter Problems. | Euiwoong Lee |
| 2017 | On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. | Marvin Knnemann, Ramamohan Paturi, Stefan Schneider |
| 2017 | Conditional Lower Bounds for All-Pairs Max-Flow. | Robert Krauthgamer, Ohad Trabelsi |
| 2017 | The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback. | Amos Korman, Yoav Rodeh |
| 2017 | Reordering Buffer Management with a Logarithmic Guarantee in General Metric Spaces. | Matthias Kohler, Harald Rcke |
| 2017 | Additive Spanners and Distance Oracles in Quadratic Time. | Mathias Bk Tejs Knudsen |
| 2017 | Quantum Automata Cannot Detect Biased Coins, Even in the Limit. | Guy Kindler, Ryan O'Donnell |
| 2017 | String Inference from Longest-Common-Prefix Array. | Juha Krkkinen, Marcin Piatkowski, Simon J. Puglisi |
| 2017 | Conservative Extensions in Guarded and Two-Variable Fragments. | Jean Christoph Jung, Carsten Lutz, Mauricio Martel, Thomas Schneider, Frank Wolter |
| 2017 | Word Equations in Nondeterministic Linear Space. | Artur Jez |
| 2017 | Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!. | Rajesh Jayaram, Barna Saha |
| 2017 | Linear-Time Kernelization for Feedback Vertex Set. | Yoichi Iwata |
| 2017 | Combinatorial Secretary Problems with Ordinal Information. | Martin Hoefer, Bojana Kodric |
| 2017 | Efficient Algorithms for Graph-Related Problems in Computer-Aided Verification (Invited Talk). | Monika Henzinger |
| 2017 | k-Distinct In- and Out-Branchings in Digraphs. | Gregory Z. Gutin, Felix Reidl, Magnus Wahlstrm |
| 2017 | Subspace Designs Based on Algebraic Function Fields. | Venkatesan Guruswami, Chaoping Xing, Chen Yuan |
| 2017 | Multiple Source Dual Fault Tolerant BFS Trees. | Manoj Gupta, Shahbaz Khan |
| 2017 | Tight Lower Bounds for Multiplicative Weights Algorithmic Families. | Nick Gravin, Yuval Peres, Balasubramanian Sivan |
| 2017 | Deterministic Graph Exploration with Advice. | Barun Gorain, Andrzej Pelc |
| 2017 | Randomized Communication vs. Partition Number. | Mika Gs, T. S. Jayram, Toniann Pitassi, Thomas Watson |
| 2017 | Bipartite Perfect Matching in Pseudo-Deterministic NC. | Shafi Goldwasser, Ofer Grossman |
| 2017 | Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier. | Omer Gold, Micha Sharir |