| 2021 | HyperLTL Satisfiability Is Σ₁¹-Complete, HyperCTL* Satisfiability Is Σ₁²-Complete. | Marie Fortin, Louwe B. Kuijer, Patrick Totzke, Martin Zimmermann |
| 2021 | Maximum Cut on Interval Graphs of Interval Count Four Is NP-Complete. | Celina M. H. de Figueiredo, Alexsander Andrade de Melo, Fabiano de S. Oliveira, Ana Silva |
| 2021 | Lower Bounds on Avoiding Thresholds. | Robert Ferens, Marek Szykula, Vojtech Vorel |
| 2021 | A Cubic Vertex-Kernel for Trivially Perfect Editing. | Mal Dumas, Anthony Perez, Ioan Todinca |
| 2021 | On Computing the Average Distance for Some Chordal-Like Graphs. | Guillaume Ducoffe |
| 2021 | Isometric Embeddings in Trees and Their Use in Distance Problems. | Guillaume Ducoffe |
| 2021 | Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances. | Gabriel L. Duarte, Mateus de Oliveira Oliveira, Uverton S. Souza |
| 2021 | Graph Characterization of the Universal Theory of Relations. | Amina Doumane |
| 2021 | Non-Axiomatizability of the Equational Theories of Positive Relation Algebras (Invited Talk). | Amina Doumane |
| 2021 | Pebble Transducers with Unary Output. | Gatan Douneau-Tabot |
| 2021 | Fuzzy Simultaneous Congruences. | Max A. Deppert, Klaus Jansen, Kim-Manuel Klein |
| 2021 | On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets. | Julian D'Costa, Engel Lefaucheux, Eike Neumann, Jol Ouaknine, James Worrell |
| 2021 | The Pseudo-Skolem Problem is Decidable. | Julian D'Costa, Toghrul Karimov, Rupak Majumdar, Jol Ouaknine, Mahmoud Salamati, Sadegh Soudjani, James Worrell |
| 2021 | On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism. | Anuj Dawar, Danny Vagnozzi |
| 2021 | Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles. | Samir Datta, Kishlaya Jaiswal |
| 2021 | Budgeted Dominating Sets in Uncertain Graphs. | Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy, David Peleg, R. Vijayaragunathan |
| 2021 | Diameter Versus Certificate Complexity of Boolean Functions. | Siddhesh Chaubal, Anna Gl |
| 2021 | Geometry of Interaction for ZX-Diagrams. | Kostia Chardonnet, Benot Valiron, Renaud Vilmart |
| 2021 | Black-Box Hypotheses and Lower Bounds. | Brynmor Chapman, R. Ryan Williams |
| 2021 | A Decidable Equivalence for a Turing-Complete, Distributed Model of Computation. | Arnaldo Cesco, Roberto Gorrieri |
| 2021 | Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem. | Silvia Butti, Vctor Dalmau |
| 2021 | Uncertain Curve Simplification. | Kevin Buchin, Maarten Lffler, Aleksandr Popov, Marcel Roeloffzen |
| 2021 | Dots & Boxes Is PSPACE-Complete. | Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna, Max van Mulken |
| 2021 | Finite Convergence of μ-Calculus Fixpoints on Genuinely Infinite Structures. | Florian Bruse, Marco Slzer, Martin Lange |
| 2021 | Reconfiguring Independent Sets on Interval Graphs. | Marcin Brianski, Stefan Felsner, Jedrzej Hodor, Piotr Micek |