Preface

This volume contains the papers presented at the 48th International Colloquium on Automata, Languages and Programming (ICALP 2021), held virtually, hosted by the University of Glasgow, UK, during July 12–16, 2021. ICALP is a series of annual conferences of the European Association for Theoretical Computer Science (EATCS), which first took place in 1972. This year, the ICALP program consisted of two tracks: Track A: Algorithms, Complexity, and Games Track B: Automata, Logic, Semantics, and Theory of Programming In response to the call for papers, a total of 362 submissions were received: 261 for Track A and 101 for Track B. Each submission was assigned to at least three Program Committee members, aided by 761 external subreviewers. The committees decided to accept 137 papers for inclusion in the scientific program: 108 papers for Track A and 29 for Track B. The selection was made by the Program Committees based on originality, quality, and relevance to theoretical computer science. The quality of the manuscripts was very high indeed, and many deserving papers could not be selected. The EATCS sponsored awards for both a best paper and a best student paper in each of the two tracks, selected by the Program Committees. The best paper awards were given to the following papers: Track A: Sayan Bhattacharya and Peter Kiss. Deterministic Rounding of Dynamic Frac- tional Matchings. Track B: Antoine Amarilli, Louis Jachiet and Charles Paperman. Dynamic Membership for Regular Languages. The best student paper awards, for papers that are solely authored by students, were given to the following paper: Track A: Or Zamir. Breaking the 2n barrier for 5-coloring and 6-coloring. Track B: none. Apart from the contributed talks, ICALP 2021 included invited presentations by Christel Baier (Technical University of Dresden), Andrei Bulatov (Simon Fraser University, Canada), Keren Censor-Hillel (Technion, Israel), Toniann Pitassi (University of Toronto, Canada), Adi Shamir (Weizmann Institute of Science, Israel), David Woodruff (Carnegie Mellon University, USA). This volume contains all the contributed papers presented at the conference, papers that accompany the invited talks of Christel Baier, Andrei Bulatov, Keren Censor-Hillel, Adi Shamir, David Woodruff, and an abstract of the invited presentation of Toniann Pitassi. The program of ICALP 2021 also included presentations of the EATCS Award 2021 to Toniann Pitassi, the Presburger Award 2021 to Shayan Oveis Gharan, the EATCS Distinguished Dissertation Awards to Talya Eden, Marie Fortin, Vera Traub, and the induction of new EATCS Fellows Luca Aceto, Rajeev Alur, Samir Khuller, David Peleg, Davide Sangiorgi, Saket Saurabh. The following workshops were held as satellite events of ICALP 2021 on July 12, 2021: Algorithmic Aspects of Temporal Graphs IV (AATG) Verification of Session Types (VEST) Programming Research in Mainstream Languages (PRiML) Graph Width Parameters: from Structure to Algorithms (GWP) Combinatorial Reconfiguration Formal methods education on-line: Tips, Tricks and Tools Flavours of Uncertainty in Verification, Planning and Optimization (FUNCTION) We wish to thank all authors who submitted extended abstracts for consideration, the Program Committees for their scholarly effort, and all the referees who assisted the Program Committees in the evaluation process. We are also grateful to the Conference General Chair, Simon Gay, and his colleagues from the School of Computing Science, University of Glasgow, for organizing ICALP 2021, and to the Scottish Informatics and Computer Science Alliance (SICSA) for sponsoring participation by PhD students from Scotland. We would like to thank Anca Muscholl, the Chair of the ICALP Steering Committee, for her continuous support and Artur Czumaj, the president of EATCS, for his generous advice on the organization of the conference. July 2021 Nikhil Bansal Emanuela Merelli James Worrel