| 2021 | A Recursion-Theoretic Characterization of the Probabilistic Class PP. | Ugo Dal Lago, Reinhard Kahle, Isabel Oitavem |
| 2021 | Connecting Constructive Notions of Ordinals in Homotopy Type Theory. | Nicolai Kraus, Fredrik Nordvall Forsberg, Chuangjie Xu |
| 2021 | The Power of One Clean Qubit in Communication Complexity. | Hartmut Klauck, Debbie Lim |
| 2021 | Improved Upper Bounds for the Rigidity of Kronecker Products. | Bohdan Kivva |
| 2021 | An Approximation Algorithm for the Matrix Tree Multiplication Problem. | Mahmoud Abo Khamis, Ryan R. Curtin, Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs, Alireza Samadian |
| 2021 | On Positivity and Minimality for Second-Order Holonomic Sequences. | George Kenison, Oleksiy Klurman, Engel Lefaucheux, Florian Luca, Pieter Moree, Jol Ouaknine, Markus A. Whiteland, James Worrell |
| 2021 | Sets of Linear Forms Which Are Hard to Compute. | Michael Kaminski, Igor E. Shparlinski |
| 2021 | Griddings of Permutations and Hardness of Pattern Matching. | Vt Jelnek, Michal Opler, Jakub Pekrek |
| 2021 | On the Hardness of Compressing Weights. | Bart M. P. Jansen, Shivesh Kumar Roy, Michal Wlodarczyk |
| 2021 | The Simplest Non-Regular Deterministic Context-Free Language. | Petr Jancar, Jir Sma |
| 2021 | Ordered Fragments of First-Order Logic. | Reijo Jaakkola |
| 2021 | A Homological Condition on Equational Unifiability. | Mirai Ikebuchi |
| 2021 | On Search Complexity of Discrete Logarithm. | Pavel Hubcek, Jan Vclavek |
| 2021 | Test of Quantumness with Small-Depth Quantum Circuits. | Shuichi Hirahara, Franois Le Gall |
| 2021 | Online Domination: The Value of Getting to Know All Your Neighbors. | Hovhannes A. Harutyunyan, Denis Pankratov, Jesse Racicot |
| 2021 | Obstructing Classification via Projection. | Pantea Haghighatkhah, Wouter Meulemans, Bettina Speckmann, Jrme Urhausen, Kevin Verbeek |
| 2021 | On Deciding Linear Arithmetic Constraints Over p-adic Integers for All Primes. | Christoph Haase, Alessio Mansutti |
| 2021 | Perfect Forests in Graphs and Their Extensions. | Gregory Z. Gutin, Anders Yeo |
| 2021 | A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct. | Shibashis Guha, Ismal Jecker, Karoliina Lehtinen, Martin Zimmermann |
| 2021 | Optimal Regular Expressions for Palindromes of Given Length. | Hermann Gruber, Markus Holzer |
| 2021 | A Note on the Join of Varieties of Monoids with LI. | Nathan Grosshans |
| 2021 | A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk). | Martin Grohe |
| 2021 | Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs. | Adam Glos, Martins Kokainis, Ryuhei Mori, Jevgenijs Vihrovs |
| 2021 | Keyboards as a New Model of Computation. | Yoan Gran, Bastien Laboureix, Corto Mascle, Valentin D. Richard |
| 2021 | Matching Patterns with Variables Under Hamming Distance. | Pawel Gawrychowski, Florin Manea, Stefan Siemer |