| 2021 | 4 vs 7 Sparse Undirected Unweighted Diameter is SETH-Hard at Time n^{4/3}. Édouard Bonnet |
| 2021 | 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, Glasgow, Scotland (Virtual Conference), July 12-16, 2021 Nikhil Bansal, Emanuela Merelli, James Worrell |
| 2021 | A Complexity Approach to Tree Algebras: the Bounded Case. Thomas Colcombet, Arthur Jaquard |
| 2021 | A Linear-Time n Karl Bringmann, Debarati Das |
| 2021 | A Rice's Theorem for Abstract Semantics. Paolo Baldan, Francesco Ranzato, Linpeng Zhang |
| 2021 | A Spectral Independence View on Hard Spheres via Block Dynamics. Tobias Friedrich, Andreas Göbel, Martin S. Krejca, Marcus Pappik |
| 2021 | A Subexponential Algorithm for ARRIVAL. Bernd Gärtner, Sebastian Haslebacher, Hung P. Hoang |
| 2021 | A Very Sketchy Talk (Invited Talk). David P. Woodruff |
| 2021 | Additive Approximation Schemes for Load Balancing Problems. Moritz Buchem, Lars Rohwedder, Tjark Vredeveld, Andreas Wiese |
| 2021 | Algebraic Proof Systems (Invited Talk). Toniann Pitassi |
| 2021 | Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths. Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu |
| 2021 | Almost-Linear-Time Weighted 𝓁 Deeksha Adil, Brian Bullins, Rasmus Kyng, Sushant Sachdeva |
| 2021 | Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs. Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, Andrzej Pelc |
| 2021 | An Almost Optimal Edit Distance Oracle. Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, Oren Weimann |
| 2021 | An Efficient Coding Theorem via Probabilistic Representations and Its Applications. Zhenjian Lu, Igor C. Oliveira |
| 2021 | An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D. Pankaj K. Agarwal, Alex Steiger |
| 2021 | Analysis of Smooth Heaps and Slim Heaps. Maria Hartmann, László Kozma, Corwin Sinnamon, Robert E. Tarjan |
| 2021 | Analytical Differential Calculus with Integration. Han Xu, Zhenjiang Hu |
| 2021 | Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms. Ojas Parekh, Kevin Thompson |
| 2021 | Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs. Ewan Davies, Will Perkins |
| 2021 | Approximating Maximum Integral Multiflows on Bounded Genus Graphs. Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Jens Vygen |
| 2021 | Approximation Algorithms for Min-Distance Problems in DAGs. Mina Dalirrooyfard, Jenny Kaufmann |
| 2021 | Arboreal Categories and Resources. Samson Abramsky, Luca Reggio |
| 2021 | Automorphisms and Isomorphisms of Maps in Linear Time. Ken-ichi Kawarabayashi, Bojan Mohar, Roman Nedela, Peter Zeman |
| 2021 | Beating Two-Thirds For Random-Order Streaming Matching. Sepehr Assadi, Soheil Behnezhad |
| 2021 | Beyond PCSP(1-in-3, NAE). Alex Brandts, Stanislav Zivný |
| 2021 | Breaking O(nr) for Matroid Intersection. Joakim Blikstad |
| 2021 | Breaking the 2ⁿ Barrier for 5-Coloring and 6-Coloring. Or Zamir |
| 2021 | Breaking the Barrier Of 2 for the Competitiveness of Longest Queue Drop. Antonios Antoniadis, Matthias Englert, Nicolaos Matsakis, Pavel Veselý |
| 2021 | Coboundary and Cosystolic Expansion from Strong Symmetry. Tali Kaufman, Izhar Oppenheim |
| 2021 | Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case. Markus Anders, Pascal Schweitzer, Florian Wetzels |
| 2021 | Comparison-Free Polyregular Functions. Lê Thành Dung Nguyên, Camille Noûs, Cécilia Pradic |
| 2021 | Computational Characterization of Surface Entropies for ℤ² Subshifts of Finite Type. Antonin Callard, Pascal Vanier |
| 2021 | Conditional Dichotomy of Boolean Ordered Promise CSPs. Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep |
| 2021 | Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime. Zachary Friggstad, Chaitanya Swamy |
| 2021 | Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time. Yong Gu, Hanlin Ren |
| 2021 | Counting Short Vector Pairs by Inner Product and Relations to the Permanent. Andreas Björklund, Petteri Kaski |
| 2021 | Crossing-Optimal Extension of Simple Drawings. Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada, Birgit Vogtenhuber |
| 2021 | Current Algorithms for Detecting Subgraphs of Bounded Treewidth Are Probably Optimal. Karl Bringmann, Jasper Slusallek |
| 2021 | Datalog-Expressibility for Monadic and Guarded Second-Order Logic. Manuel Bodirsky, Simon Knäuer, Sebastian Rudolph |
| 2021 | Decision Problems for Second-Order Holonomic Recurrences. Eike Neumann, Joël Ouaknine, James Worrell |
| 2021 | Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary. Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, Christian Wulff-Nilsen |
| 2021 | Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth. Dániel Marx, Govind S. Sankar, Philipp Schepper |
| 2021 | Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders. Marc Roth, Johannes Schmitt, Philip Wellnitz |
| 2021 | Deterministic Maximum Flows in Simple Graphs. Tianyi Zhang |
| 2021 | Deterministic Rounding of Dynamic Fractional Matchings. Sayan Bhattacharya, Peter Kiss |
| 2021 | Deterministic and Game Separability for Regular Languages of Infinite Trees. Lorenzo Clemente, Michal Skrzypczak |
| 2021 | Direct Sum and Partitionability Testing over General Groups. Andrej Bogdanov, Gautam Prakriya |
| 2021 | Distributed Subgraph Finding: Progress and Challenges (Invited Talk). Keren Censor-Hillel |
| 2021 | Dynamic Enumeration of Similarity Joins. Pankaj K. Agarwal, Xiao Hu, Stavros Sintos, Jun Yang |
| 2021 | Dynamic Membership for Regular Languages. Antoine Amarilli, Louis Jachiet, Charles Paperman |
| 2021 | Efficient Splitting of Necklaces. Noga Alon, Andrei Graur |
| 2021 | Elementary Equivalence Versus Isomorphism in Semiring Semantics. Erich Grädel, Lovro Mrkonjic |
| 2021 | Error Resilient Space Partitioning (Invited Talk). Orr Dunkelman, Zeev Geyzel, Chaya Keller, Nathan Keller, Eyal Ronen, Adi Shamir, Ran J. Tessler |
| 2021 | Fast n-Fold Boolean Convolution via Additive Combinatorics. Karl Bringmann, Vasileios Nakos |
| 2021 | Faster Algorithms for Bounded Liveness in Graphs and Game Graphs. Krishnendu Chatterjee, Monika Henzinger, Sagar Kale, Alexander Svozil |
| 2021 | Faster Algorithms for Bounded Tree Edit Distance. Shyan Akmal, Ce Jin |
| 2021 | Faster Algorithms for Rooted Connectivity in Directed Graphs. Chandra Chekuri, Kent Quanrud |
| 2021 | Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths. Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams, Yinzhan Xu |
| 2021 | Fault Tolerant Max-Cut. Keren Censor-Hillel, Noa Marelly, Roy Schwartz, Tigran Tonoyan |
| 2021 | Fine-Grained Hardness for Edit Distance to a Fixed Sequence. Amir Abboud, Virginia Vassilevska Williams |
| 2021 | Fluted Logic with Counting. Ian Pratt-Hartmann |
| 2021 | Fourier Conjectures, Correlation Bounds, and Majority. Emanuele Viola |
| 2021 | From Verification to Causality-Based Explications (Invited Talk). Christel Baier, Clemens Dubslaff, Florian Funke, Simon Jantsch, Rupak Majumdar, Jakob Piribauer, Robin Ziemek |
| 2021 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2021 | Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems. Adam Karczmarz |
| 2021 | Genome Assembly, from Practice to Theory: Safe, Complete and Linear-Time. Massimo Cairo, Romeo Rizzi, Alexandru I. Tomescu, Elia C. Zirondelli |
| 2021 | Graph Similarity and Homomorphism Densities. Jan Böker |
| 2021 | Guarded Kleene Algebra with Tests: Coequations, Coinduction, and Completeness. Todd Schmid, Tobias Kappé, Dexter Kozen, Alexandra Silva |
| 2021 | Haystack Hunting Hints and Locker Room Communication. Artur Czumaj, George Kontogeorgiou, Mike Paterson |
| 2021 | High-Girth Near-Ramanujan Graphs with Lossy Vertex Expansion. Theo McKenzie, Sidhanth Mohanty |
| 2021 | Higher-Order Model Checking Step by Step. Pawel Parys |
| 2021 | How to Send a Real Number Using a Single Bit (And Some Shared Randomness). Ran Ben Basat, Michael Mitzenmacher, Shay Vargaftik |
| 2021 | Improved Approximation Factor for Adaptive Influence Maximization via Simple Greedy Strategies. Gianlorenzo D'Angelo, Debashmita Poddar, Cosimo Vinci |
| 2021 | Improved Approximation for Longest Common Subsequence over Small Alphabets. Shyan Akmal, Virginia Vassilevska Williams |
| 2021 | Improved Lower Bounds for Reachability in Vector Addition Systems. Wojciech Czerwinski, Slawomir Lasota, Lukasz Orlikowski |
| 2021 | Improving Gebauer's Construction of 3-Chromatic Hypergraphs with Few Edges. Jakub Kozik |
| 2021 | Inference Systems with Corules for Fair Subtyping and Liveness Properties of Binary Session Types. Luca Ciccone, Luca Padovani |
| 2021 | Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity. Chandra Chekuri, Kent Quanrud |
| 2021 | Kernelization, Proof Complexity and Social Choice. Gabriel Istrate, Cosmin Bonchis, Adrian Craciun |
| 2021 | Knapsack and Subset Sum with Small Items. Adam Polak, Lars Rohwedder, Karol Wegrzycki |
| 2021 | LF Successor: Compact Space Indexing for Order-Isomorphic Pattern Matching. Arnab Ganguly, Dhrumil Patel, Rahul Shah, Sharma V. Thankachan |
| 2021 | Learning Stochastic Decision Trees. Guy Blanc, Jane Lange, Li-Yang Tan |
| 2021 | Lifting for Constant-Depth Circuits and Applications to MCSP. Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova |
| 2021 | Linear Time Runs Over General Ordered Alphabets. Jonas Ellert, Johannes Fischer |
| 2021 | Local Approximations of the Independent Set Polynomial. Dimitris Achlioptas, Kostas Zampetakis |
| 2021 | Logarithmic Weisfeiler-Leman Identifies All Planar Graphs. Martin Grohe, Sandra Kiefer |
| 2021 | Lower Bounds on Dynamic Programming for Maximum Weight Independent Set. Tuukka Korhonen |
| 2021 | Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹. Lijie Chen, Zhenjian Lu, Xin Lyu, Igor C. Oliveira |
| 2021 | Matching on the Line Admits No o(√log n)-Competitive Algorithm. Enoch Peserico, Michele Scquizzato |
| 2021 | Maximum Matchings and Popularity. Telikepalli Kavitha |
| 2021 | Minimum Stable Cut and Treewidth. Michael Lampis |
| 2021 | Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan. Sharat Ibrahimpur, Chaitanya Swamy |
| 2021 | Multiple Random Walks on Graphs: Mixing Few to Cover Many. Nicolás Rivera, Thomas Sauerwald, John Sylvester |
| 2021 | Near-Optimal Schedules for Simultaneous Multicasts. Bernhard Haeupler, D. Ellis Hershkowitz, David Wajc |
| 2021 | Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs. Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu |
| 2021 | New Sublinear Algorithms and Lower Bounds for LIS Estimation. Ilan Newman, Nithin Varma |
| 2021 | New Techniques for Universality in Unambiguous Register Automata. Wojciech Czerwinski, Antoine Mottet, Karin Quaas |
| 2021 | Non-Mergeable Sketching for Cardinality Estimation. Seth Pettie, Dingyu Wang, Longhui Yin |
| 2021 | On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications. Sayan Bandyapadhyay, Fedor V. Fomin, Kirill Simonov |
| 2021 | On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order. J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, Tobias Friedrich |
| 2021 | On Greedily Packing Anchored Rectangles. Christoph Damerius, Dominik Kaaser, Peter Kling, Florian Schneider |
| 2021 | On the Approximability of Multistage Min-Sum Set Cover. Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos, Georgios Piliouras, Stratis Skoulakis |
| 2021 | Online Stochastic Matching with Edge Arrivals. Nick Gravin, Zhihao Gavin Tang, Kangning Wang |
| 2021 | Optimal Fine-Grained Hardness of Approximation of Linear Equations. Mitali Bafna, Nikhil Vyas |
| 2021 | Optimal Spectral-Norm Approximate Minimization of Weighted Finite Automata. Borja Balle, Clara Lacroce, Prakash Panangaden, Doina Precup, Guillaume Rabusseau |
| 2021 | Optimal Transformations of Games and Automata Using Muller Conditions. Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow |
| 2021 | Optimal-Time Queries on BWT-Runs Compressed Indexes. Takaaki Nishimoto, Yasuo Tabei |
| 2021 | Parameterized Applications of Symbolic Differentiation of (Totally) Multilinear Polynomials. Cornelius Brand, Kevin Pratt |
| 2021 | Playing Stochastically in Weighted Timed Games to Emulate Memory. Benjamin Monmege, Julie Parreaux, Pierre-Alain Reynier |
| 2021 | Powerset-Like Monads Weakly Distribute over Themselves in Toposes and Compact Hausdorff Spaces. Alexandre Goy, Daniela Petrisan, Marc Aiguier |
| 2021 | Property Testing of Regular Languages with Applications to Streaming Property Testing of Visibly Pushdown Languages. Gabriel Bathie, Tatiana Starikovskaya |
| 2021 | Quantum Algorithms for Matrix Scaling and Matrix Balancing. Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, Ronald de Wolf |
| 2021 | Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. Uma Girish, Ran Raz, Wei Zhan |
| 2021 | Quantum Query Complexity with Matrix-Vector Products. Andrew M. Childs, Shih-Han Hung, Tongyang Li |
| 2021 | Quantum Relational Hoare Logic with Expectations. Yangjia Li, Dominique Unruh |
| 2021 | Quasi-Polynomial Time Algorithms for Free Quantum Games in Bounded Dimension. Hyejung H. Jee, Carlo Sparaciari, Omar Fawzi, Mario Berta |
| 2021 | Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications. Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, Qianfan Zhang |
| 2021 | Relational Algorithms for k-Means Clustering. Benjamin Moseley, Kirk Pruhs, Alireza Samadian, Yuyan Wang |
| 2021 | Relaxed Locally Correctable Codes with Improved Parameters. Vahid R. Asadi, Igor Shinkar |
| 2021 | Revisiting Priority k-Center: Fairness and Outliers. Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, Maryam Negahbani |
| 2021 | Search Problems in Trees with Symmetries: Near Optimal Traversal Strategies for Individualization-Refinement Algorithms. Markus Anders, Pascal Schweitzer |
| 2021 | Separations for Estimating Large Frequency Moments on Data Streams. David P. Woodruff, Samson Zhou |
| 2021 | Smooth Approximations and Relational Width Collapses. Antoine Mottet, Tomás Nagy, Michael Pinsker, Michal Wrona |
| 2021 | SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization. Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth |
| 2021 | Sorting Short Integers. Michal Koucký, Karel Král |
| 2021 | Sparsification of Directed Graphs via Cut Balance. Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, Kevin Sun |
| 2021 | Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence. Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, Yu Zheng |
| 2021 | Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem. Eleni Batziou, Kristoffer Arnsfelt Hansen, Kasper Høgh |
| 2021 | Structural Iterative Rounding for Generalized k-Median Problems. Anupam Gupta, Benjamin Moseley, Rudy Zhou |
| 2021 | Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries. Yu Chen, Sanjeev Khanna, Ansh Nagda |
| 2021 | Symmetries and Complexity (Invited Talk). Andrei A. Bulatov |
| 2021 | Testing Dynamic Environments: Back to Basics. Yonatan Nakar, Dana Ron |
| 2021 | Testing Triangle Freeness in the General Model in Graphs with Arboricity O(√n). Reut Levi |
| 2021 | The Greedy Algorithm Is not Optimal for On-Line Edge Coloring. Amin Saberi, David Wajc |
| 2021 | The Structure of Minimum Vertex Cuts. Seth Pettie, Longhui Yin |
| 2021 | The Submodular Santa Claus Problem in the Restricted Assignment Case. Étienne Bamas, Paritosh Garg, Lars Rohwedder |
| 2021 | The Theory of Concatenation over Finite Models. Dominik D. Freydenberger, Liat Peterfreund |
| 2021 | Towards the k-Server Conjecture: A Unifying Potential, Pushing the Frontier to the Circle. Christian Coester, Elias Koutsoupias |
| 2021 | Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times. Marcin Bienkowski, Artur Kraska, Hsiang-Hsuan Liu |
| 2021 | Truthful Allocation in Graphs and Hypergraphs. George Christodoulou, Elias Koutsoupias, Annamária Kovács |
| 2021 | Twin-width III: Max Independent Set, Min Dominating Set, and Coloring. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, Rémi Watrigant |
| 2021 | Uniform Elgot Iteration in Foundations. Sergey Goncharov |
| 2021 | Universal Algorithms for Clustering Problems. Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi |
| 2021 | Using a Geometric Lens to Find k Disjoint Shortest Paths. Matthias Bentert, André Nichterlein, Malte Renken, Philipp Zschoche |