Preface (47th International Colloquium on Automata, Languages, and Programming)

Preface This volume contains the papers presented at the 47th International Colloquium on Auto- mata, Languages and Programming (ICALP 2020), held virtually, hosted by the Saarland Informatics Campus in Saarbrücken, Germany, during July 8–11, 2020. ICALP is a series of annual conferences of the European Association for Theoretical Computer Science (EATCS), which first took place in 1972. ICALP 2020 was co-located with the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2020). The conference was affected by the outbreak of COVID-19, which had an enormous impact across the world and the ICALP community was no exception. The original plan had been to hold ICALP 2020, in conjunction with LICS 2020 at Peking University in Beijing, China. When it became clear that this would not be possible due to travel restrictions that were being imposed, and after intensive discussions between the ICALP and LICS steering committees, together with the PC chairs and conference chairs, it was decided to re-locate the conferences to Saarbrücken. Eventually, keeping the safety, health and well-being of ICALP participants as a top priority, it was decided to hold ICALP 2020 entirely online. We are very grateful to the organizers in Beijing and Saarbrücken and to all members of the theoretical computer science community for their flexibility and adaptability in this difficult situation. This first online ICALP is an experiment forced on us by the situation and will no doubt offer many lessons for the future. For 15 years, the ICALP conference ran with three tracks. This has been the subject of much deliberation in the ICALP community in recent years and the decision was taken, with ICALP 2020, to return to a two-track format. Topics previously included in Track C have been incorporated into Track A. This year, the ICALP program consisted of the following two tracks: Track A: Algorithms, Complexity, and Games. Track B: Logic, Semantics, Automata and Theory of Programming. In response to the call for papers, a total of 470 submissions were received: 347 for Track A and 123 for Track B. Each submission was assigned to at least three Program Committee members, aided by 857 external subreviewers. The committees decided to accept 138 papers for inclusion in the scientific program: 102 papers for Track A and 36 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: Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Minimum cut in O(m log2 n) time. Track B: David Barozzini, Lorenzo Clemente, Thomas Colcombet and Paweł Parys. Cost automata, safe schemes, and downward closures. The best student paper awards, for papers that are solely authored by students, were given to the following papers: Track A: Aditya Potukuchi. A spectral bound on hypergraph discrepancy. Track B: Erik Paul. Finite sequentiality of finitely ambiguous max-plus tree automata. Apart from the contributed talks, ICALP 2020 included invited presentations by Stefan Kiefer (Oxford University), Robert Krauthgamer (The Weizmann Institute of Science) and Virginia Vassilevska Williams (MIT). There were also two invited talks joint with LICS 2020: by Jerôme Leroux (Bordeaux University) and Andrew Chi-Chih Yao (Tsinghua University). This volume contains all the contributed papers presented at the conference, papers that accompany the invited talks of Andrew Yao and Stefan Kiefer, and an abstract of the invited presentation of Robert Krauthgamer. The program of ICALP 2020 also included presentations of the EATCS Award 2020 to Mihalis Yannakakis, the Gödel Prize 2020 to Robin A. Moser and Gábor Tardos, the Presburger Award 2020 to Dmitriy Zhuk, and the EATCS Distinguished Dissertation Awards to Josh Alman, Sándor Kisfaludi-Bak, and Jakub Tarnawski. The following workshops were held as satellite events of ICALP and LICS 2020 on July 6–7, 2020: Algorithmic Aspects of Temporal Graphs (AATG), Fine-Grained and Parameterized Approximation Algorithms (FG-PAAW), Verification of Infinite-State Systems (INFINITY), Logic and Computational Complexity Workshop (LCC 2020), Logic Mentoring Workshop (LMW), Programming Research in Mainstream Languages (PRiML). 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 Co-Chairs Xiaotie Deng and Holger Hermanns and all the support staff of the Organizing Committee for organizing ICALP 2020: to our colleagues in Peking University, led by Xiaotie Deng, for their organizational efforts in the originally planned location in Beijing, and to the colleagues from Saarbrücken, led by Holger Hermanns, who generously accepted the challenging task of organizing the conference at short notice, and who were then ready to run the conference online. Finally, we are grateful to all members of the TCS community who offered their support in this difficult situation. We wish to thank CPEC — Center for Perspicuous Computing and Saarland University in Saarbrücken for their generous support for the conference. We would like to thank Anca Muscholl, the Chair of the ICALP Steering Committee, for her continuous support and Paul Spirakis, the president of EATCS, for his generous advice on the organization of the conference. July 2020 Artur Czumaj, Anuj Dawar, Emanuela Merelli