Accepted papers

Proceedings

 The ICALP 2021 Proceedings have now been published in the LIPIcs series. 

Best paper awards

Track A

Sayan Bhattacharya and Peter Kiss. Deterministic Rounding of Dynamic Fractional Matchings

Track B

Antoine Amarilli, Louis Jachiet and Charles Paperman. Dynamic Membership for Regular Languages

 

Best student paper awards (for papers written solely by students)

Track A

Or Zamir. Breaking the 2n barrier for 5-coloring and 6-coloring

Track B

None

 

Track A

 

  1. Tianyi Zhang. Deterministic Maximum Flows in Simple Graphs
  2. Markus Anders, Pascal Schweitzer and Florian Wetzels. Comparative Design-Choice Analysis of Color Refinement Algorithms Beyond the Worst Case
  3. Gianlorenzo D’Angelo, Debashmita Poddar and Cosimo Vinci. Improved Approximation Factor for Adaptive Influence Maximization via Simple Greedy Strategies
  4. Michael Lampis. Minimum Stable Cut and Treewidth
  5. Anupam Gupta, Benjamin Moseley and Rudy Zhou. Structural Iterative Rounding for Generalized k-Median Problems
  6. Bernhard Haeupler, David Hershkowitz and David Wajc. Near-Optimal Schedules for Simultaneous Multicasts
  7. Édouard Bonnet. 4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time $n^{4/3}$
  8. Yong Gu and Hanlin Ren. Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time
  9. Moritz Buchem, Lars Rohwedder, Tjark Vredeveld and Andreas Wiese. Additive Approximation Schemes for Load Balancing Problems
  10. Mathieu Mari, Chien-Chung Huang, Claire Mathieu and Jens Vygen. Approximating maximum integral multiflows on bounded genus graphs
  11. Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter and Ronald de Wolf. Quantum algorithms for matrix scaling and matrix balancing
  12. Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigant. Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
  13. Shyan Akmal and Virginia Williams. Improved Approximation for Longest Common Subsequence over Small Alphabets
  14. Nick Gravin, Zhihao Gavin Tang and Kangning Wang. Online Stochastic Matching with Edge Arrivals
  15. Izhar Oppenhein and Tali Kaufman. Coboundary and cosystolic expansion from strong symmetry
  16. Karl Bringmann and Vasileios Nakos. Fast n-fold Boolean Convolution via Additive Combinatorics
  17. Keren Censor-Hillel, Noa Marelly, Roy Schwartz and Tigran Tonoyan. Fault Tolerant Max-Cut
  18. Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel and Andrzej Pelc. Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs
  19. Telikepalli Kavitha. Maximum Matchings and Popularity
  20. Jan Böker. Graph Similarity and Homomorphism Densities
  21. Enoch Peserico and Michele Scquizzato. Matching on the line admits no $o(\sqrt{\log n})$-competitive algorithm
  22. Ewan Davies and Will Perkins. Approximately counting independent sets of a given size
  23. Andreas Björklund and Petteri Kaski. Counting Short Vector Pairs by Inner Product and Relations to the Permanent
  24. Massimo Cairo, Romeo Rizzi, Alexandru I. Tomescu and Elia Carlo Zirondelli. Genome assembly, from practice to theory: safe, complete and linear-time
  25. Matthias Bentert, André Nichterlein, Malte Renken and Philipp Zschoche. Using A Geometric Lens to Find k Disjoint Shortest Paths
  26. Emanuele Viola. Fourier conjectures, correlation bounds, and Majority
  27. Markus Anders and Pascal Schweitzer. Search Problems in Trees with Symmetries: near optimal traversal strategies for individualization-refinement algorithms
  28. Ilan Newman and Nithin Varma. New Sublinear Algorithms and Lower Bounds for LIS Estimation
  29. Etienne Bamas, Paritosh Garg and Lars Rohwedder. The Submodular Santa Claus Problem in the Restricted Assignment Case
  30. Maximilian Probst Gutenberg, Viktor Fredslund-Hansen, Jacob Evald and Christian Wulff-Nilsen. Decremental APSP in Directed Graphs Versus an Adaptive Adversary
  31. Tuukka Korhonen. Lower Bounds on Dynamic Programming for Maximum Weight Independent Set
  32. Karl Bringmann and Debarati Das. A Near-Linear-Time n^0.4-Approximation for Longest Common Subsequence
  33. Mina Dalirrooyfard and Jenny Kaufmann. Approximation Algorithms for Min-Distance Problems in DAGs
  34. Jakub Kozik. Improving Gebauer’s construction of 3-chromatic hypergraphs with few edges
  35. Lijie Chen, Zhenjian Lu, Xin Lyu and Igor Oliveira. Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1
  36. Zhenjian Lu and Igor Oliveira. An Efficient Coding Theorem via Probabilistic Representations and its Applications
  37. Or Zamir. Breaking the 2^n barrier for 5-coloring and 6-coloring
  38. Yonatan Nakar and Dana Ron. Testing Dynamic Environments: Back to Basics
  39. Andrew Childs, Shih-Han Hung and Tongyang Li. Quantum query complexity with matrix-vector products
  40. Benjamin Moseley, Kirk Pruhs, Alireza Samadian and Yuyan Wang. Relational Algorithms for k-means Clustering
  41. Hyejung Hailey Jee, Carlo Sparaciari, Omar Fawzi and Mario Berta. Quasi-polynomial time algorithms for quantum games in bounded dimension
  42. Yuzhou Gu, Adam Polak, Virginia Vassilevska Williams and Yinzhan Xu. Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
  43. Artur Czumaj, George Kontogeorgiou and Mike Paterson. Haystack Hunting Hints and Locker Room Communication
  44. Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri and Maryam Negahbani. Revisiting Priority k-Center: Fairness and Outliers
  45. Arun Ganesh, Bruce Maggs and Debmalya Panigrahi. Universal Algorithms for Clustering Problems
  46. Timothy M. Chan, Virginia Vassilevska Williams and Yinzhan Xu. Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths
  47. Andrei-Alexandru Graur and Noga Alon. Efficient Splitting of Necklaces
  48. Bernd Gärtner, Sebastian Haslebacher and Hung P. Hoang. A subexponential algorithm for ARRIVAL
  49. Sayan Bandyapadhyay, Fedor Fomin and Kirill Simonov. On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications
  50. Ran Ben Basat, Michael Mitzenmacher and Shay Vargaftik. How to Send a Real Number Using a Single Bit (and Some Shared Randomness)
  51. Antonios Antoniadis, Matthias Englert, Nicolaos Matsakis and Pavel Veselý. Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop
  52. Andrej Bogdanov and Gautam Prakriya. Direct Sum and Partitionability Testing over General Groups
  53. Jonas Ellert and Johannes Fischer. Linear Time Runs over General Ordered Alphabets
  54. Amir Abboud and Virginia Vassilevska Williams. Fine-Grained Hardness for Edit Distance to a Fixed Sequence
  55. Reut Levi. Testing Triangle Freeness in the General Model in Graphs with Arboricity $O(\sqrt{n})$
  56. Theo McKenzie and Sidhanth Mohanty. High-girth near-Ramanujan graphs with lossy vertex expansion
  57. George Christodoulou, Elias Koutsoupias and Annamaria Kovacs. Truthful allocation in graphs and hypergraphs
  58. Adam Polak, Lars Rohwedder and Karol Węgrzycki. Knapsack and Subset Sum with Small Items
  59. Tobias Friedrich, Andreas Göbel, Martin S. Krejca and Marcus Pappik. A spectral independence view on hard spheres via block dynamics
  60. Zachary Friggstad and Chaitanya Swamy. Constant-Factor Approximation to Deadline TSP and Related Problems in (almost) Quasi-Polytime
  61. Michal Koucký and Karel Král. Sorting Short Integers
  62. Kevin Pratt and Cornelius Brand. Parameterized Applications of Symbolic Differentiation of (Totally) Multilinear Polynomials
  63. Joakim Blikstad. Breaking O(nr) for Matroid Intersection
  64. Marc Roth, Johannes Schmitt and Philip Wellnitz. Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders
  65. Panagiotis Charalampopoulos, Shay Mozes, Pawel Gawrychowski and Oren Weimann. An Almost Optimal Edit Distance Oracle
  66. J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel and Tobias Friedrich. On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order
  67. Pankaj K. Agarwal and Alex Steiger. An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D
  68. Uma Girish, Ran Raz and Wei Zhan. Quantum Logspace Algorithm for Powering Matrices with Bounded Norm
  69. Chandra Chekuri and Kent Quanrud. Faster Algorithms for Rooted Connectivity in Directed Graphs
  70. Shyan Akmal and Ce Jin. Faster Algorithms for Bounded Tree Edit Distance
  71. Seth Pettie and Longhui Yin. The Structure of Minimum Vertex Cuts
  72. Deeksha Adil, Brian Bullins, Rasmus Kyng and Sushant Sachdeva. Almost-linear Time Weighted $\ell_p$-norm Solvers in Slightly Dense Graphs via Sparsification
  73. Nicolas Rivera, Thomas Sauerwald and John Sylvester. Multiple Random Walks on Graphs: Mixing Few to Cover Many
  74. Karl Bringmann and Jasper Slusallek. Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal
  75. Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada and Birgit Vogtenhuber. Crossing-Optimal Extension of Simple Drawings
  76. Dániel Marx, Govind S. Sankar and Philipp Schepper. Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
  77. Eike Neumann, Joel Ouaknine and James Worrell. Decision problems for second-order holonomic recurrences
  78. David P. Woodruff and Samson Zhou. Separations for Estimating Large Frequency Moments on Data Streams
  79. Marcin Bienkowski, Artur Kraska and Hsiang-Hsuan Liu. Traveling Repairperson, Unrelated Machines, and Other Stories About Average Completion Times
  80. Adam Karczmarz. Fully Dynamic Algorithms for Minimum Weight Cycle and Related Problems
  81. Dimitris Achlioptas and Kostas Zampetakis. Local Approximations of the Independent Set Polynomial
  82. Pankaj Agarwal, Xiao Hu, Stavros Sintos and Jun Yang. Dynamic Enumeration of Similarity Joins
  83. Maria Hartmann, László Kozma, Corwin Sinnamon and Robert Tarjan. Analysis of Smooth Heaps
  84. Sayan Bhattacharya and Peter Kiss. Deterministic Rounding of Dynamic Fractional Matchings
  85. Yu Chen, Sanjeev Khanna and Ansh Nagda. Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries
  86. Joshua Brakensiek, Venkatesan Guruswami and Sai Sandeep. Conditional Dichotomy of Boolean Ordered Promise CSPs
  87. Christian Coester and Elias Koutsoupias. Towards the k-server conjecture: A unifying potential, pushing the frontier to the circle
  88. Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova. Lifting for constant-depth circuits and applications to MCSP
  89. Ruoxu Cen, Yu Cheng, Debmalya Panigrahi and Kevin Sun. Sparsification of Directed Graphs via Cut Balance
  90. Sepehr Assadi and Soheil Behnezhad. Beating Two-Thirds For Random-Order Streaming Matching
  91. Ojas Parekh and Kevin Thompson. Application of the Level-2 Quantum Lasserre Hierarchy in Quantum Approximation Algorithms
  92. Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song and Huacheng Yu. Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs
  93. Kuan Cheng, Alireza Farhadi, Mohammadtaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin and Yu Zheng. Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence
  94. Dingyu Wang, Seth Pettie and Longhui Yin. Non-Mergeable Sketching for Cardinality Estimation
  95. Guy Blanc, Jane Lange and Li-Yang Tan. Learning stochastic decision trees
  96. Amin Saberi and David Wajc. The Greedy Algorithm is not Optimal for On-Line Edge Coloring
  97. Mitali Bafna and Nikhil Vyas. Optimal Fine-grained Hardness of Approximation of Linear Equations
  98. Chandra Chekuri and Kent Quanrud. Isolating Cuts, (Bi-)Submodularity, and Faster Algorithms for Connectivity
  99. Arnab Ganguly, Dhrumil Patel, Rahul Shah and Sharma Thankachan. LF Successor: Compact Space Indexing for Order-Isomorphic Pattern Matching
  100. Takaaki Nishimoto and Yasuo Tabei. Optimal-Time Queries on BWT-runs Compressed Indexes
  101. Vahid Reza Asadi and Igor Shinkar. Relaxed Locally Correctable Codes with Improved Parameters
  102. Eleni Batziou, Kristoffer Arnsfelt Hansen and Kasper Høgh. Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem
  103. Sharat Ibrahimpur and Chaitanya Swamy. Minimum-Norm Load Balancing is (almost) as Easy as Minimizing Makespan
  104. Stratis Skoulakis, Dimitris Fotakis, Panagiotis Kostopanagiotis, Georgios Piliouras and Vasileios Nakos. On the Approximability of Dynamic Min-Sum Set Cover
  105. Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu and Qianfan Zhang. Random Order Vertex Arrival Contention Resolution Schemes For Matching, With Applications
  106. Ken-Ichi Kawarabayashi, Bojan Mohar, Roman Nedela and Peter Zeman. Automorphisms and isomorphisms of maps in linear time
  107. Christoph Damerius, Dominik Kaaser, Peter Kling and Florian Schneider. On Greedily Packing Anchored Rectangles
  108. Adam Kurpisz, Aaron Potechin and Elias Wirth. SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization

 

Track B

 

  1. Alex Brandts and Stanislav Živný. Beyond PCSP(1-in-3,NAE)
  2. Pascal Vanier and Antonin Callard. Computational characterization of surface entropies for Z² subshifts of finite type
  3. Paweł Parys. Higher-Order Model Checking Step by Step
  4. Antoine Amarilli, Louis Jachiet and Charles Paperman. Dynamic Membership for Regular Languages
  5. Luca Ciccone and Luca Padovani. Inference Systems with Corules for Fair Subtyping and Liveness Properties of Binary Session Types
  6. Han Xu and Zhenjiang Hu. Analytical Differential Calculus with Integration
  7. Erich Grädel and Lovro Mrkonjic. Elementary equivalence versus isomorphism in semiring semantics
  8. Antonio Casares, Thomas Colcombet and Nathanaël Fijalkow. Optimal Transformations of Games and Automata using Muller Conditions
  9. Ian Pratt-Hartmann. Fluted Logic with Counting
  10. Lorenzo Clemente and Michał Skrzypczak. Deterministic and game separability for regular languages of infinite trees
  11. Gabriel Istrate, Cosmin Bonchis and Adrian Craciun. Kernelization, Proof Complexity and Social Choice
  12. Benjamin Monmege, Julie Parreaux and Pierre-Alain Reynier. Playing Stochastically in Weighted Timed Games to Emulate Memory
  13. Samson Abramsky and Luca Reggio. Arboreal Categories and Resources
  14. Krishnendu Chatterjee, Monika Henzinger, Sagar Kale and Alexander Svozil. Faster Algorithms for Bounded Liveness in Graphs and Game Graphs
  15. Thomas Colcombet and Arthur Jaquard. A Complexity Approach to Tree Algebras: the Bounded Case
  16. Wojciech Czerwinski, Antoine Mottet and Karin Quaas. New Techniques for Universality in Unambiguous Register Automata
  17. Lê Thành Dũng Nguyễn, Camille Noûs and Pierre Pradic. Comparison-free polyregular functions
  18. Gabriel Bathie and Tatiana Starikovskaya. Property testing of regular languages with applications to streaming property testing of visibly pushdown languages
  19. Antoine Mottet, Tomáš Nagy, Michael Pinsker and Michał Wrona. Smooth Approximations and Relational Width Collapses
  20. Dominik D. Freydenberger and Liat Peterfreund. The theory of concatenation over finite models
  21. Alexandre Goy, Daniela Petrisan and Marc Aiguier. Powerset-Like Monads Weakly Distribute over Themselves in Toposes and Compact Hausdorff Spaces
  22. Manuel Bodirsky, Simon Knäuer and Sebastian Rudolph. Datalog-Expressibility for Monadic and Guarded Second-Order Logic
  23. Paolo Baldan, Francesco Ranzato and Linpeng Zhang. A Rice’s Theorem for Abstract Semantics
  24. Wojciech Czerwiński, Sławomir Lasota and Łukasz Orlikowski. Improved lower bounds for reachability in vector addition systems
  25. Todd Schmid, Tobias Kappé, Dexter Kozen and Alexandra Silva. Guarded Kleene Algebra with Tests: Coequations, Coinduction, and Completeness
  26. Borja Balle, Clara Lacroce, Prakash Panangaden, Doina Precup and Guillaume Rabusseau. Optimal Spectral-Norm Approximate Minimization of Weighted Finite Automata
  27. Yangjia Li and Dominique Unruh. Quantum Relational Hoare Logic with Expectations
  28. Martin Grohe and Sandra Kiefer. Logarithmic Weisfeiler-Leman Identifies All Planar Graphs
  29. Sergey Goncharov. Uniform Elgot Iteration in Foundations