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_