Highlights: - Due to multiple requests, the early registration deadline has been extended to May 18. - We recommend that participants make their hotel reservations as early as possible since Paris is an attractive destination for tourists during the summer. - The conference programme is now available. The 49th International Colloquium on Automata, Languages, and Programming (ICALP) will take place  ** in Paris, France, and online on 4-8 July 2022. ** The 2022 edition has the following special features: - The conference is hybrid. - This will be the 50th birthday of the conference and some special events are planned.  - The ICALP Extended Stay Support Scheme (IESSS) is here for helping the organisation of collaborations around the conference. 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 4. The 2022 edition will be also the occasion to celebrate the 50th anniversary of both EATCS and the first ICALP, which was first held in 1972 in Rocquencourt, in the Paris area. ============= Important dates and information ============= Website: https://icalp2022.irif.fr/ Early Registration: May 18 Conference: July 4-8, 2022 Workshops: July 4 ============= Registration ============= For registration, follow this link: https://icalp2022.irif.fr/?page_id=50 ============= Extended Stay Support Scheme (IESS) ============= For its 49th edition, the ICALP conference offers to its attendees an Extended Stay Support Scheme (IESSS) aiming at enhancing scientific collaborations and diminishing the carbon footprint of scientific research activities. ICALP 2022 attendees are encouraged to combine their visit to Paris with collaborations with local researchers. This support scheme is primarily intended for participants travelling long distances and must be combined with an attendance to ICALP. Upon acceptation, research institutes involved in this mechanism will cover standard expenses (accommodation and traveling fees, plane excluded) and  will provide material support for research activities. See https://icalp2022.irif.fr/?page_id=50 for more information. ============= Invited Speakers ============= Albert Atserias, Universitat Politècnica de Catalunya Constantinos Daskalakis, MIT Leslie Ann Goldberg, Oxford University Madhu Sudan, Harvard Stéphan Thomassé, ENS Lyon Santosh Vempala, Georgia Tech ============= Awards ============= During the conference, the following awards will be given: - the EATCS award (https://eatcs.org/index.php/eatcs-award), - the Gödel prize (https://eatcs.org/index.php/goedel-prize), - 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. ============= Accepted papers ============= See https://icalp2022.irif.fr/?page_id=85  ============= Workshops ============= See https://icalp2022.irif.fr/?page_id=46 for more information. - Parameterized Approximation Algorithms Workshop - Combinatorial Reconfiguration - Recent Advances on Total Search Problems - Algorithmic Aspects of Temporal Graphs V - Trends in Arithmetic Theories - Structure Meets Power 2022 - Straight-Line Programs, Word Equations and their Interplay - Graph Width Parameters: from Structure to Algorithms ============= Programme ============= See https://icalp2022.irif.fr/wp-content/uploads/2022/05/icalp2022programme.pdf or below. # Tuesday 8h30-9h30. Invited speaker 1  * Santosh Vempala    _The Manifold Joys of Sampling in High Dimension_ # Tuesday 10h00-12h05. Paper session 1 ## Graph algorithms  * Sebastian Forster, and Tijn de Vos    _Faster Cut Sparsification of Weighted Graphs_  * Tianyi Zhang    _Faster Cut-Equivalent Trees in Simple Graphs_  * Mingyang Deng, Yael Kirkpatrick, Victor Rong, Virginia Vassilevska Williams, and Ziqian Zhong    _New Additive Approximations for Shortest Paths and Cycles_  * Caroline Brosse, Vincent Limouzy, and Arnaud Mary    _Polynomial Delay Algorithm for Minimal Chordal Completions_  * Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, and Marek Sokołowski    _Max Weight Independent Set in Fraphs with no Long Claws: An Analog of the Gyárfás' Path Argument_ ## Games and verification  * Léonard Brice, Jean-Francois Raskin, and Marie Van Den Bogaard    _The complexity of SPEs in Mean-payoff Games_  * Benjamin Bordais, Damien Busatto-Gaston, Shibashis Guha, and Jean-Francois Raskin    _Strategy Synthesis for Global Window PCTL_  * Hugo Gimbert, Corto Mascle, Anca Muscholl, and Igor Walukiewicz    _Distributed Controller Synthesis for Deadlock Avoidance_  * Xavier Allamigeon, Stephane Gaubert, Ricardo D. Katz, and Mateusz Skomra    _Universal Complexity Bounds Based on Value Iteration and Application to Entropy Games_  * Nathalie Bertrand, Nicolas Markey, Ocan Sankur, and Nicolas Waldburger    _Parameterized Safety Verification of Round-based Shared-memory Systems_ ## Sketching and streaming  * Aviad Rubinstein, and Junyao Zhao    _Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2- Approximation_  * Moran Feldman, Paul Liu, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen    _Streaming Submodular Maximization under Matroid Constraints_  * Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý    _Streaming Algorithms for Geometric Steiner Forest_  * Moses Charikar, and Erik Waingarten    _Polylogarithmic Sketches for Clustering_  * Amit Deshpande, and Rameshwar Pratap    _One-pass Additive-error Subset Selection for $\ell_{p}$ Subspace approximation_ ## Coding theory  * Tal Yankovitz, and Gil Cohen    _LCC and LDC: Tailor-made Distance Amplification and a Refined Separation_  * Nicolas Resch, and Chen Yuan    _Threshold Rates of Code Ensembles: Linear is Best_  * Dean Doron, and Mary Wootters    _High-Probability List-Recovery, and Applications to Heavy Hitters_  * Ittai Rubinstein    _Explicit and Efficient Construction of (nearly) Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel_  * Zhenjian Lu, Igor Oliveira, and Marius Zimand    _Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity_ # Tuesday 14h00-15h00. Invited speaker 2  * Leslie Ann Goldberg    _Some new (and old) Results on Contention Resolution_ # Tuesday 15h30-17h10. Paper session 2 ## Quantum  * Chi-Ning Chou, Peter Love, Jonathan Shi, and Juspreet Singh Sandhu    _Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond_  * Penghui Yao, Yitong Yin, and Xinyuan Zhang    _Polynomial-Time Approximation of Zero-Free Partition Functions_  * Jaikumar Radhakrishnan, Shyam Dhamapurkar, and Shubham Pawar    _Set Membership with Two Classical and Quantum Bit Probes_  * Sourav Chakraborty, Chandrima Kayal, and Manaswi Paraashar    _Separations between Combinatorial Measures for Transitive Functions_ ## Computability and dynamic systems  * Djamel Eddine Amir, and Mathieu Hoyrup    _Computability of Finite Simplicial Complexes_  * Donald Stull    _The Dimension Spectrum Conjecture for Planar Lines_  * Ville Salo, and Ilkka Törmä    _What can Oracles Teach us about the Ultimate Fate of Life?_  * Jakob Piribauer, Ocan Sankur, and Christel Baier    _The Variance-penalized Stochastic Shortest Path Problem_ ## Reconstruction problems  * Josep Diaz, Varsha Dani, Cristopher Moore, and Thomas Hayes    _Improved Reconstruction of Random Geometric Graphs_  * Andrew McGregor, and Rik Sengupta    _Graph Reconstruction from Random Subgraphs_  * Akash Kumar, Anand Louis, and Rameesh Paul    _Exact Recovery Algorithm for Planted Bipartite Graph in Semi-random Graphs_  * Guy Blanc, Jane Lange, and Li-Yang Tan    _Reconstructing Decision Trees_ ## Game theory, networks, and distributed  * William Kuszmaul, and Shyam Narayanan    _Optimal Time-Backlog Tradeoffs for the Variable-Processor Cup Game_  * Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, and Nicole Wein    _Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost_  * Stavros Ioannidis, Bart de Keijzer, and Carmine Ventre    _Strong Approximations and Irrationality in Financial Networks with Derivatives_  * Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, and Anna Melnichenko    _Social Distancing Network Creation_ # Tuesday 18h00-21h00. Cocktail and vernissage of the exhibition for the 50 years of EATCS / ICALP # Wednesday 8h30-9h30. Invited speaker 3  * Constantinos Daskalakis    _Equilibrium Computation, Deep Learning, and Multi-Agent (Reinforcement) Learning_ # Wednesday 10h00-12h05. Paper session 3 ## Counting and sampling  * Charilaos Efthymiou    _On Sampling Symmetric Gibbs Distributions on Sparse Random Graphs and Hypergraphs._  * Ivona Bezakova, Andreas Galanis, Leslie Goldberg, and Daniel Stefankovic    _Fast sampling via Spectral Independence beyond Bounded-degree Graphs_  * Amin Coja-Oghlan, Andreas Galanis, Leslie Ann Goldberg, Jean Bernoulli Ravelomanana, Daniel Stefankovic, and Eric Vigoda    _Metastability of the Potts Ferromagnet on Random Regular Graphs_  * Andreas Galanis, Daniel Stefankovic, and Eric Vigoda    _Approximating Observables is as Hard as Counting_  * Guoliang Qiu, Yanheng Wang, and Chihao Zhang    _A Perfect Sampler for Hypergraph Independent Sets_ ## Tranducers and automata  * Mika Göös, Stefan Kiefer, and Weiqiang Yuan    _Lower Bounds for Unambiguous Automata via Communication Complexity_  * Antonio Casares, Thomas Colcombet, and Karoliina Lehtinen    _On the Size of Good-for-games Rabin Automata and its Link with the Memory in Muller Games_  * Léo Exibard, Emmanuel Filiot, and Ayrat Khalimov    _A Generic Solution to Register-bounded Synthesis With an Application to Discrete Orders_  * Leon Bohn, and Christof Löding    _Passive Learning of Deterministic Büchi Automata by Combinations of DFAs_  * Moses Ganardi, Rupak Majumdar, Andreas Pavlogiannis, Lia Schütze, and Georg Zetzsche    _Reachability in Bidirected Pushdown VASS_ ## Property testing  * Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury, and Sayantan Sen    _Tolerant Bipartiteness Testing in Dense Graphs_  * Louis Esperet, and Sergey Norin    _Testability and Local Certification of Monotone Properties in Minor-closed Classes_  * Omri Ben-Eliezer, Shoham Letzter, and Erik Waingarten    _Finding Monotone Patterns in Sublinear Time, Adaptively_  * Talya Eden, Dana Ron, and Will Rosenbaum    _Almost Optimal Bounds for Sublinear-Time Sampling of $k$-Cliques in Bounded Arboricity Graphs_  * Karl Bringmann, Alejandro Cassis, Nick Fischer, and Vasileios Nakos    _Improved Sublinear-Time Edit Distance for Preprocessed Strings_ ## Dynamic algorithms and sensitivity oracles  * Josh Alman, and Dean Hirsch    _Parameterized Sensitivity Oracles and Dynamic Algorithms using Exterior Algebras_  * Surender Baswana, Koustav Bhanja, and Abhyuday Pandey    _Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle_  * Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck    _Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances_  * Aaron Bernstein, Jan van den Brand, Maximilian Probst, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun    _Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary_  * Aleksander B. G. Christiansen, and Eva Rotenberg    _Fully-dynamic α + 2 Arboricity Decomposition and Implicit Colouring._ # Wednesday 14h00-16h05. Best papers session  * Joakim Blikstad    _Sublinear-round Parallel Matroid Intersection_  * Jakub Tětek    _Approximate Triangle Counting via Sampling and Fast Matrix Multiplication_  * Gaëtan Douéneau-Tabot    _Hiding Pebbles when the Output Alphabet is Unary_  * Ilan Newman, and Nithin Varma    _Strongly Sublinear Algorithms for Testing Pattern Freeness_  * Jakub Gajarský, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon Toruńczyk    _Twin-width and Types_ # Wednesday 16h45-17h30. EATCS Award 2022  * TBA    _TBA_ # Wednesday 17h30-19h30. EATCS general assembly  *    _EATCS general assembly:\\ EATCS fellows, EATCS distinguished dissertation Award, Best Icalp papers, Best Icalp Student Papers_ # Thursday 8h30-9h30. Invited speaker 4  * Albert Atserias    _Towards a Theory of Algorithmic Proof Complexity: Motivation and Directions_ # Thursday 10h00-12h05. Paper session 4 ## Computational Geometry  * Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, and Andreas Wiese    _Tight Approximation Algorithms for Two-dimensional Guillotine Strip Packing_  * Fedor Fomin, Petr Golovach, Tanmay Inamdar, and Meirav Zehavi    _(Re)packing Equal Disks into Rectangle_  * Ziyun Huang, and Jinhui Xu    _In-Range Farthest Point Queries and Related Problem in High Dimensions_  * Jacobus Conradi, and Anne Driemel    _On Computing the k-Shortcut Fréchet Distance_  * Klaus Jansen, Arindam Khan, Marvin Lira, and K. V. N. Sreenivas    _A PTAS for Packing Hypercubes into a Knapsack_ ## Parameterized complexity  * Ramanujan M. Sridharan, Daniel Lokshtanov, and Fahad Panolan    _Backdoor Sets on Nowhere Dense SAT_  * Bingkai Lin, Xuandi Ren, Yican Sun, and Xiuhan Wang    _On Lower Bounds of Approximating Parameterized $k$-Clique_  * Ishay Haviv    _A Fixed-Parameter Algorithm for the Kneser Problem_  * Clément Legrand-Duchesne, Ashutosh Rai, and Martin Tancer    _Parameterized Complexity of Untangling Knots_  * Alexandra Lassota, Aleksander Łukasiewicz, and Adam Polak    _Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs_ ## Approximation algorithms  * Lin Chen, Xiaoyu Wu, and Guochuan Zhang    _Approximation Algorithms for Interdiction Problem with Packing Constraints_  * Karl Bringmann, and Alejandro Cassis    _Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution_  * Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, and Pasin Manurangsi    _Improved Approximation Algorithms and Lower Bounds for Search- Diversification Problems_  * Nikhil Ayyadevara, Rajni Dabas, Arindam Khan, and K. V. N. Sreenivas    _Near-optimal Algorithms for Stochastic Online Bin Packing_  * Claire Mathieu, and Hang Zhou    _A PTAS for Capacitated Vehicle Routing on Trees_ ## Optimization  * Shunhua Jiang, Bento Natura, and Omri Weinstein    _A Faster Interior-Point Method for Sum-of-Squares Optimization_  * Ming Ding, Rasmus Kyng, and Peng Zhang    _Two-Commodity Flow is Equivalent to Linear Programming under Nearly-Linear Time Reductions_  * Marcin Briański, Martin Koutecký, Daniel Kráľ, Kristýna Pekárková, and Felix Schröder    _Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Anteger Programming_  * Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, and Peng Zhang    _Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets_  * Mitchell Black, and Amir Nayyeri    _Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes_ # Wednesday 14h30-15h50. Presburger Award and Gödel Prize 2022  * TBA    _TBA_  * TBA    _TBA_ # Thursday 16h00-17h40. Paper session 5 ## Homomorphisms  * Martin Grohe, Gaurav Rattan, and Tim Seppelt    _Homomorphism Tensors and Linear Equations_  * Sandra Kiefer, and Daniel Neuen    _A Study of Weisfeiler-Leman Colorings on Planar Graphs_  * Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, and Kirill Simonov    _The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique- Width_  * Balagopal Komarath, Anurag Pandey, and C. S. Rahul    _Monotone Arithmetic Complexity of Graph Homomorphism Polynomials_ ## Process calculi and types  * David Barozzini, Paweł Parys, and Jan Wróblewski    _Unboundedness for Recursion Schemes: A Simpler Type System_  * Enguerrand Prebet    _Functions and References in the pi-Calculus: Full Abstraction and Proof Techniques_  * Todd Schmid, Wojciech Rozowski, Alexandra Silva, and Jurriaan Rot    _Processes Parametrised by an Algebraic Theory_ ## Learning theory, fairness, and privacy  * Jan Pich, and Rahul Santhanam    _Learning Algorithms versus Automatability of Frege Systems_  * Nathaniel Harms, and Yuichi Yoshida    _Downsampling for Testing and Learning in Product Distributions_  * Niclas Boehmer, and Tomohiro Koana    _The Complexity of Finding Fair Many-to-One Matchings_  * Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee    _Privately Estimating Graph Parameters in Sublinear time_ ## Randomness in computation  * Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro    _Low-Degree Polynomials Extract from Local Sources_  * Shir Peleg, Gil Cohen, Dor Minzer, Aaron Potechin, and Amnon Ta-Shma    _Expander Random Walks: The General Case and Limitations_  * Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha    _Smoothed Analysis of the Koml\'os Conjecture_  * Jakob Bæk Tejs Houen, and Mikkel Thorup    _Understanding the Moments of Tabulation Hashing via Chaoses_ # Friday 8h30-9h30. Invited speaker 5  * Madhu Sudan    _Streaming and Sketching Complexity of CSPs: A survey_ # Friday 10h00-12h05. Paper Session 6 ## Data structures, sorting, and string processing  * Elahe Ghasemi, Vincent Jugé, and Ghazal Khalighinejad    _Galloping in Fast-growth Natural Merge Sorts_  * Takaaki Nishimoto, Shunsuke Kanda, and Yasuo Tabei    _An Optimal-Time RLBWT Construction in BWT-runs Bounded Space_  * Arnab Ganguly, Rahul Shah, and Sharma V. Thankachan    _Fully Functional Parameterized Suffix Trees in Compact Space_  * Debarati Das, Tomasz Kociumaka, and Barna Saha    _Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding_  * Pawel Gawrychowski, and Karol Pokorski    _Sublinear Dynamic Interval Scheduling (on one or multiple machines)_ ## Graphs and complexity  * Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, and Raghunath Tewari    _Dynamic Meta-theorems for Distance and Matching_  * Amina Doumane    _Regular Expressions for Tree-Width 2 Graphs_  * Tamio-Vesa Nakajima, and Stanislav Živný    _Linearly Ordered Colourings of Hypergraphs_  * Niel De Beaudrap, Aleks Kissinger, and John van de Wetering    _Circuit Extraction for ZX-diagrams can be \#P-hard_  * Pawel Idziak, Piotr Kawałek, Jacek Krzaczkowski, and Armin Weiß    _Satisfiability Problems for Finite Groups_ ## Graph distances and fault tolerance  * Diptarka Chakraborty, Kushagra Chatterjee, and Keerti Choudhary    _Pairwise Reachability Oracles and Preservers under Failures_  * Michał Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Toruńczyk, and Alexandre Vigny    _Algorithms and Data Structures for First-order Logic with Connectivity under Vertex Failures_  * Chao Liao, Qingyun Chen, Bundit Laekhanukit, and Yuhao Zhang    _Almost Tight Approximation Hardness for Single-Source Directed k-Edge- Connectivity_  * Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai    _Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver_  * Shimon Kogan, and Merav Parter    _Beating Matrix Multiplication for $n^{1/3}$-Directed Shortcuts_ ## Complexity  * Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin Künnemann    _A Structural Investigation of the Approximability of Polynomial-Time Problems_  * Theodoros Papamakarios, and Alexander Razborov    _Space Characterizations of Complexity Measures and Size-space Trade-offs in Propositional Proof Systems_  * Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, and Xinyu Wu    _The SDP Value of Random 2CSPs_  * Luyining Gan, and Jie Han    _The Decision Problem for Perfect Matchings in Dense Hypergraphs_  * David Caballero, Timothy Gomez, Robert Schweller, and Tim Wylie    _Unique Assembly Verification in Two-Handed Self-Assembly_ # Thursday 19h30-22h30. Conference dinner # Friday 14h00-15h00. Invited speaker 6  * Stéphan Thomassé    _TBA_ # Friday 15h30-16h45. Paper session 7 ## Online algorithms  * Yossi Azar, Chay Machluf, Boaz Patt-Shamir, and Noam Touitou    _Competitive Vertex Recoloring_  * Ryder Chen, Jahanvi Khatkar, and Seeun William Umboh    _Online Weighted Cardinality Joint Replenishment Problem with Delay_ ## Decremental algorithms  * Jakub Łącki, and Yasamin Nazari    _Near-Optimal Decremental Hopsets with Applications_  * Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian    _Regularized Box-Simplex Games and Dynamic Decremental Bipartite Matching_  * Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja    _Decremental Matching in General Graphs_ ## Cryptography  * Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta    _Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices_  * Shweta Agrawal, Damien Stehle, and Anshu Yadav    _Round-Optimal Lattice-Based Threshold Signatures, Revisited_  * Justin Holmgren, Andrea Lincoln, and Ron Rothblum    _Delegation for Search Problems_ ## Counting and complexity  * Surya Mathialagan, Virginia Vassilevska Williams, and Yinzhan Xu    _Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds_  * Calvin Beideman, Karthekeyan Chandrasekaran, and Weihang Wang    _Counting and Enumerating Optimum Cut Sets for Hypergraph $k$-partitioning problems for fixed $k$_  * Pierre Bergé, Édouard Bonnet, and Hugues Déprés    _Deciding Twin-width at most 4 is NP-complete_