-->

JOINT INVITED SPEAKERS

Edith Elkind

Edith Elkind

University of Oxford

Stephanie Weirich

Stephanie Weirich

UPenn

ICALP INVITED SPEAKERS

Anuj Dawar

Anuj Dawar

University of Cambridge

Danupon Nanongkai

Danupon Nanongkai

MPI Saarbrücken

Merav Parter

Merav Parter

Weizmann Institute

LICS INVITED SPEAKERS

Martin Escardó

Martin Escardó

University of Birmingham

Alexandra Silva

Alexandra Silva

Cornell University

LICS INVITED TUTORIAL SPEAKERS

Sam Buss

Sam Buss

UCSD

Alex Simpson

Alex Simpson

University of Ljubljana

FSCD INVITED SPEAKERS

Delia Kesner

Delia Kesner

Université Paris Cité

Bettina Könighofer

Bettina Könighofer

TU Graz

Sebastian Ullrich

Sebastian Ullrich

LEAN-FRO and Karlsruhe Institute of Technology

ICALP 2024

51st EATCS International Colloquium on Automata, Languages and Programming

ICALP is the main conference and annual meeting of the European Association for Theoretical Computer Science (EATCS). ICALP 2024 will be preceded by a series of workshops, which will take place on July 7, 2024.

ICALP 2024 is organized by the Department of Software Science, Tallinn University of Technology, in cooperation with the European Association for Theoretical Computer Science (EATCS).

The first ICALP conference was organized in 1972. For more information about previous editions, see the EATCS webpage http://eatcs.org/index.php/international-colloquium.

Important dates

  • Submissions: February 14, 2024 at 1pm CET
  • Rebuttal: March 26-29, 2024
  • Author notification: April 14, 2024
  • Camera-ready version: April 28, 2024
  • Early registration: May 17, 2024
  • Conference: July 8-12, 2024
  • ICALP Workshops: July 6-7, 2024

Submissions

Paper submissions are handled via Easychair.

1) Papers must present original research on the theory of computer science. No prior publication and no simultaneous submission to other publication outlets (either a conference or a journal) is allowed. Authors are encouraged to also make full versions of their submissions freely accessible in an on-line repository such as ArXiv, HAL, ECCC.

2) Submissions take the form of an extended abstract of no more than 15 pages, excluding references and a clearly labelled appendix. The appendix may consist either of omitted proofs or of a full version of the submission, and it will be read at the discretion of program committee members. The use of the LIPIcs document class is an option, but not required. The extended abstract has to present the merits of the paper and its main contributions clearly, and describe the key concepts and technical ideas used to obtain the results. Submissions must provide the proofs which can enable the main mathematical claims of the paper to be verified.

3) Submissions are anonymous. The conference will employ a lightweight double-blind reviewing process. Submissions should not reveal the identity of the authors in any way. Authors should ensure that any references to their own related work are in the third person (e.g., not “We build on our previous work …” but rather “We build on the work of …”).

The purpose of this double-blind process is to help PC members and external reviewers come to an initial judgment about the paper without bias, and not to make it impossible for them to discover who the authors are if they were to try. Nothing should be done in the name of anonymity that weakens the submission or makes the job of reviewing the paper more difficult. In particular, important references should not be omitted. In addition, authors should feel free to disseminate their ideas or draft versions of their paper as they normally would. For example, authors may post drafts of their papers on the web, submit them to arXiv, and give talks on their research ideas.

4) Submissions authored or co-authored by members of the program committee are allowed.

5) The submissions are done via Easychair to the appropriate track of the conference (see topics below). The use of pdflatex or similar pdf generating tools is mandatory and the page limit is strict (see point 2.) Papers that deviate significantly from these requirements risk rejection without consideration of merit.

6) During the rebuttal phase, authors will have from March 26-29, 2024 to view and respond to initial reviews. Further instructions will be sent to authors of submitted papers before that time.

7) At least one author of each accepted paper is expected to register for the conference, and all talks are in-person. In exceptional cases, there may be support for remotely presenting a talk.

8) Papers authored only by students should be marked as such upon submission in order to be eligible for the best student paper awards of the track.

SafeToC

ICALP has joined http://safetoc.org.

Participants have to follow the ICALP code of conduct.

The ICALP 2024 SafeToc advocate is Diana Kessler.

`

ICALP TRACKS

Papers presenting original research on all aspects of theoretical computer science are sought. Typical, but not exclusive, topics of interest are:

Track A

`Algorithms, Complexity and Games

  • Algorithmic and Complexity Aspects of Network Economics
  • Algorithmic Aspects of Biological and Physical Systems
  • Algorithmic Aspects of Networks and Networking
  • Algorithmic Aspects of Security and Privacy
  • Algorithmic Game Theory and Mechanism Design
  • Approximation and Online Algorithms
  • Combinatorial Optimization
  • Combinatorics in Computer Science
  • Computational Complexity
  • Computational Geometry
  • Computational Learning Theory
  • Cryptography
  • Data Structures
  • Design and Analysis of Algorithms
  • Distributed and Mobile Computing
  • Foundations of Machine Learning
  • Graph Mining and Network Analysis
  • Parallel and External Memory Computing
  • Parameterized Complexity
  • Quantum Computing
  • Randomness in Computation
  • Sublinear Time and Streaming Algorithms
  • Theoretical Foundations of Algorithmic Fairness

Track B

Automata, Logic, Semantics, and Theory of Programming

  • Algebraic and Categorical Models of Computation
  • Automata, Logic, and Games
  • Database Theory, Constraint Satisfaction Problems, and Finite Model Theory
  • Formal and Logical Aspects of Learning
  • Formal and Logical Aspects of Security and Privacy
  • Logic in Computer Science and Theorem Proving
  • Models of Computation: Complexity and Computability
  • Models of Concurrent, Distributed, and Mobile Systems
  • Models of Reactive, Hybrid, and Stochastic Systems
  • Principles and Semantics of Programming Languages
  • Program Analysis, Verification, and Synthesis
  • Type Systems and Typed Calculi

Accepted papers

Track A

Marin Bougeret, Bart M. P. Jansen and Ignasi Sau. Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
Ce Jin and Hongxun Wu. A Faster Algorithm for Pigeonhole Equal Sums
Hamed Hatami, Kaave Hosseini, Shachar Lovett and Anthony Ostuni. Refuting approaches to the log-rank conjecture for XOR functions
Yiannis Giannakopoulos, Alexander Grosz and Themistoklis Melissourgos. On the Smoothed Complexity of Combinatorial Local Search
Yu Chen and Zihan Tan. Lower Bounds on 0-Extension with Steiner Nodes
Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk and Paweł Rzążewski. Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters
Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach and Tuukka Korhonen. Two-sets cut-uncut on planar graphs
Shiri Chechik, Doron Mukhtar and Tianyi Zhang. Streaming Edge Coloring with Subquadratic Palette Size
Shiri Chechik and Tianyi Zhang. Path-Reporting Distance Oracles with Logarithmic Stretch and Linear Size
Guy Goldberg. Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error
Soh Kumabe and Yuichi Yoshida. Lipschitz Continuous Allocations for Optimization Games
Junjie Chen, Minming Li, Haifeng Xu and Song Zuo. Bayesian Calibrated Click-Through Auctions
Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx and Roohani Sharma. Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
Yusuke Kobayashi and Tatsuya Terao. Subquadratic Submodular Maximization with a General Matroid Constraint
Jonas Kamminga and Sevag Gharibian. BQP, meet NP: Search-to-decision reductions and approximate counting
William Kuszmaul and Zoe Xi. Towards an Analysis of Quadratic Probing
Naoto Ohsaka. Alphabet Reduction for Reconfiguration Problems
Michaela Borzechowski, John Fearnley, Spencer Gordon, Rahul Savani, Patrick Schnider and Simon Weber. Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
Andreas Emil Feldmann and Michael Lampis. Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
Sophia Heimann, Hung P. Hoang and Stefan Hougardy. The k-Opt algorithm for the Traveling Salesman Problem has exponential running time for k > 5
Surender Baswana and Koustav Bhanja. Vital Edges for (s,t)-mincut: Efficient Algorithms, Compact Structures, & Optimal Sensitivity Oracles
Mario Grobler, Stephanie Maaz, Nicole Megow, Amer Mouawad, Vijayaragunathan Ramamoorthi, Daniel Schmand and Sebastian Siebertz. Solution discovery via reconfiguration for problems in P
Sanjeev Khanna, Aaron Putterman and Madhu Sudan. Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
Yaniv Sadeh and Haim Kaplan. Caching Connections in Matchings
Édouard Bonnet, Jędrzej Hodor, Tuukka Korhonen and Tomáš Masařík. Treewidth is Polynomial in Maximum Degree on Graphs Excluding a Planar Induced Minor
Ce Jin, Michael Kapralov, Sepideh Mahabadi and Ali Vakilian. Streaming Algorithms for Connectivity Augmentation
Orestis Plevrakis, Seyoon Ragavan and S. Matthew Weinberg. On the cut-query complexity of approximating max-cut
Klaus Heeger, Danny Hermelin, Matthias Mnich and Dvir Shabtay. No Polynomial Kernels for Knapsack
Itai Boneh, Shay Golan, Shay Mozes and Oren Weimann. Õptimal Dynamic Time Warping on Run-Length Encoded Strings
Shuichi Hirahara and Naoto Ohsaka. Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
Shiri Chechik and Tianyi Zhang. Faster Algorithms for Dual-Failure Replacement Paths
Shaofeng H.-C. Jiang, Wenqian Wang, Yubo Zhang and Yuhao Zhang. Algorithms for the Generalized Poset Sorting Problem
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek and Sorrachai Yingchareonthawornchai. The Group Access Bounds for Binary Search Trees
Chung Shue Chen, Peter Keevash, Sean Kennedy, Élie de Panafieu and Adrian Vetta. Robot positioning using torus packing for multisets
Christophe Paul, Evangelos Protopapas, Dimitrios Thilikos and Sebastian Wiederrecht. Delineating Half-Integrality of the Erdős-Pósa Property for Minors: the Case of Surfaces
Agastya Vibhuti Jha and Akash Kumar. A Sublinear Time Tester for Max-Cut on Clusterable Graphs
Yotam Kenneth and Robert Krauthgamer. Cut Sparsification and Succinct Representation of Submodular Hypergraphs
Andrei Constantinescu, Pascal Lenzner, Rebecca Reiffenhäuser, Daniel Schmand and Giovanna Varricchio. Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games
Maxime Cautrès, Nathan Claudet, Mehdi Mhalla, Simon Perdrix, Valentin Savin and Stéphan Thomassé. Vertex-minor universal graphs for generating entangled quantum subsystems
Augusto Modanese and Yuichi Yoshida. Testing Spreading Behavior in Networks with Arbitrary Topologies
Matan Gilboa. A Characterization of Complexity in Public Goods Games
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király and Shubhang Kulkarni. Splitting-off in Hypergraphs
Sariel Har-Peled, Elfarouk Harb and Vasilis Livanos. Oracle-Augmented Prophet Inequalities
Rajesh Jayaram, Jakub Łącki, Slobodan Mitrović, Krzysztof Onak and Piotr Sankowski. Dynamic PageRank: Algorithms and Lower Bounds
Emile Anand, Jan van den Brand, Mehrdad Ghadiri and Daniel J Zhang. The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
Yury Makarychev, Max Ovsiankin and Erasmo Tani. Approximation Algorithms for lp-Shortest Path and lp-Group Steiner Tree
Adam Karczmarz and Marcin Smulewicz. Fully Dynamic Strongly Connected Components in Planar Digraphs
Shyan Akmal, Virginia Vassilevska Williams and Nicole Wein. Detecting Disjoint Shortest Paths in Linear Time and More
Kingsley Yung. Limits of Sequential Local Algorithms on the Random k-XORSAT Problem
Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo and Jiaheng Wang. Approximate counting for spin systems in sub-quadratic time
Chiranjib Bhattacharyya, Ravindran Kannan and Amit Kumar. Random Separating Hyperplane Theorem and Learning Polytopes
Michal Dory, Sebastian Forster, Yasamin Nazari and Tijn de Vos. New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
Vikraman Arvind and Pushkar Joglekar. A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
Shuangle Li, Bingkai Lin and Yuwei Liu. Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer and Pavel Veselý. Fully-Scalable MPC Algorithms for Clustering in High Dimension
Clément Dallard, Fedor Fomin, Petr Golovach, Tuukka Korhonen and Martin Milanič. Computing Tree Decompositions with Small Independence Number
Andreas Björklund, Petteri Kaski and Jesper Nederlof. Another Hamiltonian cycle in bipartite Pfaffian graphs
Johannes Meintrup, Frank Kammer, Konstantinos Dogeas, Thomas Erlebach and William K. Moses Jr.. Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
Yossi Azar, Shahar Lewkowicz and Danny Vainstein. List Update with Delays or Time Windows
Boris Klemz and Marie Diana Sieper. Constrained Level Planarity is FPT with Respect to the Vertex Cover Number
Weiming Feng and Heng Guo. An FPRAS for two terminal reliability in directed acyclic graphs
Martin Grohe and Daniel Neuen. Isomorphism for Tournaments of Small Twin Width
Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo and Or Zamir. Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
Robert Ganian, Haiko Müller, Sebastian Ordyniak, Giacomo Paesani and Mateusz Rychlicki. A Tight Subexponential Algorithm for Two-Page Book Embedding
Baris Can Esmer, Jacob Focke, Dániel Marx and Paweł Rzążewski. Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
Keren Censor-Hillel, Tomer Even and Virginia Vassilevska Williams. Fast Approximate Counting of Cycles
Kento Iseri, Tomohiro I, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka and Ayumi Shinohara. Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg and Sushant Sachdeva. Optimal Electrical Oblivious Routing on Expanders
Shi Li, Chenyang Xu and Ruilong Zhang. Polylogarithmic Approximations for Robust s-t Path
Kent Quanrud. Adaptive sparsification for matroid intersection
Sushant Sachdeva, Anvith Thudi and Yibin Zhao. Better Sparsifiers for Directed Eulerian Graphs
Yuda Feng and Shi Li. A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
Niklas Schlomberg. An improved integrality gap for disjoint cycles in planar graphs
Reut Levi, Talya Eden and Dana Ron. Testing Ck-freeness in bounded-arboricity graphs
Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta and Saswata Mukherjee. Exponential lower bounds via exponential sums
Ariel Korin, Tsvi Kopelowitz and Liam Roditty. On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
Noga Ron-Zewi and Elie Abboud. Finer-grained Reductions in Fine-grained Hardness of Approximation
Ilan Doron-Arad, Ariel Kulik and Hadas Shachnai. Lower Bounds for Matroid Optimization Problems with a Linear Constraint
Vladimir Podolskii and Dmitrii Sluch. One-Way Communication Complexity of Partial XOR Functions
Fateme Abbasi, Marek Adamczyk, Miguel Bosch Calvo, Jarosław Byrka, Fabrizio Grandoni, Krzysztof Sornat and Antoine Tinguely. An O(loglog n)-Approximation for Submodular Facility Location
Lucas Gretta and Eric Price. Sharp Noisy Binary Search with Monotonic Probabilities
Aditi Dudeja. Decremental Matching in General Weighted Graphs
Djamal Belazzougui, Gregory Kucherov and Stefan Walzer. Better space-time-robustness trade-offs for set reconciliation
Sami Davies, Benjamin Moseley and Heather Newman. Simultaneously Approximating All lp-norms in Correlation Clustering
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein and Amin Saberi. Sublinear Algorithms for TSP via Path Covers
Holger Dell, John Lapinskas and Kitty Meeks. Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
Leonid Gurvits, Nathan Klein and Jonathan Leake. From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP
Shalev Ben-David and Srijita Kundu. Oracle separation of QMA and QCMA with bounded adaptivity
Prantar Ghosh and Manuel Stoeckl. Low-Memory Algorithms for Online Edge Coloring
Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj and Ramanujan M. Sridharan. Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy
Mónika Csikós and Nabil Mustafa. An Optimal Sparsification Lemma for Low-Crossing Matchings and its Applications
Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev and Maksim Zhukovskii. Tight Bounds on Adjacency Labels for Monotone Graph Classes
Mohammad Hossein Bateni, Laxman Dhulipala, Kishen Gowda, D Ellis Hershkowitz, Rajesh Jarayam and Jakub Lacki. Parallel and Sequential Hardness of Hierarchical Graph Clustering
Eunou Lee and Ojas Parekh. An improved Quantum Max Cut approximation via Maximum Matching
Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma and Prafullkumar Tale. Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth and Vertex Cover
Soheil Behnezhad and Mohammad Saneian. Streaming Edge Coloring with Asymptotically Optimal Colors
Jan Olkowski, Dariusz Kowalski and Mohammad Hajiaghayi. Distributed fast crash-tolerant consensus with nearly-linear quantum communication
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay and Chen Wang. The Discrepancy of Shortest Paths
Charlie Carlson, Ewan Davies, Alexandra Kolla and Aditya Potukuchi. A spectral approach to approximately counting independent sets in dense bipartite graphs
Xin Li and Yan Zhong. Two-Source and Affine Non-Malleable Extractors for Small Entropy
Omkar Baraskar, Agrim Dewan, Chandan Saha and Pulkit Sinha. NP-hardness of testing equivalence to sparse polynomials and constant support polynomials
Yaowei Long and Yunfan Wang. Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity
Noel Arteche, Erfan Khaniki, Ján Pich and Rahul Santhanam. From Proof Complexity to Circuit Complexity via Interactive Protocols
Kevin Hua, Daniel Li, Jaewoo Park and Thatchaphol Saranurak. Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
Li Chen and Mingquan Ye. High-Accuracy Multicommodity Flows via Iterative Refinement
Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein and Zixuan Xu. Additive Spanner Lower Bounds with Optimal Inner Graph Structure
Zhenjian Lu and Rahul Santhanam. Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity
Panagiotis Charalampopoulos, Pawel Gawrychowski and Samah Ghazawi. Optimal Bounds for Distinct Quartics
Ilan Doron and Seffi Naor. Non-Linear Paging
Narek Bojikian and Stefan Kratsch. A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
Yasushi Kawase, Koichi Nishimura and Hanna Sumita. Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets
Pritam Acharya, Sujoy Bhore, Aaryan Gupta, Arindam Khan, Bratin Mondal and Andreas Wiese. Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects
Srnivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez and Carlos Palazuelos. Learning low-degree quantum objects
Nick Fischer and Leo Wennmann. Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki and Tamás Schwarcz. Problems on Group-labeled Matroid Bases
Fateme Abbasi, Sandip Banerjee, Joachim Spoerhase, Ameet Gadekar, Roohani Sharma, Jaroslaw Byrka, Kamyar Khodamoradi, Parinya Chalermsook and Dániel Marx. Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
Serge Gaspers and Jerry Zirui Li. Quantum Algorithms for Graph Coloring and other Partitioning, Covering, and Packing Problems
Yu Chen, Michael Kapralov, Mikhail Makarov and Davide Mazzali. On the Streaming Complexity of Expander Decomposition
Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh and Anannya Upasana. Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
Aaron Potechin and Aaron Zhang. Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle

Track B

Sylvain Schmitz and Lia Schütze. On the Length of Strongly Monotone Descending Chains over ℕᵈ
Alberto Larrauri and Stanislav Živný. Solving promise equations over monoids and groups
Massimo Benerecetti, Laura Bozzelli, Fabio Mogavero and Adriano Peron. Automata-Theoretic Characterisations of Branching-Time Temporal Logics
George Kenison. The Threshold Problem for Hypergeometric Sequences with Quadratic Parameters
Mohan Sai Teja Dantam and Richard Mayr. Finite-memory Strategies for Almost-sure Energy-MeanPayoff Objectives in MDPs
Guillaume Theyssier. FO logic on cellular automata orbits equals MSO logic
Yuxi Fu, Qizhe Yang and Yangluo Zheng. Improved Algorithm for Reachability in d-VASS
Julian Dörfler and Christian Ikenmeyer. Functional Closure Properties of Finite N-weighted Automata
Cheng Zhang, Arthur Azevedo de Amorim and Marco Gaboardi. Domain Reasoning In TopKAT
Roland Guttenberg. Flattability of Priority Vector Addition Systems
Jakub Rydval, Žaneta Semanišinová and Michał Wrona. Identifying Tractable Quantified Temporal Constraints within Ord-Horn
Dmitry Chistikov, Alessio Mansutti and Mikhail Starchak. Integer Linear-Exponential Programming in NP by Quantifier Elimination
Antoine Mottet, Tomáš Nagy and Michael Pinsker. An order out of nowhere: a new algorithm for infinite-domain CSPs
Benjamin Scheidt. On Homomorphism Indistinguishability and Hypertree Depth
Manon Blanc and Olivier Bournez. The complexity of computing in continuous time: space complexity is precision
Bruno Loff and Mateusz Skomra. Smoothed analysis of deterministic discounted and mean-payoff games
Wojciech Różowski. A Complete Quantitative Axiomatisation of Behavioural Distance of Regular Expressions
Michael Benedikt, Chia-Hsuan Lu, Boris Motik and Tony Tan. Decidability of Graph Neural Networks via Logical Characterizations
Arnaud Carayol and Lucien Charamond. The structure of trees in the pushdown hierarchy
Rohan Acharya, Marcin Jurdziński and Aditya Prakash. Lookahead Games and Efficient Determinisation of History-Deterministic Büchi Automata
Pavol Kebis, Florian Luca, Joel Ouaknine, Andrew Scoones and James Worrell. On Transcendence of Numbers Related to Sturmian and Arnoux-Rauzy Words
Jakub Rydval. Homogeneity and Homogenizability: Hard Problems for the Logic SNP
Amina Doumane, Samuel Humeau and Damien Pous. A finite presentation of treewidth at most 3 graphs
Go Hashimoto, Daniel Gaina and Ionuț Țuțu. Forcing, Transition Algebras, and Calculi
Jakub Gajarský and Rose McCarty. On classes of bounded tree rank, their interpretations, and efficient sparsification
Yuya Uezato. Regular Expressions with Backreferences and Lookaheads Capture NLOG
Paul Gallot, Sebastian Maneth, Keisuke Nakano and Charles Peyrat. Deciding Linear Height and Linear Size-to-Height Increase of Macro Tree Transducers
C. Aiswarya, Amaldev Manuel and Saina Sunny. Edit Distance of Finite State Transducers
Christoph Haase, Shankara Naryananan Krishna, Khushraj Madnani, Om Swostik Mishra and Georg Zetzsche. An efficient quantifier elimination procedure for Presburger arithmetic
Raphael Douglas Giles, Vincent Jackson and Christine Rizkallah. T-Rex: Termination of Recursive Functions using Lexicographic Linear Combinations
Steffen van Bergerem, Roland Guttenberg, Sandra Kiefer, Corto Mascle, Nicolas Waldburger and Chana Weil-Kennedy. Verification of Population Protocols with Unordered Data
Quentin Guilmant, Engel Lefaucheux, Joël Ouaknine and James Worell. The 2-Dimensional Constraint Loop Problem is Decidable
Pascal Baumann, Eren Keskin, Roland Meyer and Georg Zetzsche. Separability in Büchi Vass and Singly Non-Linear Systems of Inequalities
Mikołaj Bojańczyk, Lê Thành Dũng Nguyên and Rafał Stefański. Function spaces for orbit-finite sets

ICALP COMMITTEES

Conference chair

Pawel Sobocinski (Tallinn UoT)

Organising committee

  • Niccolò Veltri (Tallinn University of Technology)
  • Amar Hadzihasanovic (Tallinn University of Technology)
  • Fosco Loregian (Tallinn University of Technology)
  • Matt Earnshaw (Tallinn University of Technology)
  • Diana Kessler (Tallinn University of Technology)
  • Ekaterina Zhuchko (Tallinn University of Technology)
  • Juhan Ernits (Tallinn University of Technology)
  • Kristi Ainen (Tallinn University of Technology)
  • Arianna Jater (Tallinn University of Technology)
  • Mariann Lugus (Tallinn University of Technology)

Proceedings chair

Gabriele Puppis (University of Udine, Italy)

Workshop chairs

  • Valentin Blot (ENS Paris-Saclay)
  • Valia Mitsou (IRIF, University Paris Cité)
  • Ekaterina Zhuchko (Tallinn University of Technology)

Programme Commitee (Track A)

Chairs: Karl Bringmann (Saarland University, Germany) and Ola Svensson (EPFL, Switzerland)

  • Nima Anari (Stanford University)
  • Karl Bringmann (co-chair, Saarland University)
  • Parinya Chalermsook (Aalto University)
  • Vincent Cohen-Addad (Google Research)
  • Jose Correa (Universidad de Chile)
  • Holger Dell (Goethe University Frankfurt)
  • Ilias Diakonikolas (University of Wisconsin-Madison)
  • Yuval Filmus (Technion)
  • Arnold Filtser (Bar Ilan University)
  • Naveen Garg (IIT Delhi)
  • Pawel Gawrychowski (University of Wrocław)
  • Anupam Gupta (Carnegie Mellon University)
  • Samuel Hopkins (MIT)
  • Sophie Huiberts (Columbia University)
  • Giuseppe Italiano (LUISS University)
  • Michael Kapralov (EPFL)
  • Eun Jung Kim (Université Paris-Dauphine)
  • Sándor Kisfaludi-Bak (Aalto University)
  • Tomasz Kociumaka (Max-Planck-Institute for Informatics)
  • Fabian Kuhn (University of Freiburg)
  • Amit Kumar (IIT Delhi)
  • William Kuszmaul (Harvard University)
  • Rasmus Kyng (ETH Zurich)
  • Kasper Green Larsen (Aarhus University)
  • François Le Gall (Nagoya University)
  • Pasin Manurangsi (Google Research)
  • Daniel Marx (CISPA Helmholtz Center for Information Security)
  • Yannic Maus (TU Graz)
  • Nicole Megow (University of Bremen)
  • Ruta Mehta (University of Illinois at Urbana-Champaign)
  • Jakob Nordström (University of Copenhagen)
  • Richard Peng (University of Waterloo)
  • Seth Pettie (University of Michigan)
  • Adam Polak (Bocconi University)
  • Lars Rohwedder (Maastricht University)
  • Eva Rotenberg (DTU Compute)
  • Sushant Sachdeva (University of Toronto)
  • Melanie Schmidt (University of Cologne)
  • Sebastian Siebertz (University of Bremen)
  • Shay Solomon (Tel Aviv University)
  • Nick Spooner (University of Warwick)
  • Clifford Stein (Columbia University)
  • Ola Svensson (co-chair, EPFL)
  • Luca Trevisan (Bocconi University)
  • Ali Vakilian (Toyota Technological Institute Chicago)
  • Jan van den Brand (Georgia Tech)
  • Erik Jan van Leeuwen (Utrecht University)
  • Oren Weimann (University of Haifa)
  • Nicole Wein (University of Michigan)
  • Andreas Wiese (TU Munich)
  • John Wright (UC Berkeley)

Programme Committee (Track B)

Chair: Martin Grohe (RWTH Aachen University)

  • Arnold Beckmann (Swansea University)
  • Manuel Bodirsky (TU Dresden)
  • Patricia Bouyer (CNRS, LMF)
  • Yijia Chen (Shanghai Jiao Tong University)
  • Victor Dalmau (Universitat Pompeu Fabra)
  • Laurent Doyen (CNRS, LMF)
  • Marcelo Fiore (Cambridge University)
  • Stefan Göller (University of Kassel)
  • Martin Grohe (RWTH Aachen University, chair)
  • Sandra Kiefer (Oxford University)
  • Aleks Kissinger (Oxford University)
  • Bartek Klin (Oxford University)
  • Antonin Kucera (Masaryk University Brno)
  • Carsten Lutz (University of Leipzig)
  • Jerzy Marcinkowski (University of Wrocław)
  • Annabelle McIver (Macquaire University Sydney)
  • Andrzej Murawski (Oxford University)
  • Paweł Parys (University of Warsaw)
  • Michał Pilipczuk (University of Warsaw)
  • Joel Ouaknine (Max Planck Institute for Software Systems)
  • Christian Riveros (Pontificia Universidad Catolica de Chile)
  • Alexandra Silva (Cornell University)
  • Balder ten Cate (ILLC Amsterdam)
  • Szymon Toruńczyk (University of Warsaw)
  • Igor Walukiewicz (CNRS, University of Bordeaux)
  • Sarah Winter (IRIF, University Paris Cité)
  • Georg Zetzsche (Max Planck Institute for Software Systems)
  • Martin Ziegler (KAIST)

Registration

All prices are in euros and include 22% VAT. Note that every accepted paper requires at least one regular (non-student) registration.

The prices listed below are the early bird prices, valid until May 17.

Early birdAll inclusiveICALP 2024LiCS 2024FSCD 2024Workshops (1 day)Workshops (2 days)Workshops (3 days)Workshops (unlimited)
Regular non-member 1000 800 640 640 80160240320
Regular member 950 750 590 590
Student non-member 780 600 480 480 60120180240
Student member 730 550 430 430

The prices listed below are the late registration prices, in place after May 17.

Late registrationAll inclusiveICALP 2024LiCS 2024FSCD 2024Workshops (1 day)Workshops (2 days)Workshops (3 days)Workshops (unlimited)
Regular non-member 1200 960 770 770 100200300400
Regular member 1150 910 720 720
Student non-member 780 720 580 580 80160240320
Student member 730 670 530 530

Membership discounts

The relevant membership disounts apply as follows: for ICALP an EATCS membership, for LiCS an ACM/ACM SigLog/IEEE membership, for FSCD an ACM/ACM SigLog/ACM SIGPLAN membership. Any of the above memberships qualifies for a discounted all-inclusive price.

Workshop participation

Conference participants who purchase a conference-specific registration (i.e. ICALP, LiCS or FSCD) and who also wish to attend workshops need to purchase an additional workshop registration, depending on how many days of workshops they wish to attend. The all-inclusive price includes access to all three conferences and unlimited workshop participation.

Welcome reception, Tuesday 9 July

All conference registrations include a ticket to the Welcome reception at Kadriorg Art Museum, Weizengergi 37, on the evening of Tuesday 9 July.

Joint banquet, Wednesday 10 July

The joint banquet will be held on Wednesday 10 July at the Tallinn Seaplane Harbour Museum. All participants who want to attend the banquet must purchase a banquet ticket separately -- the early bird price until May 17 is 85 euros per banquet ticket, the price after May 17 is 100 euros. Additional banquet tickets can be purchased for accompanying people. Note that the all-inclusive price does not include a banquet ticket.

To register, please click on the following link. Our partner Fienta takes payments and provides invoices. For questions regarding registration please email icalp_lics_fscd2024@taltech.ee.

Cancellations and refunds

Cancellations should be notified in writing by e-mail to ICALP_LiCS_FSCD2024@taltech.ee. Your cancellation will be confirmed in writing.

Cancellations are subject to the following conditions:

  • Cancellations received by May 31, 2024: 10% is held as an administrative fee.
  • Cancellations received after May 31, 2024: no refund will be made.

All refunds will be processed after the meeting.

Letter of Confirmation of Participation

A Letter of Confirmation of participation for VISA Applications or other purposes can be requested by e-mail to ICALP_LiCS_FSCD2024@taltech.ee. Letters of Confirmation will only be issued for fully registered presenters, e.g. an accepted article + full payment of the registration fees is required. Issuace of the visa will depend on a relevant official. In case the presenter will be denied the visa, a full refund will be made even after May 31. The organizers of the conference will not take any financial responsibilities of the potential costs of a delegate travelling to and during the stay in Estonia. Details on visa and consular issues, crossing the border, etc. are available at the MFA of Estonia.

Local Information

For questions regarding local organisation and local information, please email ICALP_LiCS_FSCD2024@taltech.ee.

Venue, Tallinn and Estonia

The conferences and workshops will be held in the Astra building on the campus of Tallinn University.

Astra building

The address is Narva mnt 29. This is a central location, within walking distance of the old town, and is easily accessible from the airport. There will be some disruption of local transport in Tallinn in the summer due to planned road upgrades. You can plan your trip here.

Conference participants may take the opporunity to extend their stay and visit Estonia. Estonia is truly magical in early July – there's plenty of sun and the evenings are long and warm. The portal visit estonia is a great source of tourist information.

For useful advice and inspiration on Tallinn’s top attractions, activities, events, and places to eat and drink, check out the city’s official tourism portal, visittallinn.ee, or follow @VisitTallinn on social media

.

July 9 Welcome Reception

Venue: Kadriorg Art Museum (housed in the Kadriorg Palace)

Address: Weizenbergi 37

Walk from the Conference Venue : 1,1 km / 16 minutes

Kadriorg Art Museum

July 10 Joint Banquet

Venue: Seaplane Harbour Museum

Address: Vesilennuki 6

Distance from the Conference Venue ca 3 km. Transfers will be provided from the conference venue.

Seaplane Harbour Museum

Accommodation

There are plenty of accommodation choices for all budgets in the area. We have an agreed discount rate for a limited number of rooms for conference participants at several local hotels:

  • Nordic Hotel Forum, (4* superior), Viru väljak 3, which is 15 minutes walk or a 3 minute tram ride from the conference location. Nordic Hotel Forum is a 4 star superior hotel in the prime location in Tallinn that has recently completed a full renovation to the entire hotel. The hotel offers spacious and elegant hotel rooms and a Leisure Centre on the 8th floor with magnificent views over the historic Old Town of Tallinn. The price includes buffet breakfast, free WiFi and use of hotel’s leisure centre on the top floor with fully equipped gym, indoor pool and saunas. Book here.

  • Kalev Spa Hotel and Water Park, (4*), Aia St 18, 20 minutes walk from the conference venue and accessible by Bus Line 8, stop Ahtri to Uus-Sadama. Located near the historic Old Town and the culturally vibrant seashore area. Perfect for both leisure and business travellers looking to rejuvenate body and soul with the ultimate spa experience. Modern amenities, including luxurious spa facilities, indoor pools, and comfortable accommodation. Book here.

  • Radisson Park Inn Central, (3*), Narva Rd 7c, 10 minutes walk from conference venue or easily accesssible via tram. Located a 5-minute walk away from the medieval old town. The price includes breakfast and free Wi-Fi. Well accessible from the Airport and Port of Tallinn. Book here.

  • Go Hotel Schnelli, (3*), Toompuiestee 37/1, 35 minutes walk to the conference venue or accessible in ~20 mins by public transport via Bus number 8, Stop Balti Jaam to Uus-Sadama. A budget-friendly hotel, located in the immediate vicinity of Tallinn's Old Town and the historic railway passenger terminal, Balti Jaam. Right next to the vibrant Kalamaja district and the Telliskivi area, known for its numerous popular restaurants and venues. A perfect location for evening hang-outs! Book here.

  • Hestia Hotel Barons, (4*), Suur-Karja 7, located in the Old Town, 25 minutes walk or a short tram ride to the conference venue. Book here.

  • Hestia Hotel Europa, (4*), Paadi St 5, 13 minute walk from the conference venue. Book here.

  • Hestia Hotel Seaport, (3*), Uus-Sadama St 23, 9 minute walk from the conference venue. Book here.

Getting there and local transport

Tallinn Airport offers direct flights to many European cities and is also well-connected to several regional hubs, with several daily flights to Helsiki, Warsaw, Stockholm and Frankfurt.

It is also possible to get to Tallinn by ferry from Helsiki (~2 hours, several daily connections), and by coach from Riga, Vilnius and other cities in the Baltic region.

While Tallinn has an excellent and affordable local transport network, please note that there are major road construction works going on in the Tallinn City centre, as a new tram line is being built. Check the routes/stops situation, how to get to your needed locations. There is relevant/current data available on the Tallinn website.

The conference is supported by the City of Tallinn. All the participants will get a free Tallinn public transportation pass. Relevant details will be sent in due course.

Tallinn logo

Some links you might find useful planning your trip: