======================================================== ICALP 2023 - Call for Participation ======================================================== The 50th EATCS International Colloquium on Automata, Languages, and Programming (ICALP) will take place in: Paderborn, Germany, on 10-14 July 2023. ICALP is the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS). As usual, ICALP will be preceded by a series of workshops, which will take place on July 10. The 2023 edition has the following features: - The conference is planned as a physical, in-person event. - This will be the 50th ICALP conference and some special events are planned. ======================================================== Important dates and information ======================================================== Conference website: https://icalp2023.cs.upb.de/ Twitter: @ICALPconf Early registration: May 15, 2023 by 23:59 CET Conference: July 10-14, 2023 (Workshops on July 10, 2023) ======================================================== Registration ======================================================== Please register here: https://icalp2023.cs.upb.de/registration/ On-site child care: Please contact noelle.maicher.hoff@upb.de of the Equality Office of Paderborn University as soon as possible. ======================================================== Invited Speakers ======================================================== Anna Karlin - University of Washington, USA Rasmus Kyng - ETH Zurich, Switzerland Rupak Majumdar - Max Planck Institute for Software Systems, Germany Thomas Vidick - California Institute of Technology, USA, and Weizmann Institute of Science, Israel James Worrell - University of Oxford, UK ======================================================== Awards ======================================================== During the conference, the following awards will be given: – the EATCS award (https://eatcs.org/index.php/eatcs-award), - the Church award (https://eatcs.org/index.php/church-award) – the Presburger award (https://eatcs.org/index.php/presburger), – the EATCS distinguished dissertation award (https://eatcs.org/index.php/dissertation-award), – the best papers for Track A and Track B, – the best student papers for Track A and Track B (see submission guidelines). ========================================================= Special 50th ICALP session ========================================================= Invited talks: Kurt Mehlhorn (MPI für Informatik, Saarland Informatics Campus) Thomas Henzinger (IST Austria) ========================================================= Workshops ========================================================= See https://icalp2023.cs.upb.de/workshops/ for more information. - Combinatorial Reconfiguration - Graph Width Parameters: from Structure to Algorithms (GWP 2023) - Algorithmic Aspects of Temporal Graphs VI - Adjoint Homomorphism Counting Workshop (ad hoc) - Congestion Games - Workshop On Reachability, Recurrences, and Loops '23 (WORReLL'23) - Workshop on Recent Trends in Online Algorithms - Quantum Computing with Qiskit, and why Classical Algorithms still matter! - Algebraic Complexity Theory - Computer Science for CONTINUOUS Data ============= Accepted papers ============= ////////////////////// TRACK A ////////////////////// Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi and Kewen Wu. On Differentially Private Counting on Trees Leslie Ann Goldberg and Marc Roth. Parameterised and Fine-grained Subgraph Counting, modulo 2 Michał Wlodarczyk. Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth Laure Morelle, Ignasi Sau, Giannos Stamoulis and Dimitrios M. Thilikos. Faster parameterized algorithms for modification problems to minor-closed classes Sanjeev Khanna, Yu Chen and Zihan Tan. Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics Noam Touitou. Frameworks for Nonclairvoyant Network Design with Deadlines or Delay Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shunichi Maezawa, Yuta Nozaki, Yoshio Okamoto and Kenta Ozeki. Rerouting Planar Curves and Disjoint Paths Honghao Fu, Daochen Wang and Qi Zhao. Parallel self-testing of EPR pairs under computational assumptions Shi Li. Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems Shyan Akmal and Ce Jin. An Efficient Algorithm for All-Pairs Bounded Edge Connectivity Benjamin Aram Berendsohn, Ishay Golinsky, Haim Kaplan and Laszlo Kozma. Fast approximation of search trees on trees with centroid trees Ishan Bansal, Joe Cheriyan, Logan Grout and Sharat Ibrahimpur. Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions Hadley Black, Iden Kalemaj and Sofya Raskhodnikova. Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing Claire Mathieu and Hang Zhou. A Tight $(1.5+\epsilon)$-Approximation for Unsplittable Capacitated Vehicle Routing on Trees Sixue Liu, Zhao Song, Hengjie Zhang, Lichen Zhang and Tianyi Zhou. Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching Yanlin Chen and Ronald de Wolf. Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints Spencer Compton, Slobodan Mitrović and Ronitt Rubinfeld. New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling Tatsuya Terao. Faster Matroid Partition Algorithms David Harris and Vladimir Kolmogorov. Parameter estimation for Gibbs distributions Eric Rivals, Michelle Sweering and Pengfei Wang. Convergence of the number of period sets in strings David E. Roberson and Tim Seppelt. Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability Tobias Friedrich, Andreas Göbel, Maximilian Katzmann and Leon Schiller. Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs Konstantina Mellou, Marco Molinaro and Rudy Zhou. Online Demand Scheduling with Failovers David Eppstein and Daniel Frishberg. Improved mixing for the convex polygon triangulation flip walk Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-Ichi Maezawa, Yuta Nozaki and Yoshio Okamoto. Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra Rajarshi Bhattacharjee, Gregory Dexter, Petros Drineas, Cameron Musco and Archan Ray. Sublinear Time Eigenvalue Approximation via Random Sampling Lijie Chen, Xin Lyu, Avishay Tal and Hongxun Wu. New PRGs for Unbounded-width/Adaptive-order Read-once Branching Programs Petr Hlineny and Jan Jedelský. Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar Yann Disser, Max Klimm, Kevin Schewior and David Weckbecker. Incremental Maximization via Continuization Mohit Garg, Felix Hommelsheim and Nicole Megow. Matching Augmentation via Simultaneous Contractions Manuel Cáceres. Minimum Chain Cover in Almost Linear Time Zachary Friggstad and Ramin Mousavi. An $O(\log k)$-Approximation for Directed Steiner Tree in Planar Graphs Shu Liu, Chaoping Xing and Chen Yuan. List Decoding of Rank-Metric Codes with Row-to-Column Ratio Bigger Than 1/2 Yossi Azar and Danny Vainstein. Multi Layer Peeling for Linear Arrangement and Hierarchical Clustering Daniel Hader and Matthew Patitz. The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Cross-Model Simulation in Tile-Based Self-Assembly Hans L. Bodlaender, Carla Groenland and Michał Pilipczuk. Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters Ishan Agarwal and Richard Cole. Stable Matching: Choosing Which Proposals to Make Ruizhe Zhang and Xinzhi Zhang. A Hyperbolic Extension of Kadison-Singer Type Results Fedor Fomin, Petr Golovach, Danil Sagunov and Kirill Simonov. Approximating Long Cycle Above Dirac’s Guarantee Michael Whitmeyer and Siddharth Iyer. Searching for Regularity in Bounded Functions Vaishali Surianarayanan, Daniel Lokshtanov and Saket Saurabh. Breaking the All Subsets Barrier for Min $k$-Cut Magdalen Dobson and Guy Blelloch. The Geometry of Tree-Based Sorting Thiago Bergamaschi. Improved Product-state Approximation Algorithms for Quantum Local Hamiltonians Shaddin Dughmi, Yusuf Hakan Kalaycı and Neel Patel. On Sparsification of Stochastic Packing Problems Siu-Wing Cheng and Haoqiang Huang. Approximate Nearest Neighbor for Polygonal Curves under Frechet Distance Gramoz Goranci and Monika Henzinger. Efficient Data Structures for Incremental Exact and Approximate Maximum Flow Shimon Kogan and Merav Parter. New Additive Emulators Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann and Martin Schirneck. Fault-Tolerant ST-Diameter Oracles Michal Feldman, Federico Fusco, Stefano Leonardi, Simon Mauras and Rebecca Reiffenhäuser. Truthful Matching with Online Items and Offline Agents Ilan Cohen and Debmalya Panigrahi. A General Framework for Learning-Augmented Online Allocation Fedor Fomin, Petr Golovach, Ignasi Sau, Giannos Stamoulis and Dimitrios M. Thilikos. Compound Logics for Modification Problems Anders Aamand, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis, Peter Rasmussen and Mikkel Thorup. Optimal Decremental Connectivity in Non-Sparse Graphs Dana Ron and Omer Cohen Sidon. Sample-based distance-approximation for subsequence-freeness Siddharth Barman and Pooja Kulkarni. Approximation Algorithms for Envy-Free Cake Division with Connected Pieces Kazusato Oko, Shinsaku Sakaue and Shin-ichi Tanigawa. Nearly Tight Spectral Sparsification of Directed Hypergraphs Daniel Agassy, Dani Dorfman and Haim Kaplan. Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player Jakob Bæk Tejs Houen and Mikkel Thorup. A Sparse Johnson-Lindenstrauss Transform using Fast Hashing Pan Peng and Yuyang Wang. An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs Qin Minglong and Penghui Yao. Decidability of fully quantum nonlocal games with noisy maximally entangled states Louis Esperet, Nathaniel Harms and Viktor Zamaraev. Optimal Adjacency Labels for Subgraphs of Cartesian Products Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi and Jukka Suomela. Locality in online, dynamic, sequential, and distributed graph algorithms Dmitry Paramonov, Gillat Kol, Klim Efremenko and Raghuvansh R. Saxena. Protecting Single-Hop Radio Networks from Message Drops Alexandru Gheorghiu, Tony Metger and Alexander Poremba. Quantum cryptography with classical communication - Parallel remote state preparation for copy-protection, verification, and more Andrzej Dorobisz and Jakub Kozik. Local Computation Algorithms for Hypergraph Coloring - following Beck's approach Ishay Haviv. On Finding Constrained Independent Sets in Cycles Petra Berenbrink, Lukas Hintze, Hamed Hosseinpour, Dominik Kaaser and Malin Rau. Dynamic Averaging Load Balancing on Arbitrary Graphs Ilan Doron, Ariel Kulik and Hadas Shachnai. An EPTAS for Budgeted Matching and Budgeted Matroid Intersection Karthik Murali and Therese Biedl. On computing the vertex connectivity of 1-plane graphs Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan and Shay Sapir. Lower Bounds for Pseudo-Deterministic Counting in a Stream Charilaos Efthymiou and Weiming Feng. On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n,d/n) Jun-Ting Hsieh and Pravesh K Kothari. Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm Or Zamir. The wrong direction of Jensen’s inequality is algorithmically right Talya Eden, Sofya Raskhodnikova, Quanquan C. Liu and Adam Smith. Triangle Counting with Local Edge Differential Privacy Lukas Drexler, Jan Eube, Kelin Luo, Heiko Röglin, Melanie Schmidt and Julian Wargalla. Connected k-Center and k-Diameter Clustering Dylan Hyatt-Denesik, Afrouz Ameli and Laura Sanita. Finding Almost Tight Witness Trees Adam Karczmarz and Piotr Sankowski. Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs Xiantao Li and Chunhao Wang. Simulating Markovian open quantum systems using higher-order series expansion Monika Henzinger, Paul Liu, Jan Vondrák and Da Wei Zheng. Faster submodular maximization for several classes of matroids Miguel Bosch Calvo, Fabrizio Grandoni and Afrouz Jabal Ameli. A 4/3 Approximation for 2-Vertex-Connectivity Paul Beame and Niels Kornerup. Cumulative Memory Lower Bounds for Randomized and Quantum Computation Sudatta Bhattacharya and Michal Koucky. Streaming $k$-edit approximate pattern matching via string decomposition Robert Ferens and Marek Szykuła. Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds David Stalfa, Rajmohan Rajaraman and Sheng Yang. Scheduling under Non-Uniform Job and Machine Delays Konstantinos Zampetakis and Charilaos Efthymiou. Broadcasting with Random Matrices Chandra Chekuri and Rhea Jain. Approximation Algorithms for Network Design in Non-Uniform Fault Models Jin-Yi Cai and Ben Young. Planar \#CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint Andrej Bogdanov and Alon Rosen. Nondeterministic Refutations for Nearest Boolean Vector Amir Azarmehr and Soheil Behnezhad. Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation Timothy M. Chan, Qizheng He and Yuancheng Yu. On the Fine-Grained Complexity of Small-Size Geometric Set Cover and Discrete $k$-Center for Small $k$ Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami and Kaave Hosseini. Online Learning and Disambiguations of Partial Concept Classes Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee and Joshua Wang. Efficient Caching with Reserves via Marking Jun-Ting Hsieh, Pravesh Kothari, Aaron Potechin and Jeff Xu. Ellipsoid Fitting Up to a Constant Ryu Hayakawa, Jordi Weggemans, Tomoyuki Morimae, Chris Cade, Marten Folkertsma, Sevag Gharibian and Francois Le Gall. Improved Hardness Results for the Guided Local Hamiltonian Problem Mohak Goyal, Sukolsak Sakshuwong, Sahasrajit Sarmasarkar and Ashish Goel. Low Sample Complexity Participatory Budgeting Yi-Jun Chang. Ortho-radial Drawing in Near-linear Time Kuan Cheng, Zhengzhong Jin, Xin Li, Zhide Wei and Yu Zheng. Linear Insertion Deletion Codes in the High-Noise and High-Rate Regimes Rotem Oshman and Tal Roth. The Communication Complexity of Set Intersection under Product Distributions Thomas Sauerwald, He Sun and Danny Vagnozzi. The Support of Open versus Closed Random Walks Sam Coy, Artur Czumaj, Peter Davies and Gopinath Mishra. Optimal (degree+1)-Coloring in Congested Clique Ittai Rubinstein. Average-Case to (shifted) Worst-Case Reduction for the Trace Reconstruction Problem Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha and Bhargav Thankey. Low-depth arithmetic circuit lower bounds: Bypassing set-multilinearization Nicolas Resch, Chen Yuan and Yihan Zhang. Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery Peyman Afshani, Pingan Cheng, Aniket Basu Roy and Zhewei Wei. On Range Summary Queries ////////////////////// TRACK B ////////////////////// Frits Vaandrager and Thorsten Wißmann. Action Codes Michael Lampis. First Order Logic on Pathwidth Revisited Again Patricia Bouyer, Nathanaël Fijalkow, Mickael Randour and Pierre Vandenhove. How to Play Optimally for Regular Objectives? Bader Abu Radi and Orna Kupferman. On Semantically-Deterministic Automata Manuel Bodirsky and Simon Knäuer. Network Satisfaction Problems Solved by k-Consistency Ruiwen Dong. The Identity Problem in $\mathbb{Z} \wr \mathbb{Z}$ is decidable Michael Blondin and François Ladouceur. Population Protocols with Unordered Data Markus Lohrey and Andreas Rosowski. On the complexity of diameter and related problems in permutation groups Moritz Lichter. Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting Wojciech Rozowski, Tobias Kappé, Dexter Kozen, Todd Schmid and Alexandra Silva. Probabilistic Guarded KAT Modulo Bisimilarity: Completeness and Complexity Bartosz Bednarczyk, Ian Pratt-Hartmann and Daumantas Kojelis. On the of Limits of Decision: the Adjacent Fragment of First-Order Logic Mikołaj Bojańczyk and Lê Thành Dũng Nguyễn. Algebraic Recognition of Regular Functions Jan Dreier, Nikolas Mählmann, Sebastian Siebertz and Szymon Toruńczyk. Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes Antonio Casares and Pierre Ohlmann. Characterising memory in infinite games Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski and Szymon Toruńczyk. Canonical decompositions in monadically stable and bounded shrubdepth graph classes Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokołowski and Szymon Toruńczyk. Flipper games for monadically stable graph classes Titouan Carette, Etienne Moutot, Thomas Perez and Renaud Vilmart. Compositionality of planar perfect matchings, a universal and complete fragment of ZW-calculus Harry Vinall-Smeeth and Christoph Berkholz. A dichotomy for succinct representations of homomorphisms Javier Esparza and Vincent Grande. Black-box Testing Liveness Properties of Partially Observable Stochastic Systems Thomas Henzinger, Pavol Kebis, Nicolas Mazzocchi and N. Ege Saraç. Regular Methods for Operator Precedence Languages George Kenison, Joris Nieuwveld, Joël Ouaknine and James Worrell. Positivity Problems for Reversible Linear Recurrence Sequences Olivier Carton, Gaëtan Douéneau-Tabot, Emmanuel Filiot and Sarah Winter. Deterministic regular functions of infinite words Fabian Birkmann, Stefan Milius and Henning Urbat. Nominal Topology for Data Languages Marvin Künnemann, Filip Mazowiecki, Lia Schütze, Henry Sinclair-Banks and Karol Węgrzycki. Coverability in VASS Revisited: Improving Rackoff’s Bound to Obtain Conditional Optimality Austen Z. Fan, Paraschos Koutris and Hangdong Zhao. The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar and Kuldeep Meel. Approximate Model Counting: Is SAT Oracle More Powerful than NP Oracle? Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis and Aris Papadopoulos. Monadic NIP in monotone classes of relational structures Michael Benedikt, Dmitry Chistikov and Alessio Mansutti. The complexity of Presburger arithmetic with power or powers Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan Thinniyam Srinivasan and Georg Zetzsche. Checking Refinement of Asynchronous Programs against Context-Free Specifications The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Is e buidheann carthannais a th’ ann an Oilthigh Dhùn Èideann, clàraichte an Alba, àireamh clàraidh SC005336.