-->

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

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
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
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.

An exception to this rule is when a participant has registered to a conference and would like to attend a workshop on the same day that the conference is scheduled -- in this case no additional fee is necessary for that day, but we ask that you email icalp_lics_fscd2024@taltech.ee with the details of your registration and the additional workshop(s) you would like to attend so that we can keep an accurate track of the numbers of participants.

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.

Programme

The table below shows an overview of the schedule for the three conferences and associated events. Click on a session for more detail.

  Monday 8 July Tuesday 9 July Wednesday 10 July Thursday 11 July Friday 12 July Saturday 13 July
Morning Silva Dawar Weirich Parter Elkind Ullrich
LiCS S1, S2 ICALP A1, A2 LiCS S4 ICALP B1, A6, A7, A8 LiCS S6 FSCD S1 ICALP B3, A12, A13 LiCS S8 FSCD S3 ICALP joint A/B session, A14, A15 FSCD S5 ICALP B5, A18, A19, A20 FSCD S7
Lunch   LiCS SC meeting ICALP SC meeting EATCS council meeting FSCD SC meeting    
Afternoon Simpson Nanongkai LiCS S5 ICALP B2, A9, A10, A11 LiCS S7 FSCD S2 ICALP best papers Escardó Kesner FSCD S8
LiCS S3  ICALP A3, A4, A5 LICS S9 FSCD S4 ICALP B4, A16, A17 FSCD S6 ICALP B6, A21, A22, A23
FSCD general meeting
Gödel prize Buss König-hofer EATCS award  
  Church award LiCS poster session  
LiCS ToT EATCS assembly
Presburger awards ICALP business meeting
Evening Welcome reception, Kadriorg Art Museum Joint banquet, Seaplane Harbour Museum  

The diagram below shows the timing of the workshops vis a vis the main conferences.

Workshop schedule

Detailed programme

Monday July 8 morning invited talk

TIME LICS INVITED TALK
  1
09:00 Alexandra Silva. TBA.
09:05
09:10
09:15 TBA
09:20
09:25
09:30
09:35
09:40
09:45
09:50
09:55

Monday July 8 morning regular session

TIME LICS S1 - MODAL, TEMPORAL, HIGHER ORDER AND COUNTING LOGICS LICS S2 - CATEGORY THEORY ICALP A1 - SPARSIFICATION AND CUTS ICALP A2 - COMPLEXITY THEORY 1
  1 Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
10:30 Bharat Adsul, Paul Gastin, Shantanu Kulkarni and Pascal Weil. An expressively complete local past propositional dynamic logic over Mazurkiewicz traces and its applications



Filippo Bonchi, Alessandro Di Giorgio, Nathan Haydon and Pawel Sobocinski. Diagrammatic Algebra of First-order Logic Yotam Kenneth and Robert Krauthgamer. Cut Sparsification and Succinct Representation of Submodular Hypergraphs Guy Goldberg. Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error
10:35
10:40
10:45 Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joel Ouaknine, Mihir Vahanwala and James Worrell. On the Decidability of Monadic Second-Order Logic with Arithmetic Predicates Masahito Hasegawa and Serge Lechenne. Braids, Twists, Trace and Duality in Combinatory Algebras
10:50    
10:55 Sanjeev Khanna, Aaron Putterman and Madhu Sudan. Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs Xin Li and Yan Zhong. Two-Source and Affine Non-Malleable Extractors for Small Entropy
11:00 Maximilian Pflueger, Johannes Marti and Egor V. Kostylev. A Characterisation Theorem for Two-Way Bisimulation-Invariant Monadic Least Fixpoint Logic Over Finite Structures Philip Saville and Hugo Paquet. Effectful semantics in bicategories: strong, commutative, and concurrent pseudomonads
11:05
11:10
11:15 Miroslav Chodil and Antonin Kucera. The Finite Satisfiability Problem for PCTL is Undecidable Nihil Shah and Amin Karamlou. Directed Containers That Do Not Distribute Over Distribution Monads    
11:20 Orestis Plevrakis, Seyoon Ragavan and S. Matthew Weinberg. On the cut-query complexity of approximating max-cut Hamed Hatami, Kaave Hosseini, Shachar Lovett and Anthony Ostuni. Refuting approaches to the log-rank conjecture for XOR functions
11:25
11:30 Piotr Ostropolski-Nalewaja and Tim Lyon. Decidability of Quasi-Dense Modal Logics Zeinab Galal and Jean-Simon Pacaud Lemay. Combining fixpoint and differentiation theory
11:35
11:40    
11:45 Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos and Alexandre Vigny. Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes Eric Finster, Alex Rice and Jamie Vicary. A Syntax for Strictly Associative and Unital ∞-Categories Agastya Vibhuti Jha and Akash Kumar. A Sublinear Time Tester for Max-Cut on Clusterable Graphs Vladimir Podolskii and Dmitrii Sluch. One-Way Communication Complexity of Partial XOR Functions
11:50
11:55
12:00 Sandra Kiefer and Daniel Neuen. Bounding the Weisfeiler--Leman Dimension via a Depth-Analysis of I/R-Trees Thorsten Wißmann and Stefan Milius. Initial Algebras Unchained - A Novel Initial Algebra Construction Formalized in Agda
12:05    
12:10 Surender Baswana and Koustav Bhanja. Vital Edges for (s,t)-mincut: Efficient Algorithms, Compact Structures, & Optimal Sensitivity Oracles Vikraman Arvind and Pushkar Joglekar. A Multivariate to Bivariate Reduction for Noncommutative   Rank and Related Results
12:15 Martin Grohe and Eran Rosenbluth. Are Targeted Messages More Effective? Mayuko Kori, Kazuki Watanabe, Jurriaan Rot and Shin-Ya Katsumata. Composing Codensity Bisimulations
12:20
12:25

Monday July 8 afternoon invited session

TIME LICS INVITED TUTORIAL ICALP INVITED TALK
    1
14:00 Alex Simpson. A tutorial on Sheaf Semantics. Danupon Nanongkai. Cross-Paradigm Graph Algorithms.
14:05 Abstract. Sheaf semantics provides a unifying framework for modelling intuitionistic, intermediate and classical logics. On the one hand, it seamlessly generalises several more specific forms of semantics such as the Kripke and Beth models of intuitionistic logic, as well as Cohen's forcing interpretation of classical logic (as used in his set-theoretic independence proofs). On the other, it naturally embraces some genuinely new types of model in which the underlying structure of "possible worlds" or "conditions" is given by a category rather than a partial order.

Starting with the Kripke semantics of intuitionistic logic, I shall build towards the goal of presenting and explaining sheaf semantics in its general form, together with example applications.

While the core technical content of the tutorial dates back some 50 years to the 1970s, the technology of sheaf semantics remains relevant today, with several current applications in logic in computer science. The aim is to make the tutorial intelligible to an audience who have some general knowledge of logic, but potentially no prior background in category theory. 
Abstract. A goal of the theory of graph algorithms is algorithmic techniques that enable computing devices to process graph data with little resources (time, space, communication overhead, etc.). This led to extensive studies of graph algorithms in various models of computation (sequential algorithms, distributed algorithms, streaming algorithms, etc.) by many sub-communities. "Cross-paradigm graph algorithms" is an effort to attack the same problem in many models of computation simultaneously, intending to generate new insights that may not emerge from the isolated viewpoint of a single model and to ultimately develop techniques that can be used to solve graph problems near-optimally across many models of computation.
In this talk, I will discuss some recent advances in graph algorithmic techniques for basic graph problems (e.g. minimum cut, shortest path, and maximum flow) in connection to this research program, especially some insights that led to cross-paradigm algorithms and to answering notorious open questions.

No background will be assumed from the audience beyond familiarity with textbook graph algorithms.
14:10
14:15
14:20
14:25
14:30
14:35
14:40
14:45
14:50
14:55
15:00  
15:05
15:10
15:15
15:20
15:25

Monday 8 July afternoon regular session

TIME LICS S3 - TOPICS IN LOGIC, REWRITING, AND PROOF THEORY ICALP A3 - APPROXIMATION ALGORITHMS I ICALP A4 - PARAMETRIZED ALGORITHMS I ICALP A5 - HARDNESS OF APPROXIMATION
  1 Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
16:00 Anupam Das and Abhishek De. A proof theory of right-linear (omega-)grammars via cyclic proofs Sami Davies, Benjamin Moseley and Heather Newman. Simultaneously Approximating All lp-norms in Correlation Clustering Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx and Roohani Sharma. Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification Noga Ron-Zewi and Elie Abboud. Finer-grained Reductions in Fine-grained Hardness of Approximation
16:05
16:10
16:15 Victor Arrial, Giulio Guerrieri and Delia Kesner. Genericity Through Stratification
16:20      
16:25 Niklas Schlomberg. An improved integrality gap for disjoint cycles in planar graphs Robert Ganian, Haiko Müller, Sebastian Ordyniak, Giacomo Paesani and Mateusz Rychlicki. A Tight Subexponential Algorithm for Two-Page Book Embedding Shuangle Li, Bingkai Lin and Yuwei Liu. Improved Lower Bounds for Approximating  Parameterized Nearest Codeword and Related  Problems under ETH
16:30 Chris Barrett, Willem Heijltjes and Daniel Castle.The Relational Machine Calculus
16:35
16:40
16:45 Fabian Mitterwallner, Aart Middeldorp and René Thiemann. Linear Termination is Undecidable      
16:50 Yu Chen and Zihan Tan. Lower Bounds on 0-Extension with Steiner Nodes Boris Klemz and Marie Diana Sieper. Constrained Level Planarity is FPT with Respect to the Vertex Cover Number Naoto Ohsaka. Alphabet Reduction for Reconfiguration Problems
16:55
17:00 Marie Kerjean and Pierre-Marie Pédrot. ∂ is for Dialectica
17:05
17:10      
17:15 Cameron Allett. Non-Elementary Compression of First-Order Proofs in Deep Inference Using Epsilon-Terms 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 Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach and Tuukka Korhonen. Two-sets cut-uncut on planar graphs Shuichi Hirahara and Naoto Ohsaka. Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
17:20
17:25
17:30 Raheleh Jalali and Stefan Hetzl. On the Completeness of Interpolation Algorithms
17:35      
17:40 Reut Levi, Talya Eden and Dana Ron. Testing Ck-freeness in bounded-arboricity graphs Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj and Ramanujan M. Sridharan. Parameterized Algorithms for Coordinated Motion Planning: Minimizing Energy Omkar Baraskar, Agrim Dewan, Chandan Saha and Pulkit Sinha. NP-hardness of testing equivalence to sparse polynomials and constant support polynomials
17:45 Søren Brinck Knudstorp. Relevant S is Undecidable
17:50
17:55

Tuesday 9 July morning invited talk

TIME ICALP INVITED TALK
  1
09:00 Anuj Dawar. Limits of Symmetric Computation. 
09:05
09:10 I survey recent work on symmetric computation.  A number of strands of work, from logic, circuit complexity, combinatorial optimization and other areas have converged on similar notions of symmetry in computation.  I talk about how methods for showing inexpressibility in logic translate into lower bounds for symmetric models of computation. I illustrate this with applications in algebraic circuit complexity.  I also discuss perspectives for future work. 
09:15
09:20
09:25
09:30
09:35
09:40
09:45
09:50
09:55

Tuesday 9 July morning regular session

TIME LICS S4 - TYPE THEORY ICALP B1 - AUTOMATA ICALP A6 - PARAMETRIZED ALGORITHMS II  ICALP A7 - CONTINUOUS OPTIMIZATION ICALP A8 - MIXED GRAPH PROBLEMS
  1 Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
 
10:30 Pierre-Marie Pédrot. “Upon This Quote I Will Build My Church Thesis” Arnaud Carayol and Lucien Charamond. The structure of trees in the pushdown hierarchy 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 Emile Anand, Jan van den Brand, Mehrdad Ghadiri and Daniel J Zhang. The Bit Complexity of Dynamic Algebraic Formulas and their Determinants Shyan Akmal, Virginia Vassilevska Williams and Nicole Wein. Detecting Disjoint Shortest Paths in Linear Time and More
10:35
10:40
10:45 Liron Cohen, Yannick Forster, Dominik Kirst, Bruno da Rocha Paiva and Vincent Rahli. Separating Markov's Principles
10:50        
10:55 Massimo Benerecetti, Laura Bozzelli, Fabio Mogavero and Adriano Peron. Automata-Theoretic Characterisations of Branching-Time Temporal Logics Baris Can Esmer, Jacob Focke, Dániel Marx and Paweł Rzążewski. Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness Li Chen and Mingquan Ye. High-Accuracy Multicommodity Flows via Iterative Refinement Mohammad Hossein Bateni, Laxman Dhulipala, Kishen Gowda, D Ellis Hershkowitz, Rajesh Jayaram and Jakub Łącki. It's Hard to HAC with Average Linkage!
11:00 Kirstin Peters and Nobuko Yoshida.  Separation and Encodability in Mixed Choice Multiparty Sessions
11:05
11:10
11:15 Christian Sattler and David Wärn. Natural numbers from integers        
11:20 Julian Dörfler and Christian Ikenmeyer. Functional Closure Properties of Finite N-weighted Automata Clément Dallard, Fedor Fomin, Petr Golovach, Tuukka Korhonen and Martin Milanič. Computing Tree Decompositions with Small Independence Number Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg and Sushant Sachdeva. Optimal Electrical Oblivious Routing on Expanders Mario Grobler, Stephanie Maaz, Nicole Megow, Amer Mouawad, Vijayaragunathan Ramamoorthi, Daniel Schmand and Sebastian Siebertz. Solution discovery via reconfiguration for problems in P
11:25
11:30 Samuel Mimram and Emile Oleon. Delooping cyclic groups with lens spaces in homotopy type theory
11:35
11:40        
11:45 Ulrik Buchholtz and Johannes Schipp von Branitz. Primitive Recursive Dependent Type Theory Paul Gallot, Sebastian Maneth, Keisuke Nakano and Charles Peyrat. Deciding Linear Height and Linear Size-to-Height Increase of Macro Tree Transducers Andreas Emil Feldmann and Michael Lampis. Parameterized Algorithms for Steiner Forest in Bounded Width Graphs Sushant Sachdeva, Anvith Thudi and Yibin Zhao. Better Sparsifiers for Directed Eulerian Graphs Johannes Meintrup, Frank Kammer, Konstantinos Dogeas, Thomas Erlebach and William K. Moses Jr.. Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
11:50
11:55
12:00 Pierre Cagne, Ulrik Buchholtz, Nicolai Kraus and Marc Bezem. On symmetries of spheres in univalent foundations
12:05        
12:10 C. Aiswarya, Amaldev Manuel and Saina Sunny. Edit Distance of Finite State Transducers Narek Bojikian and Stefan Kratsch. A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width Kevin Hua, Daniel Li, Jaewoo Park and Thatchaphol Saranurak. Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time Augusto Modanese and Yuichi Yoshida. Testing Spreading Behavior in Networks with Arbitrary Topologies
12:15 Emmanuel Hainry, Bruce Kapron, Jean-Yves Marion and Romain Péchoux. Declassification Policy for Program Complexity Analysis
12:20
12:25

Tuesday 9 July afternoon regular session

TIME LICS S5 - PROBABILISTIC AND QUANTUM COMPUTATION  ICALP B2 - INFINITE-STATE SYSTEMS ICALP A9 - MATROIDS ICALP A10 - COMPLEXITY THEORY II ICALP A11 - GRAPH THEORY
  1 Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
 
14:00 Alex Simpson. Equivalence and Conditional Independence in Atomic Sheaf Logic Sylvain Schmitz and Lia Schütze. On the Length of Strongly Monotone Descending Chains over ℕᵈ Kent Quanrud. Adaptive sparsification for matroid intersection Zhenjian Lu and Rahul Santhanam. Impagliazzo’s Worlds Through the Lens of Conditional Kolmogorov Complexity Andreas Björklund, Petteri Kaski and Jesper Nederlof. Another Hamiltonian cycle in bipartite Pfaffian graphs
14:05
14:10
14:15 John Li, Jon Aytac, Philip Johnson-Freyd, Amal Ahmed and Steven Holtzen. A Nominal Approach to Probabilistic Separation Logic
14:20        
14:25 George Kenison. The Threshold Problem for Hypergeometric Sequences with Quadratic Parameters 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 Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király and Shubhang Kulkarni. Splitting-off in Hypergraphs
14:30 Victor Blanchi and Hugo Paquet. Element-free probability distributions and random partitions
14:35
14:40
14:45 James Hefford and Matt Wilson. A Profunctorial Semantics for Quantum Supermaps        
14:50 Pavol Kebis, Florian Luca, Joel Ouaknine, Andrew Scoones and James Worrell. On Transcendence of Numbers Related to Sturmian and Arnoux-Rauzy Words Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki and Tamás Schwarcz. Problems on Group-labeled Matroid Bases Shalev Ben-David and Srijita Kundu. Oracle separation of QMA and QCMA with bounded adaptivity Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev and Maksim Zhukovskii. Tight Bounds on Adjacency Labels for Monotone Graph Classes
14:55
15:00 Pietro Di Gianantonio and Abbas Edalat. A Cartesian Closed Category for Random Variables
15:05
15:10        
15:15 Wojciech Różowski and Alexandra Silva. A Completeness Theorem for Probabilistic Regular Expressions Quentin Guilmant, Engel Lefaucheux, Joël Ouaknine and James Worell. The 2-Dimensional Constraint Loop Problem is Decidable Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh and Anannya Upasana. Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints Michaela Borzechowski, John Fearnley, Spencer Gordon, Rahul Savani, Patrick Schnider and Simon Weber. Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents Martin Grohe and Daniel Neuen. Isomorphism for Tournaments of Small Twin Width
15:20
15:25
15:30 Alexandre Clément, Noé Delorme and Simon Perdrix. Minimal Equational Theories for Quantum Circuits
15:35        
15:40 Raphael Douglas Giles, Vincent Jackson and Christine Rizkallah. T-Rex: Termination of Recursive Functions using Lexicographic Linear Combinations Ilan Doron-Arad, Ariel Kulik and Hadas Shachnai. Lower Bounds for Matroid Optimization Problems with a Linear Constraint Yiannis Giannakopoulos, Alexander Grosz and Themistoklis Melissourgos. On the Smoothed Complexity of Combinatorial Local Search  
15:45 Lorenzo Ciardo. Quantum advantage and CSP complexity
15:50
15:55

Tuesday 9 July afternoon special session

TIME AWARD TALKS
  1
16:30 Gödel Prize, laudatio Mikołaj Bojańczyk. Ryan Williams. Circuit Complexity from Circuit Analysis Algorithms 
16:35
16:40 I will explain on a personal level how I got into circuit complexity, and how I ended up proving circuit lower bounds like "NEXP does not have polynomial-size ACC circuits". In short, my path to circuit complexity lower bounds was circuitous, arising from the study of exact exponential time algorithms. I'll also speak about what else has been proved since the initial results, building on the various ideas that were introduced. 
16:45
16:50
16:55
17:00
17:05
17:10
17:15
17:20
17:25
17:30 LiCS ToT. Samson Abramsky and Bob Coecke. A categorical semantics of quantum protocols.
17:35
17:40 LiCS ToT. Andreas Podelski and Andrey Rybalchenko. Transition Invariants.
17:45
17:50 Presburger award. Justin Hsu. Logics for Separation in Randomized Programs.
17:55 Separation logic is a well-studied and practically impactful technique for reasoning about sharing and separation in programs with complex behavior, such as memory allocation or concurrency. In this talk, I'll give a brief tour of recent work generalizing these methods to randomized programs and probabilistic notions of separation.
18:00
18:05
18:10 Presburger award. Pravesh Kothari. TBA 
18:15 TBA
18:20
18:25

Wednesday 10 July morning invited talk

TIME LICS/ICALP JOINT INVITED TALK
  1
09:00 Stephanie Weirich. Tracking how dependently typed functions use their arguments.
09:05
09:10 Abstract. Dependent type systems extend the expressiveness of typed programming languages by allowing the result types of functions to depend on the values of their arguments. This feature allows programmers to design expressive interfaces and express application-specific properties about their code. However, many function arguments in these languages are purely specificational: they are there to provide information to the type checker, but they otherwise have no runtime significance. These arguments can be identified through various mechanisms, such as usage analysis (counting how many times functions use their parameters) or dependency analysis (tracking which results depend on which inputs). In this talk, I will show how dependent-type systems can integrate such analyses and make use of this information while checking programs.
09:15
09:20
09:25
09:30
09:35
09:40
09:45
09:50
09:55

Wednesday 10 July morning regular session

TIME LICS S6 - FIRST ORDER LOGIC FCSD S1 - HOMOTOPY TYPE THEORY ICALP B3 - SEMANTIC MODELLING AND VERIFICATION ICALP A12 - GRAPH DISTANCE PROBLEMS ICALP A13 - STRING AND MIXED PROBLEMS
  1 Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
   
10:30 Jakub Gajarský, Michał Pilipczuk, Szymon Toruńczyk, Giannos Stamoulis and Marek Sokołowski. Elementary first-order model checking for sparse graphs Maximilian Doré, Evan Cavallo and Anders Mörtberg. Automating Boundary Filling in Cubical Agda Cheng Zhang, Arthur Azevedo de Amorim and Marco Gaboardi. Domain Reasoning In TopKAT Shiri Chechik and Tianyi Zhang. Faster Algorithms for Dual-Failure Replacement Paths Itai Boneh, Shay Golan, Shay Mozes and Oren Weimann. Õptimal Dynamic Time Warping on Run-Length Encoded Strings
10:35
10:40
10:45 Tal Hershko and Maksim Zhukovskii. First order distinguishability of sparse random graphs
10:50      
10:55 Go Hashimoto, Daniel Gaina and Ionuț Țuțu. Forcing, Transition Algebras, and Calculi Shiri Chechik and Tianyi Zhang. Path-Reporting Distance Oracles with Logarithmic Stretch and Linear Size Panagiotis Charalampopoulos, Pawel Gawrychowski and Samah Ghazawi. Optimal Bounds for Distinct Quartics
11:00 Oskar Fiuk, Emanuel Kieronski and Vincent Michielini. On the complexity of Maslov’s class K Camil Champin, Samuel Mimram and Oleon Emile. Delooping generated groups in homotopy type theory
11:05
11:10
11:15 Danila Demin and Maksim Zhukovskii. First order complexity of finite random structures      
11:20 Wojciech Różowski. A Complete Quantitative Axiomatisation of Behavioural Distance of Regular Expressions Ariel Korin, Tsvi Kopelowitz and Liam Roditty. On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch Nick Fischer and Leo Wennmann. Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
11:25
11:30 Nadim Kasymov, Nadira Karimova and Bakh Khoussainov. Defining algorithmically presented structures in first order logic Niels van der Weide. Univalent Enriched Categories and the Enriched Rezk Completion
11:35
11:40      
11:45 Nathan Lhote, Vincent Michielini and Michał Skrzypczak. Uniformisation of Regular Relations in First-Order Logic with Two Variables Mikołaj Bojańczyk, Lê Thành Dũng Nguyên and Rafał Stefański. Function spaces for orbit-finite sets Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams, Nicole Wein and Zixuan Xu. Additive Spanner Lower Bounds with Optimal Inner Graph Structure Andrei Constantinescu, Pascal Lenzner, Rebecca Reiffenhäuser, Daniel Schmand and Giovanna Varricchio. Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games
11:50
11:55
12:00 Harry Vinall-Smeeth. From Quantifier Depth to Quantifier Number: Separating Structures with k Variables Nathan Corbyn, Lukas Heidemann, Nick Hu, Chiara Sarti, Calin Tataru and Jamie Vicary. homotopy.io: a proof assistant for finitely-presented globular n-categories
12:05      
12:10 Steffen van Bergerem, Roland Guttenberg, Sandra Kiefer, Corto Mascle, Nicolas Waldburger and Chana Weil-Kennedy. Verification of Population Protocols with Unordered Data Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay and Chen Wang. The Discrepancy of Shortest Paths Lucas Gretta and Eric Price. Sharp Noisy Binary Search with Monotonic Probabilities
12:15 Thomas Place and Marc Zeitoun. Dot-depth three, return of the J-class
12:20
12:25

Wednesday 10 July afternoon regular session

TIME LICS S7 - GAMES AND PROGRAM SEMANTICS FCSD S2 - CATEGORIES ICALP BEST PAPERS
  1 Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
14:00 Ali Asadi, Krishnendu Chatterjee, Jakub Svoboda and Raimundo Saona Urmeneta. Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary Weights Tao Gu, Jialu Bao, Justin Hsu, Alexandra Silva and Fabio Zanasi. A Categorical Approach to DIBI Models Ce Jin and Hongxun Wu. A Faster Algorithm for Pigeonhole Equal Sums
14:05
14:10
14:15 Noah Abou El Wafa and André Platzer. Complete Game Logic with Sabotage
14:20  
14:25 Kingsley Yung. Limits of Sequential Local Algorithms on the Random k-XORSAT Problem
14:30 Sougata Bose, Rasmus Ibsen-Jensen and Patrick Totzke. Bounded-Memory Strategies in Partial-Information Games Ralph Matthes, Kobe Wullaert and Benedikt Ahrens. Substitution for non-wellfounded syntax with binders through monoidal categories
14:35
14:40
14:45 Antonio Casares and Pierre Ohlmann. Positional ω-regular languages  
14:50 Yuda Feng and Shi Li. A Note on Approximating Weighted Nash Social Welfare with Additive Valuations
14:55
15:00 Yoàv Montacute and Glynn Winskel. Concurrent Games over Relational Structures: The Origin of Game Comonads Jean-Simon Lemay and Marie Kerjean. Laplace Distributors and Laplace Transformations for Differential Categories
15:05
15:10  
15:15 Vasileios Koutavas, Yu-Yang Lin and Nikos Tzevelekos. Pushdown Normal-Form Bisimulation: A Nominal Context-Free Approach to Program Equivalence Dmitry Chistikov, Alessio Mansutti and Mikhail Starchak. Integer Linear-Exponential Programming in NP by Quantifier Elimination
15:20
15:25
15:30 Pierre Clairambault and Simon Forest. An Analysis of Symmetry in Quantitative Semantics Benoît Guillemet, Matthieu Piquerez and Assia Mahboubi. Machine-Checked Categorical Diagrammatic Reasoning
15:35  
15:40 Roland Guttenberg. Flattability of Priority Vector Addition Systems
15:45 Sergey Goncharov, Stefan Milius, Stelios Tsampas and Henning Urbat. Bialgebraic Reasoning on Higher-order Program Equivalence
15:50
15:55

Wednesday 10 July afternoon special session

TIME LICS INVITED TUTORIAL FSCD INIVITED TALK AWARD TALKS & EATCS BUSINESS
      1
16:30 Sam Buss. Provability, totality, and complexity in bounded arithmetic. Bettina Könighofer. TBA. EATCS Award. Samson Abramsky. TBA.
16:35
16:40 Abstract. Bounded arithmetic is a collection of first-order theories that serves as a framework for studying problems in definability, probability, and complexity.  It brings together topics in provably total functions and TFNP functions, propositional proof complexity, and independence results.  This talk will survey results in this area, both old and new.
TBA TBA
16:45
16:50
16:55
17:00
17:05
17:10
17:15 Church Award. Thomas Erhard and Laurent Regnier. The differential lambda-calculus: from semantics to syntax 
17:20
17:25 Abstract. Linear logic, introduced by Girard in 1986, is a logical Curry-Howard account of linear algebra. It deeply relates the algebraic notion of linearity with computational linearity: a program is linear if it uses completely and exactly once its input. Linear logic also admits exponential modalities that allow to host non-linear proofs/morphisms corresponding roughly speaking to lambda-terms in the syntax and to analytic functions in the semantics. We will show how, in some models of linear logic, dereliction - the  rule that embeds linear functions into analytic ones - has a kind of inverse that should be understood as extracting from a non-linear morphism its "best linear approximant", that is as differentiation. From this  observation we derive a differential extension of linear logic which takes the form of new rules for the exponentials, symmetric to the usual ones. We will describe the corresponding extension of the lambda-calculus, the differential lambda-calculus, featuring  a syntactic operation of differentiation based on the usual laws of the differential calculus. We will present the Taylor expansion of lambda-terms which is based on an iterated use of these syntactic derivatives and provides a fine grain algebraic theory of finite approximations of programs, deeply connected with intersection types disciplines and game semantics. If time permits, we will discuss the analogies and differences with automated differentiation.
17:30  
17:35
17:40
17:45
17:50
17:55
18:00   EATCS General Assembly and ICALP business meeting.
18:05
18:10
18:15
18:20
18:25
18:30
18:35
18:40
18:45
18:50
18:55
19:00
19:05
19:10
19:15
19:20
19:25

Thursday 11 July morning invited talk

TIME ICALP INVITED TALK
  1
09:00 Merav Parter. Graphs Shortcuts: New Bounds and Algorithms.
09:05
09:10 Abstract. For an n-vertex digraph G=(V,E), a shortcut set is a (small) subset of edges H taken from the transitive closure of G that, when added to G guarantees that the diameter of GH is small. Shortcut sets, introduced by Thorup in 1993, have a wide range of applications in algorithm design, especially in the context of parallel, distributed and dynamic computation on directed graphs. A folklore result in this context shows that every n-vertex digraph admits a shortcut set of linear size (i.e., of O(n) edges) that reduces the diameter to Õ(√n). Despite extensive research over the years, the question of whether one can reduce the diameter to o(√n) with Õ(n) shortcut edges has been left open.

In this talk, I will present the first improved diameter-sparsity tradeoff for this problem, breaking the √n diameter barrier. Specifically, we show an O(nω)-time randomized algorithm for computing a linear shortcut set that reduces the diameter of the digraph to Õ(n). I also present time efficient algorithms for computing these shortcuts and explain the limitations of the current approaches. Finally, I will draw some connections between shortcuts and several forms of graph sparsification (e.g., reachability preservers, spanners).


Based on a joint work with Shimon Kogan (SODA 2022, ICALP 2022, FOCS 2022, SODA 2023).
09:15
09:20
09:25
09:30
09:35
09:40
09:45
09:50
09:55

Thursday 11 July morning regular session

TIME LICS S8 - VECTOR ADDITION SYSTEMS AND CSP FCSD S3 - PROOF THEORY AND LOGIC I ICALP A/B JOINT SESSION ICALP A14 - DYNAMIC GRAPH ALGORITHMS ICALP A15 -GEOMETRY
  1 Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
 
10:30 Eren Keskin and Roland Meyer.  On the Separability Problem of VASS Reachability Languages Pablo Donato. The Flower Calculus Manon Blanc and Olivier Bournez. The complexity of computing in continuous time: space complexity is precision Michal Dory, Sebastian Forster, Yasamin Nazari and Tijn de Vos. New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths 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
10:35
10:40
10:45 Michael Blondin, Alain Finkel, Piotr Hofman, Filip Mazowiecki and Philip Offtermatt. Soundness of reset workflow nets
10:50      
10:55 Yuya Uezato. Regular Expressions with Backreferences and Lookaheads Capture NLOG Yaowei Long and Yunfan Wang. Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer and Pavel Veselý. Fully-Scalable MPC Algorithms for Clustering in High Dimension
11:00 A. R. Balasubramanian. Decidability and Complexity of Decision Problems for Affine Continuous VASS G. A. Kavvos. Two-dimensional Kripke Semantics
11:05
11:10
11:15 Manuel Bodirsky, Žaneta Semanišinová and Carsten Lutz. The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems      
11:20 Aaron Potechin and Aaron Zhang. Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle Aditi Dudeja. Decremental Matching in General Weighted Graphs Pritam Acharya, Sujoy Bhore, Aaryan Gupta, Arindam Khan, Bratin Mondal and Andreas Wiese. Approximation Schemes for Geometric Knapsack for Packing Spheres and Fat Objects
11:25
11:30 Victor Dalmau and Jakub Opršal. Local consistency as a reduction between constraint satisfaction problems Junyoung Jang, Sophia Roshal, Frank Pfenning and Brigitte Pientka. Adjoint Natural Deduction
11:35
11:40      
11:45 Libor Barto, Silvia Butti, Alexandr Kazda, Caterina Viola and Stanislav Živný.  Algebraic Approach to Approximation Noel Arteche, Erfan Khaniki, Ján Pich and Rahul Santhanam. From Proof Complexity to Circuit Complexity via Interactive Protocols Adam Karczmarz and Marcin Smulewicz. Fully Dynamic Strongly Connected Components in Planar Digraphs Mónika Csikós and Nabil Mustafa. An Optimal Sparsification Lemma for Low-Crossing Matchings and  its Applications
11:50
11:55
12:00 Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin, Tamio-Vesa Nakajima and Stanislav Živný. 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise Ambrus Kaposi and Szumi Xie. Second-order generalised algebraic theories: signatures and first-order semantics
12:05      
12:10   Rajesh Jayaram, Jakub Łącki, Slobodan Mitrović, Krzysztof Onak and Piotr Sankowski. Dynamic PageRank: Algorithms and Lower Bounds Chiranjib Bhattacharyya, Ravindran Kannan and Amit Kumar. Random Separating Hyperplane Theorem and Learning Polytopes
12:15 Demian Banakh and Marcin Kozik.  Injective hardness conditions for PCSPs
12:20
12:25

Thursday 11 July afternoon invited talk

TIME LICS/FSCD JOINT INVITED TALK
  1
14:00 Martín Escardó. Topology in constructive mathematics and computer science.
14:05
14:10 Abstract. Topology provides a bridge between the finite nature of computers and the infinite nature of mathematical objects we want to compute with. The first part of the talk will review the history and main contributions of various protagonists, building on the pioneering insights of Brouwer, Kleene, Kreisel, Myhill & Shepherdson, Scott, Smyth, Voevodsky, among others. The second part of the talk will discuss my own work, old and recent, including the development of topological ideas in type theory, which serves both as a programming language and as a foundation of constructive mathematics. The talk will be addressed to a general audience, and will not assume familiarity with topology or type theory.
14:15
14:20
14:25
14:30
14:35
14:40
14:45
14:50
14:55

Thursday 11 July afternoon regular session

TIME LICS S9 - AUTOMATA THEORY FCSD S4 - PROOF THEORY AND LOGIC II ICALP B4 - CONSTRAINT SATISFACTION AND HOMOMORPHISMS ICALP A16 - STREAMING ALGORITHMS ICALP A17 - PARAMETERIZED ALGORITHMS III
  1 Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
 
15:30 Emmanuel Filiot, Ismaël Jecker, Christof Löding, Anca Muscholl, Gabriele Puppis and Sarah Winter. Finite-valued Streaming String Transducers Thiago Felicissimo and Théo Winterhalter. Impredicativity, Cumulativity and Product Covariance in the Logical Framework Dedukti Antoine Mottet, Tomáš Nagy and Michael Pinsker. An order out of nowhere: a new algorithm for infinite-domain CSPs Shiri Chechik, Doron Mukhtar and Tianyi Zhang. Streaming Edge Coloring with Subquadratic Palette Size 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
15:35
15:40
15:45 Udi Boker. Discounted-Sum Automata with Real-Valued Discount Factors
15:50      
15:55 Alberto Larrauri and Stanislav Živný. Solving promise equations over monoids and groups Soheil Behnezhad and Mohammad Saneian. Streaming Edge Coloring with Asymptotically Optimal Colors 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
16:00 Ismaël Jecker, Filip Mazowiecki and David Purser. Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata Victor Sannier and Patrick Baillot. A linear Type System for Lp-Metric Sensitivity Analysis (Best paper by junior researcher)
16:05
16:10
16:15 Pierre Ohlmann and Mikołaj Bojańczyk. Rank-decreasing transductions      
16:20 Jakub Rydval. Homogeneity and Homogenizability: Hard Problems for the Logic SNP Ce Jin, Michael Kapralov, Sepideh Mahabadi and Ali Vakilian. Streaming Algorithms for Connectivity Augmentation Marin Bougeret, Bart M. P. Jansen and Ignasi Sau. Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
16:25
16:30 Benedict Bunting and Andrzej Murawski. Contextual Equivalence for State and Control via Nested Data René Thiemann and Akihisa Yamada. A verified algorithm for deciding pattern completeness
16:35
16:40      
16:45 Laura Ciobanu and Georg Zetzsche. Slice closures of indexed languages and word equations with counting constraints Jakub Rydval, Žaneta Semanišinová and Michał Wrona. Identifying Tractable Quantified Temporal Constraints within Ord-Horn Yu Chen, Michael Kapralov, Mikhail Makarov and Davide Mazzali. On the Streaming Complexity of Expander Decomposition Klaus Heeger, Danny Hermelin, Matthias Mnich and Dvir Shabtay. No Polynomial Kernels for Knapsack
16:50
16:55
17:00 Ashwani Anand, Sylvain Schmitz, Lia Schütze and Georg Zetzsche. Verifying Unboundedness via Amalgamation Andrej Dudenhefner and Daniele Pautasso. Mechanized Subject Expansion in Uniform Intersection Types for Perpetual Reductions
17:05      
17:10 Benjamin Scheidt. On Homomorphism Indistinguishability and Hypertree Depth Prantar Ghosh and Manuel Stoeckl. Low-Memory Algorithms for Online Edge Coloring Somnath Bhattacharjee, Markus Bläser, Pranjal Dutta and Saswata Mukherjee. Exponential lower bounds via exponential sums
17:15 Arka Ghosh and Sławomir Lasota. Equivariant ideals of polynomials
17:20
17:25

Friday 12 July morning invited talk

TIME LICS/ICALP/FSCD JOINT INVITED TALK
  1
09:00 Edith Elkind. Group Fairness: Multiwinner Voting and Beyond.
09:05
09:10 Abstract. In multiwinner voting with approval ballots the agents are presented with a set of alternatives, each agent indicates which of these alternatives they approve, and the goal is to select a fixed-size subset of the alternatives, in a way that reflects the voters' preferences. This framework captures a variety of group decision-making scenarios, from choosing a list of speakers for an event to appointing a set of validators in a proof-of-stake blockchain. An important concern in many of these scenarios is group fairness: every sufficiently large group of agents with similar preferences should be represented in the winning set of alternatives. In this talk, we discuss how to formalise this idea and whether the resulting axioms can be satisfied by efficiently computable voting rules. We also discuss extensions of our framework to the more expressive setting of participatory budgeting, where the agents are presented with a slate of projects (which may have different costs) and the goal is to select a subset of projects subject to a budget constraint.
09:15
09:20
09:25
09:30
09:35
09:40
09:45
09:50
09:55

Friday 12 July morning regular session

TIME FCSD S5 - CONSTRUCTIVE MATH AND PROGRAMMING LANGUAGES ICALP B5 - FINITE MODELS, GRAPHS, AND COMPLEXITY ICALP A18 - ONLINE ALGORITHMS ICALP A19- APPROXIMATE COUNTING ICALP A20 - DATA STRUCTURES
  Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
   
10:30 Hugo Herbelin and Jad Koleilat. On the logical structure of some maximality and well-foundedness principles equivalent to choice principles Guillaume Theyssier. FO logic on cellular automata orbits equals MSO logic Ilan Doron and Seffi Naor. Non-Linear Paging Keren Censor-Hillel, Tomer Even and Virginia Vassilevska Williams. Fast Approximate Counting of Cycles Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo and Or Zamir. Optimal Non-Adaptive Cell Probe Dictionaries and Hashing
10:35
10:40
10:45
10:50        
10:55 Michael Benedikt, Chia-Hsuan Lu, Boris Motik and Tony Tan. Decidability of Graph Neural Networks via Logical Characterizations Yaniv Sadeh and Haim Kaplan. Caching Connections in Matchings Holger Dell, John Lapinskas and Kitty Meeks. Nearly optimal independence oracle algorithms for edge estimation in hypergraphs William Kuszmaul and Zoe Xi. Towards an Analysis of Quadratic Probing
11:00 Sohei Ito and Makoto Tatsuta. Representation of Peano Arithmetic in Separation Logic
11:05
11:10
11:15        
11:20 Amina Doumane, Samuel Humeau and Damien Pous. A finite presentation of treewidth at most 3 graphs Yossi Azar, Shahar Lewkowicz and Danny Vainstein. List Update with Delays or Time Windows Weiming Feng and Heng Guo. An FPRAS for two terminal reliability in directed acyclic graphs Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek and Sorrachai Yingchareonthawornchai. The Group Access Bounds for Binary Search Trees
11:25
11:30 Mateo Torres-Ruiz, Robin Piedeleu, Alexandra Silva and Fabio Zanasi. On Iteration in Discrete Probabilistic Programming
11:35
11:40        
11:45 Jakub Gajarský and Rose McCarty. On classes of bounded tree rank, their interpretations, and efficient sparsification Sariel Har-Peled, Elfarouk Harb and Vasilis Livanos. Oracle-Augmented Prophet Inequalities Konrad Anand, Weiming Feng, Graham Freifeld, Heng Guo and Jiaheng Wang. Approximate counting for spin systems in sub-quadratic time Djamal Belazzougui, Gregory Kucherov and Stefan Walzer. Robust Set Reconciliation
11:50
11:55
12:00 Kostia Chardonnet, Louis Lemonnier and Benoît Valiron. Semantics for a Turing-complete Reversible Programming Language with Inductive Types
12:05        
12:10 Christoph Haase, Shankara Naryananan Krishna, Khushraj Madnani, Om Swostik Mishra and Georg Zetzsche. An efficient quantifier elimination procedure for Presburger arithmetic Shaofeng H.-C. Jiang, Wenqian Wang, Yubo Zhang and Yuhao Zhang. Algorithms for the Generalized Poset Sorting Problem Charlie Carlson, Ewan Davies, Alexandra Kolla and Aditya Potukuchi. A spectral approach to approximately counting independent sets in dense bipartite graphs 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
12:15
12:20
12:25

Friday 12 July afternoon invited talk

TIME FSCD INVITED TALK
  1
14:00 Delia Kesner. Reasoning about Properties of Call-by-Name and Call-by-Value in a Subsuming Framework.
14:05
14:10 Abstract. This talk explores how the well-established models of computation given by Call-by-Name (CBN) and Call-by-Value (CBV) can be encoded within a broader setting provided by a unifying framework called the dBang calculus.
We first introduce the dBang calculus, which subsumes (untyped and typed) CBN and CBV, both from a static and a dynamic perspective. We then explore various properties of these computational models, including type inhabitation, upper bounds and exact measures for evaluation lengths, meaningfulness,  and genericity. In all these cases, explained and discussed in the talk, the properties of CBN and CBV are subsumed/inherited from the corresponding counterparts within the dBang calculus.
14:15
14:20
14:25
14:30
14:35
14:40
14:45
14:50
14:55

Friday 12 July afternoon regular session

TIME FCSD S6 - COMBINATORICS ICALP B6 - GAMES AND VECTOR ADDITION SYSTEMS ICALP A21 - QUANTUM COMPUTING ICALP A22 - GAME THEORY ICALP A23 - APPROXIMATION ALGORITHMS II
  Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
     
15:30 Samson Abramsky, Serban Cercelescu and Carmen Maria Constantin. Commutation groups and state-independent contextuality Mohan Sai Teja Dantam and Richard Mayr. Finite-memory Strategies for Almost-sure Energy-MeanPayoff Objectives in MDPs
Maxime Cautrès, Nathan Claudet, Mehdi Mhalla, Simon Perdrix, Valentin Savin and Stéphan Thomassé. Vertex-minor universal graphs for generating entangled quantum subsystems Matan Gilboa. A Characterization of Complexity in Public Goods Games Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein and Amin Saberi. Sublinear Algorithms for TSP via Path Covers
15:35
15:40
15:45
15:50        
15:55 Bruno Loff and Mateusz Skomra. Smoothed analysis of deterministic discounted and mean-payoff games Eunou Lee and Ojas Parekh. An improved Quantum Max Cut approximation via Maximum Matching Soh Kumabe and Yuichi Yoshida. Lipschitz Continuous Allocations for Optimization Games Leonid Gurvits, Nathan Klein and Jonathan Leake. From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP
16:00 Mateus De Oliveira Oliveira and Farhad Vadiee. State Canonization and Early Pruning in Width-Based Automated Theorem Proving
16:05
16:10
16:15        
16:20 Rohan Acharya, Marcin Jurdziński and Aditya Prakash. Lookahead Games and Efficient Determinisation of History-Deterministic Büchi Automata Jan Olkowski, Dariusz Kowalski and Mohammad Hajiaghayi. Distributed fast crash-tolerant consensus with nearly-linear quantum communication Junjie Chen, Minming Li, Haifeng Xu and Song Zuo. Bayesian Calibrated Click-Through Auctions Sophia Heimann, Hung P. Hoang and Stefan Hougardy. The k-Opt algorithm for the Traveling Salesman Problem has exponential running time for k≥5
16:25
16:30 FSCD general meeting
16:35
16:40        
16:45 Yuxi Fu, Qizhe Yang and Yangluo Zheng. Improved Algorithm for Reachability in d-VASS Srnivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez and Carlos Palazuelos. Learning low-degree quantum objects Yasushi Kawase, Koichi Nishimura and Hanna Sumita. Minimizing Symmetric Convex Functions over Hybrid of Continuous and Discrete Convex Sets Yury Makarychev, Max Ovsiankin and Erasmo Tani. Approximation Algorithms for lp-Shortest Path and lp-Group Steiner Tree
16:50
16:55
17:00
17:05        
17:10 Pascal Baumann, Eren Keskin, Roland Meyer and Georg Zetzsche. Separability in Büchi Vass and Singly Non-Linear Systems of Inequalities Serge Gaspers and Jerry Zirui Li. Quantum Algorithms for Graph Coloring and other Partitioning, Covering, and Packing Problems Chung Shue Chen, Peter Keevash, Sean Kennedy, Élie de Panafieu and Adrian Vetta. Robot positioning using torus packing for multisets Shi Li, Chenyang Xu and Ruilong Zhang. Polylogarithmic Approximations for Robust s-t Path
17:15
17:20
17:25

Saturday 13 July morning invited talk

TIME FSCD INVITED TALK
  1
09:00 Sebastian Ullrich. Lean: Past, Present, and Future.
09:05
09:10 Abstract. The Lean programming language and theorem prover project is celebrating its tenth birthday this year, having been started by Leonardo de Moura at Microsoft Research and first released as Lean 0.1 in 2014. In this invited talk, I will review Lean’s history and unique features and discuss our roadmap for its bright future.
09:15
09:20
09:25
09:30
09:35
09:40
09:45
09:50
09:55

Saturday 13 July morning regular session

TIME FSCD S7 - REDUCTION STRATEGIES
  Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
10:30 Beniamino Accattoli and Adrienne Lancelot. Mirroring Call-by-Need, or Values Acting Silly
10:35
10:40
10:45
10:50
10:55
11:00 Beniamino Accattoli and Claudio Sacerdoti Coen. IMELL Cut Elimination with Linear Overhead
11:05
11:10
11:15
11:20
11:25
11:30 Małgorzata Biernacka, Dariusz Biernacki, Sergueï Lenglet and Alan Schmitt. Optimizing a Non-Deterministic Abstract Machine with Environments
11:35
11:40
11:45
11:50
11:55
12:00 Aloÿs Dufour and Damiano Mazza. Böhm and Taylor for All!
12:05
12:10
12:15
12:20
12:25

Saturday 13 July afternoon regular session

TIME FCSD S8 - TERM REWRITING
  Set number in cell B2 to 1 for Sunday as the first day of the week; 2 for Monday.
Sunday for Hebrew, US English, Canadian English
14:00 Salvador Lucas. Termination of Generalized Term Rewriting Systems
14:05
14:10
14:15
14:20
14:25
14:30 Franz Baader and Jürgen Giesl. On the Complexity of the Small Term Reachability Problem for Terminating Term Rewriting Systems
14:35
14:40
14:45
14:50
14:55
15:00 Teppei Saito and Nao Hirokawa. Simulating Dependency Pairs by Semantic Labeling
15:05
15:10
15:15
15:20
15:25
15:30 Takahito Aoto, Naoki Nishida and Jonas Schöpf. Equational Theories and Validity for Logically Constrained Term Rewriting
15:35
15:40
15:45
15:50
15:55

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: