| 2016 | Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials. | Bart M. P. Jansen, Astrid Pieterse |
| 2016 | Deciding Semantic Finiteness of Pushdown Processes and First-Order Grammars w.r.t. Bisimulation Equivalence. | Petr Jancar |
| 2016 | Computational and Proof Complexity of Partial String Avoidability. | Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin |
| 2016 | Polynomial Space Randomness in Analysis. | Xiang Huang, Donald M. Stull |
| 2016 | Competitive Packet Routing with Priority Lists. | Tobias Harks, Britta Peis, Daniel Schmand, Laura Vargas Koch |
| 2016 | On Synchronizing Colorings and the Eigenvectors of Digraphs. | Vladimir V. Gusev, Elena V. Pribavkina |
| 2016 | Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields. | Zeyu Guo, Anand Kumar Narayanan, Chris Umans |
| 2016 | Pointer Quantum PCPs and Multi-Prover Games. | Alex Bredariol Grilo, Iordanis Kerenidis, Attila Pereszlnyi |
| 2016 | Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework. | Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, Suguru Tamaki |
| 2016 | On the Limits of Gate Elimination. | Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov |
| 2016 | Connected Reversible Mealy Automata of Prime Size Cannot Generate Infinite Burnside Groups. | Thibault Godin, Ines Klimann |
| 2016 | Programming Biomolecules That Fold Greedily During Transcription. | Cody W. Geary, Pierre-Etienne Meunier, Nicolas Schabanel, Shinnosuke Seki |
| 2016 | On the Complexity Landscape of Connected f-Factor Problems. | Robert Ganian, N. S. Narayanaswamy, Sebastian Ordyniak, C. S. Rahul, M. S. Ramanujan |
| 2016 | On Existential MSO and its Relation to ETH. | Robert Ganian, Ronald de Haan, Iyad A. Kanj, Stefan Szeider |
| 2016 | Determining Sets of Quasiperiods of Infinite Words. | Guilhem Gamard, Gwnal Richomme |
| 2016 | On Planar Valued CSPs. | Peter Fulla, Stanislav Zivn |
| 2016 | Computing DAWGs and Minimal Absent Words in Linear Time for Integer Alphabets. | Yuta Fujishige, Yuki Tsujimaru, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda |
| 2016 | Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms. | Tobias Friedrich |
| 2016 | On the General Chain Pair Simplification Problem. | Chenglin Fan, Omrit Filtser, Matthew J. Katz, Binhai Zhu |
| 2016 | Ride Sharing with a Vehicle of Unlimited Capacity. | Angelo Fanelli, Gianluigi Greco |
| 2016 | Preprocessing Under Uncertainty: Matroid Intersection. | Stefan Fafianie, Eva-Maria C. Hols, Stefan Kratsch, Vuong Anh Quyen |
| 2016 | A Single-Exponential Fixed-Parameter Algorithm for Distance-Hereditary Vertex Deletion. | Eduard Eiben, Robert Ganian, O-joung Kwon |
| 2016 | Faster Algorithms for the Maximum Common Subtree Isomorphism Problem. | Andre Droschinsky, Nils M. Kriege, Petra Mutzel |
| 2016 | Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers. | Titus Dose |
| 2016 | A Note on the Advice Complexity of Multipass Randomized Logspace. | Peter Dixon, Debasis Mandal, Aduri Pavan, N. V. Vinodchandran |