Programme

The detailed programme for the conference is given below. A condensed version of the programme (without session-specific details) is available here.

Sessions and coffee breaks for the constituent conferences take place in the following locations:

ICALP: Windsor Building
PODC: Shilling Building
SPAA: Queens Building

Lunch is served in the Students’ Union building. You can refer to our map page for the locations of these buildings on the campus.

Show:

08:55–09:00
PODC

ApPLIED Opening Remarks

Shilling Building Lecture Theatre [stream] [qs]

Achour Mostefaoui and Matthieu Perrin
08:55–10:00
ICALP
Algorithmic Aspects of Temporal Graphs IX (Session 1)

Windsor 1-02
1. 08:55
  
  Opening and welcome
2. 09:00
  
  New approximations for temporal vertex cover on always star temporal graphs
  Sophia Heck (University of Vienna)
3. 09:30
  
  Temporal role colouring
  Ella Yates (University of Glasgow)
09:00–10:00
PODC/SPAA
Student Spotlight Workshop 2026 (Session 1)

Queens Building Lecture Theatre [stream] [qs]

Naama Ben-David (Technion), Hanna Komlós (Max Planck Institute for Informatics)

Abstract

This workshop will showcase student-led research through short talks and poster presentations, offering students a welcoming venue to share their ideas, receive feedback, and connect with the broader community early in their academic journeys. The program will feature a mix of published results, work currently under submission, and exciting research in progress on topics relevant to SPAA, PODC, and algorithms more broadly.

We especially encourage senior researchers, faculty, postdocs, and experienced community members to attend. By asking questions, offering perspective, and starting conversations, your presence can help students refine their ideas, build confidence, and feel more connected to the field.
1. 09:00
  
  Opening Remarks
2. 09:10
  
  Distributed Computability with Automata Theory
  Coutouly Yannis
3. 09:22
  
  Compress or Random: Bipartite Matching is in Catalytic Logspace, and more
  Aryan Agarwala
4. 09:34
  
  Distributed MIS Algorithms for Rational Agents using Games
  Nithin Salevemula
5. 9:46
  
  Toggle Tree: A New Data Structure for Efficient Parallel Graph Processing
  Xinjian Jiang
09:00–10:00
PODC

Efficient Randomized Shared Memory Primitives and Algorithms (ApPLIED Keynote)

Shilling Building Lecture Theatre [stream] [qs]

Philipp Woelfel, University of Calgary, Canada
09:00–10:00
ICALP

Quantum Constraint Satisfaction Problems (Arrival)

Windsor 0-04
09:05–09:10
ICALP

Infinity 2026 Welcome

Windsor 0-02
09:10–09:55
ICALP

Fine-Grained Complexity and Formal Languages (Infinity 2026)

Windsor 0-02

Henning Fernau

Abstract

In this talk, some basic ideas of fine-grained complexity are introduced. This includes the presentation of key hypotheses like (S)ETH, OVH, APSP and 3SUM. In the second part of the talk, we will explain how to base conclusions on these hypotheses for problems arising in formal languages, in particular, in automata theory and parsing.
09:55–10:00
ICALP

Introductions (Infinity 2026)

Windsor 0-02
10:00–10:30

Coffee Break (ICALP/PODC/SPAA)

Shilling/Windsor Building Foyers
10:30–12:30
PODC/SPAA
Student Spotlight Workshop 2026 (Session 2)

Queens Building Lecture Theatre [stream] [qs]

Naama Ben-David (Technion), Hanna Komlós (Max Planck Institute for Informatics)

Abstract

This workshop will showcase student-led research through short talks and poster presentations, offering students a welcoming venue to share their ideas, receive feedback, and connect with the broader community early in their academic journeys. The program will feature a mix of published results, work currently under submission, and exciting research in progress on topics relevant to SPAA, PODC, and algorithms more broadly.

We especially encourage senior researchers, faculty, postdocs, and experienced community members to attend. By asking questions, offering perspective, and starting conversations, your presence can help students refine their ideas, build confidence, and feel more connected to the field.
1. 10:30
  
  Synchronization in Anonymous Networks Under Arbitrary Dynamics
  Anya Chaturvedi
2. 10:42
  
  Consensus Time in 3-Majority and 2-Choices Is Determined by the Maximum Initial Opinion Density
  Niccolò D’Archivio
3. 10:54
  
  Safe Diameter-Free Consensus in Granular Synchrony
  Hadar Matlaw
4. 11:06
  
  TEE is not a Healer, TEE-Rex is
  Sadegh Keshavarzi
5. 11:18
  
  Break
6. 11:30
  
  History-Independent Concurrent Hash Tables
  Noa Schiller
7. 11:42
  
  Workload Informed Concurrent Priority Queue Design
  Olivia Grimes
8. 11:54
  
  Flexible Lock-Free Locks
  Yael Zak
9. 12:06
  
  Machine Verification of Concurrent Fast Arrays
  Evan Lucca
10. 12:18
  
  Concluding Remarks
10:30–12:30
PODC
Shared Memory, Consensus, Causality, and Distributed Systems (ApPLIED Session 1)

Shilling Building Lecture Theatre [stream] [qs]
1. 10:30
  
  Obfuscated Consensus
  James Aspnes, Shlomi Dolev, Amit Hendin
2. 10:50
  
  Analyzing Linearizability in Relativistic Distributed Systems
  Kahbod Aeini, Wojciech Golab
3. 11:10
  
  CHARISMA: Do You Read Me?
  Andria Trigeorgi, Stela Makri, Kyriacos Clerides, Andreas Hadjipieris, Panagiotis Charalambous, Ioannis Kyriakides, Efstathios Stavrakis, Nicolas Nicolaou
4. 11:30
  
  QUANTAS 2: An Abstract, Concrete and Byzantine Simulator
  Joseph Oglio, Mikhail Nesterenko
5. 11:50
  
  Invited Paper: Experimental Analysis of Distributed Agentic Large-Language Model Inference Architectures
  Kartik Padalkar, Vitor Jesus, Jose M. Alcaraz Calero
6. 12:10
  
  DScale: a Simulation Framework for Large-Scale Distributed Systems
  Konstantin Shprenger, Michael Anoprenko, Petr Kuznetsov
10:30–12:00
ICALP
Algorithmic Aspects of Temporal Graphs IX (Session 2)

Windsor 1-02
1. 10:30
  
  Journey planning in public transportation networks: An application of temporal graph reachability
  Jonas Sauer (University of Bonn)
2. 11:00
  
  On the hardness of finding temporally connected subgraphs of any size
  Nils Morawietz (University of Jena)
3. 11:30
  
  Enumerating spanners in temporal graphs
  Andrea Marino (University of Florence)
10:30–11:15
ICALP

Precise Complexity Analysis of Coverability in Vector Addition Systems (Infinity 2026)

Windsor 0-02

Henry Sinclair-Banks

Abstract

Coverability in Vector Addition Systems with States (VASS) is a well-known, well-studied, fundamental problem for infinite-state systems. In short, VASS can be seen as finite automata equipped with non-negative integer counters that can be incremented and decremented but cannot be zero-tested. Over the last few years, our understanding of the exact complexity of coverability in VASS has significantly improved. In this presentation, I will explain: (i) a conditionally optimal ETH-based lower bound on the time required to decide coverability in VASS with a non-fixed number of counters, (ii) a conditional lower bound on the time required to decide coverability in unary-encoded VASS with two counters, and (iii) the state-of-the-art complexity of coverability in binary-encoded VASS with one counter.
10:30–12:30
ICALP
Quantum Constraint Satisfaction Problems (Session 2)

Windsor 0-04
1. 10:30
  
  Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction (Invited)
  Lorenzo Ciardo
2. 11:30
  
  NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
  Prem Nigam Kar
3. 12:00
  
  Operator Satisfiability under Commutation-Group Constraints
  Jianwen Chen
11:25–12:15
ICALP
Spotlight talks (Infinity 2026)

Windsor 0-02
1. Fine-Grained Complexity of Ambiguity Problems on Automata
  Anita Dürr
2. A quick guide to the APSP conjecture
  Jakob Nogler
3. Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
  Mirza Redzic
4. Intersecting Dense Automata: Constructions, Complexity and Certificates
  Neha Rino
12:30–14:00

Lunch

Students' Union Building
14:00–15:00
SPAA

Parallel Spatial Data Structures

Queens Building Lecture Theatre [stream] [qs]

Yan Gu (University of California, Riverside), Ziyang Men (University of California, Riverside), Yihan Sun (University of California, Riverside)

Abstract

Spatial data structures are used to model the geometric relationships among real-world objects, typically in 2D or 3D. Many textbook data structures, such as kd-trees, quad/octrees, and R-trees/BVHs, are widely studied in sequential settings and extensively used in real-world applications. Among them, R-trees are generally considered the fastest for updates, while kd-trees perform the best for queries.

Surprisingly, efficiently adapting them to parallel settings has remained an open challenge for a long time. While this might be expected for updates, even how to efficiently construct these algorithms in parallel was previously unknown.

This talk will introduce our recent work at SIGMOD’25 and PPoPP’26, PSI-Lab (Parallel Spatial Index). It features highly parallel algorithms for both the construction and updates of all these spatial trees. Furthermore, it offers several interesting algorithmic insights that can generalize to a broader set of parallel data structures, such as our ongoing work on B-trees and learned indexes (which we will cover if time permits).

Building on these results, we will address the ultimate question: can these parallel data structures still leverage their strengths just like their sequential counterparts? We have designed rigorous benchmarks to evaluate them. At a high level, the advantages of these highly optimized parallel solutions largely align with their sequential versions, but we will share more interesting findings in the talk.

Prerequisite knowledge

Minimum prerequisite knowledge is needed. We would expect the audience to have basic knowledge about parallel algorithm design such as the work/span analysis.

Biography

Yan Gu is an Associate Professor in the Computer Science and Engineering (CSE) Department at UC Riverside. He completed his PhD at Carnegie Mellon University in 2018 and his Bachelor’s degree at Tsinghua University in 2012. Before joining UCR, he spent one year as a postdoc at MIT. His research interest lies in designing simple and efficient algorithms with strong theoretical guarantees and good practical performance. He is a recipient of the NSF CAREER Award and the Google Research Scholar Program in 2024. He has won the Best Paper Awards at PPoPP'23 and ESA'23, the Best Paper Runner-up at VLDB'23, and the Outstanding Paper Awards at SPAA'24 and SPAA'20, and Best paper Finalist in ICS'25.

Yihan Sun is an Associate Professor in the Computer Science and Engineering (CSE) Department at the University of California, Riverside (UCR). She received her Ph.D. degree from Carnegie Mellon University in 2019, advised by Guy Blelloch. Prior to that, she received her Bachelor’s degree in Computer Science from Tsinghua University in 2014.Her research interests include broad topics in the theory and practice of parallel computing, including algorithms, data structures, frameworks, implementations, programming tools and their applications. Much of her work aims at bridging the gap between theory and practice of parallel computing. She is a recipient of the NSF CAREER Award in 2023, and the Google Research Scholar program in 2024. Her work has won the Best Paper Awards at PPoPP'23 and ESA'23, and the Outstanding Paper Awards of SPAA'20 and SPAA'24, and Best paper Finalist in ICS'25.

Ziyang Men is a fourth-year Ph.D. candidate in Computer Science at the UC Riverside. His research interests lie in the design of efficient parallel algorithms and data structures with good theoretical and practical benefits. His current work focuses on parallel spatial indexes, such as kd-trees and R-trees, with results published in venues including SIGMOD, PPoPP, and SPAA. He received his Master's degree from the University of Copenhagen and dual Bachelor's degrees from the University of Electronic Science and Technology of China and the University of Glasgow.
14:00–15:00
ICALP
Algorithmic Aspects of Temporal Graphs IX (Session 3)

Windsor 1-02
1. 14:00
  
  Exploring temporal graphs
  Paul Bastide (University of Oxford)
2. 14:30
  
  Minimum temporal spanners in happy graphs
  Hendrik Molter (Hasso Plattner Institute)
14:00–15:00
PODC/SPAA
Grassroots Computing

Queens 170 [stream] [qs]

Idit Keidar (Technion), Andrew Lewis-Pye (London School of Economics and Political Science), Ehud Shapiro (Weizmann Institute of Science)
Abstract

At its conception, the Internet was welcomed as the great equaliser; today, it is a dominant source of inequality. The cause is architectural: the digital realm offers centralised/autocratic platforms (Facebook, X, Amazon, Uber) and decentralised/plutocratic ones (Bitcoin, Ethereum), but no egalitarian and democratic alternative. Grassroots computing aims to provide one.

A grassroots system consists of people and their smartphones, with no globally named servers. Grassroots software platforms are characterised by (1) having multiple independent instances (2) that may interact and coalesce into ever-larger instances, possibly a single global one. Almost all known global platforms are not grassroots: Centralised (one Facebook) and decentralised (one Bitcoin, DHT, IPFS) systems violate (1); permissioned consensus violates (2). Scuttlebutt is the one exception.

This tutorial presents the conceptual and formal foundations of grassroots computing and grassroots platforms, and how AI turns the scientific papers that describe them into working implementations.

Part 1 — Introduction: Grassroots and AI
- Why grassroots? What grassroots is? The grassroots vision. Realising the vision with AI.
Part 2 — Below consensus: volitional agents, grassroots social networks and currencies
- Defining grassroots: Transition systems, protocols, and properties of interleavings
- Volitional transactions: Specifying systems consisting of people and their machines
- Grassroots platforms that need no consensus: social networks and currencies.
- An AI discipline for coding grassroots platforms from scientific papers that describe them.
Part 3 — Grassroots consensus and constitutional governance
- Why digital democracy needs digital consensus
- Constitutional consensus for democratic governance
- Grassroots federation
Part 4 — Wrap up: How can you help?
- Open problems and where the computer science community can contribute.
Why this matters for PODC
- Covers core PODC areas: distributed algorithms, fault tolerance, consensus, cryptographic protocols, peer-to-peer systems, and mobile computing.
- Poses a foundational question: what can distributed systems achieve without global coordination or any global resource beyond the network?
- Byzantine-resilient grassroots consensus with proven communication-complexity bounds.
- Connects distributed-computing theory to emerging societal applications: digital democracy, financial inclusion, and sovereign communities.
Why this matters for SPAA
- Grassroot systems—people with smartphone and no named servers—offer a pure, symmetric, parallel, decentralised model of computation.
- An atomic multiagent transaction synchronises only the agents it touches; disjoint transactions run concurrently, with no global lock, clock, or consensus.
- Grassroots obliviousness is disjoint-access parallelism at the systems level: independent participants make progress without coordination.
- Agents are anonymous, asynchronous, and locally named, with no global clock and no globally-named server.
14:00–15:00
ICALP
Quantum Constraint Satisfaction Problems (Session 3)

Windsor 0-04
1. 14:00
  
  Satisfiability of commutative vs. non-commutative CSPs (Invited)
  Stanislav Živný
14:00–15:00
PODC

Relaxed Concurrent Data Structures (ApPLIED Keynote)

Shilling Building Lecture Theatre [stream] [qs]

Philippas Tsigas, Chalmers University of Technology, Sweden
14:05–14:50
ICALP

Fine-Grained Dichotomies for evaluating database queries (Infinity 2026)

Windsor 0-02

Nofar Carmeli

Abstract

Consider the task of evaluating queries over databases. We will start by considering a very simple class of queries: join queries, and a simple question: when can the query answers be enumerated with ideal time guarantees (linear preprocessing and constant delay)?

As time permits, we will progress into more expressive query classes (conjunctive queries and unions of conjunctive queries), and into more demanding query-answering tasks, such as allowing direct access to query answers (i.e., simulating a sorted array containing the answers), every time asking a similar question.

The answer to such a question is always a dichotomy: a condition on the query structure, an efficient query evaluation algorithm in case it is satisfied, and a conditional lower bound in case it is not.
15:00–15:30

Coffee Break (ICALP/PODC/SPAA)

Shilling/Windsor Building Foyers
15:20–16:05
ICALP

On The Fine Grained Complexity of Multi-Stack Reachability (Infinity 2026)

Windsor 0-02

Michael Wehar

Abstract

Determining whether there exists a string that is accepted by a given pushdown automaton (PDA) is referred to as the non-emptiness problem for pushdown automata. This is a classic problem that is complete for polynomial time. Attempts to prove an unconditional superlinear time complexity lower bound for this problem have been unsuccessful. However, an unconditional time complexity lower bound can be proven for the intersection non-emptiness problem for one PDA and multiple DFAs. We apply this result to show a lower bound for the non-emptiness problem for multi-stack pushdown automata with bounded phase switches (i.e. multi-stack PDAs where all stacks can push, but only one designated stack can pop per switch). In particular, for k phase switches, we prove a near-tight time complexity lower bound of n^{Θ(2^k)} where n is the number of states and k is the number of phase switches.
15:30–17:00
PODC/SPAA
Grassroots Computing

Queens 170 [stream] [qs]

Idit Keidar (Technion), Andrew Lewis-Pye (London School of Economics and Political Science), Ehud Shapiro (Weizmann Institute of Science)
Abstract

At its conception, the Internet was welcomed as the great equaliser; today, it is a dominant source of inequality. The cause is architectural: the digital realm offers centralised/autocratic platforms (Facebook, X, Amazon, Uber) and decentralised/plutocratic ones (Bitcoin, Ethereum), but no egalitarian and democratic alternative. Grassroots computing aims to provide one.

A grassroots system consists of people and their smartphones, with no globally named servers. Grassroots software platforms are characterised by (1) having multiple independent instances (2) that may interact and coalesce into ever-larger instances, possibly a single global one. Almost all known global platforms are not grassroots: Centralised (one Facebook) and decentralised (one Bitcoin, DHT, IPFS) systems violate (1); permissioned consensus violates (2). Scuttlebutt is the one exception.

This tutorial presents the conceptual and formal foundations of grassroots computing and grassroots platforms, and how AI turns the scientific papers that describe them into working implementations.

Part 1 — Introduction: Grassroots and AI
- Why grassroots? What grassroots is? The grassroots vision. Realising the vision with AI.
Part 2 — Below consensus: volitional agents, grassroots social networks and currencies
- Defining grassroots: Transition systems, protocols, and properties of interleavings
- Volitional transactions: Specifying systems consisting of people and their machines
- Grassroots platforms that need no consensus: social networks and currencies.
- An AI discipline for coding grassroots platforms from scientific papers that describe them.
Part 3 — Grassroots consensus and constitutional governance
- Why digital democracy needs digital consensus
- Constitutional consensus for democratic governance
- Grassroots federation
Part 4 — Wrap up: How can you help?
- Open problems and where the computer science community can contribute.
Why this matters for PODC
- Covers core PODC areas: distributed algorithms, fault tolerance, consensus, cryptographic protocols, peer-to-peer systems, and mobile computing.
- Poses a foundational question: what can distributed systems achieve without global coordination or any global resource beyond the network?
- Byzantine-resilient grassroots consensus with proven communication-complexity bounds.
- Connects distributed-computing theory to emerging societal applications: digital democracy, financial inclusion, and sovereign communities.
Why this matters for SPAA
- Grassroot systems—people with smartphone and no named servers—offer a pure, symmetric, parallel, decentralised model of computation.
- An atomic multiagent transaction synchronises only the agents it touches; disjoint transactions run concurrently, with no global lock, clock, or consensus.
- Grassroots obliviousness is disjoint-access parallelism at the systems level: independent participants make progress without coordination.
- Agents are anonymous, asynchronous, and locally named, with no global clock and no globally-named server.
15:30–16:30
PODC/SPAA

Student Spotlight Workshop 2026 (Poster Session)

Shilling Building Foyer

Naama Ben-David (Technion), Hanna Komlós (Max Planck Institute for Informatics)

Abstract

This workshop will showcase student-led research through short talks and poster presentations, offering students a welcoming venue to share their ideas, receive feedback, and connect with the broader community early in their academic journeys. The program will feature a mix of published results, work currently under submission, and exciting research in progress on topics relevant to SPAA, PODC, and algorithms more broadly.

We especially encourage senior researchers, faculty, postdocs, and experienced community members to attend. By asking questions, offering perspective, and starting conversations, your presence can help students refine their ideas, build confidence, and feel more connected to the field.
15:30–16:30
PODC
Data Structures, AI, and Cloud Verification (ApPLIED Session 2)

Shilling Building Lecture Theatre [stream] [qs]
1. 15:30
  
  Invited Paper: Relaxed Data Structures for Practical Parallelism: Survey and Design Recommendations
  Philippas Tsigas, Kåre von Geijer
2. 15:40
  
  Invited Paper: A Verifiable and Adaptive Federated Learning Framework via Zero-Knowledge Proofs and Reputation-Weighted Blockchain
  Djamel Djenouri, Shahid Latif, Jawad Ahmad
3. 16:00
  
  A Formal Model of Multi-Controller Orchestration Systems in Cloud Management"
  Tengfei An, Maria Potop-Butucaru
4. 16:20
  
  Invited Paper: Quality Without Control: Evidence-Driven Software Quality Assurance for Cross-Domain Systems
  Stefan Tai, Maria Borges, Sebastian Werner, Mi-Jung Choi, Katinka Wolter
15:30–17:30
ICALP
Algorithmic Aspects of Temporal Graphs IX (Session 4)

Windsor 1-02
1. 15:30
  
  Tracking the evolution of dynamic networks with indirect sampling
  Antonio Fernández Anta (IMDEA Networks Institute)
2. 16:00
  
  Efficient approximate temporal triangle counting in streaming with predictions
  Fabio Vandin (University of Padova)
3. 16:30
  
  Data structures for temporal queries on dynamic temporal graphs
  Davide Bilò (University of L'Aquila)
4. 17:00
  
  Structural thresholds in doubly random temporal graphs
  Henry Austin (Durham University)
15:30–17:30
ICALP

Infinity 2026 (Session 4)
15:30–17:30
ICALP
Quantum Constraint Satisfaction Problems (Session 4)

Windsor 0-04
1. 15:30
  
  A Quantum Polynomial Freiman-Ruzsa Theorem
  Tom Gur
2. 16:30
  
  Three-qubit nonlocality paradoxes: beyond GHZ
  Nadish de Silva
16:15–17:00
ICALP

On the Fine-Grained Complexity of Concurrency Testing (Infinity 2026)

Windsor 0-02

Andreas Pavlogiannis

Abstract

Concurrency is ubiquitous and comes in various forms, from multi-threading inside a CPU to distributed systems, databases, and the internet of things. Testing whether a concurrent system adheres to its prescribed behavior is a natural algorithmic task, and a de-facto practice among researchers and system developers. In this talk, we will overview the algorithmic complexity of testing various systems and properties, through the fine-grained lens. This is a rich landscape, even more so since concurrent systems exhibit natural syntactic parameters, such as the number of communicating processes, the number of shared objects, etc. We will also study concurrency testing from the perspective of modern weak memory, whereby a concurrent system is allowed to exhibit complex and often counter-intuitive behaviors that escape the standard interleaving view. The plethora of weak memory models provides a fertile ground for fun and interesting fine-grained complexity questions of practical relevance, some of which we will tackle in this talk.
16:30–18:00
PODC
A Celebration of Prasad Jayanti

Queens Building Lecture Theatre [stream] [qs]
1. 16:30
  
  Opening
  Panagiota Fatourou
2. 16:33
  
  Optimal Snapshots & F-Arrays: Two papers by Prasad Jayanti that influenced my research
  Panagiota Fatourou
3. 16:48
  
  Adaptive Snapshot Algorithms
  Philipp Woelfel
4. 17:03
  
  Efficient and practical constructions of LL/SC variables
  Srdjan Petrovic
5. 17:18
  
  Mutual Exclusion
  Siddhartha Jayanti
6. 17:33
  
  Lessons from Prasad
  Eric Ruppert
7. 17:47
  
  Personal Reflections & Videos
16:50–17:30
PODC
Decentralized Services, Time, and Byzantine Communication (ApPLIED Session 3)

Shilling Building Lecture Theatre [stream] [qs]
1. 16:50
  
  Invited Paper: Composable Autonomic Offerings for Decentralized Service Provisioning in the Computing Continuum
  Ildefons Magrans de Abril, Boris Sedlak, Victor Casamayor Pujol, Schahram Dustdar
2. 17:10
  
  Byzantine Reliable Broadcast with Causal Ordering
  Mariarosaria Barbaraci, Christian Cachin
3. 17:20
  
  Convergence Analysis of Consensus-Based Tracking Algorithms for Logical Time Functions in Multi-Agent Networks
  Ivan Arkhipov, Evgeny Krokhalev, Oleg Granichin
17:10–17:55
ICALP

Online Orthogonal Vectors Revisited (Infinity 2026)

Windsor 0-02

Alexander Golovnev

Abstract

We prove new upper and lower bounds for the Online Orthogonal Vectors Problem (OnlineOV). In this problem, a preprocessing algorithm receives n vectors and constructs a data structure of size S. Subsequently, a query algorithm receives a vector q and, in time T, determines whether q is orthogonal to any of the input vectors.

Using a novel structure-versus-randomness decomposition, we design data structures that outperform all known constructions and refute a conjecture regarding the hardness of OnlineOV. On the lower-bound side, assuming the Non-uniform Strong Exponential Time Hypothesis, we prove arbitrarily large polynomial lower bounds on the space S required by any OnlineOV data structure with computationally unbounded preprocessing and sublinear query time.
18:00–19:30

Drinks Reception (ICALP/PODC/SPAA)

Windsor Building

Legend

APPLIED WORKSHOPS AATG IX SSW 2026 QCSP INFINITY BREAKS PSDS GRASSROOTS SOCIAL

08:35–08:40
SPAA

Opening (SPAA)

Queens Building Lecture Theatre [stream] [qs]
08:40–08:45
PODC

Opening (PODC)

Shilling Building Auditorium [stream] [qs]
08:40–10:00
SPAA
SPAA Session 1: Scheduling Algorithms

Queens Building Lecture Theatre, chaired by Phillip Gibbons (Carnegie Mellon University) [stream] [qs]
1. 08:40
  
  Faster EPTAS for Scheduling on Uniform Machines
  Klaus Jansen (Kiel University), Björn Schumacher (Kiel University), Roberto Solis-Oba (Western University)
2. 09:00
  
  Lossless Robustification of Packet Scheduling Algorithms
  Yossi Azar (Tel Aviv University), Or Vardi (Tel Aviv University)
3. 09:20
  
  Improved Approximation Algorithms for Parallel Task Scheduling and Multiple Cluster Scheduling
  Bennet Edler (Kiel University), Klaus Jansen (Kiel University), Felix Ohnesorge (Kiel University), Lis Pirotton (Kiel University)
4. 09:40
  
  Online Span Minimization for Flexible Uniform Jobs
  Mozhengfu Liu (Northwestern University), Samir Khuller (Northwestern University), Xueyan Tang (Nanyang Technological University)
08:45–10:00
PODC
PODC Session 1

Shilling Building Auditorium, chaired by Peter Davies-Peck [stream] [qs]
1. 08:45
  
  Deterministic Distributed Algorithms for Short Disjoint Paths
  Mohsen Ghaffari (MIT); Hsin-Hao Su (Boston College)
2. 09:05
  
  Girth Approximations in the CONGEST Model
  Shiri Chechik (Tel Aviv University); Gur Lifshitz (Tel-Aviv University); Doron Mukhtar (Tel Aviv University)
3. 09:25
  
  Distributed Treewidth Computation and Courcelle’s Theorem in the CONGEST Model
  Benjamín Jauregui (Universidad de Chile); Jason Li (CMU); Pedro Montealegre (Universidad Adolfo Ibáñez); Ioan Todinca (Université d’Orléans)
4. 09:45
  
  Brief Announcement: On Energy Complexity and Multi-Instance Computation in the Congested Clique
  Dominick Banasik, Varsha Dani (Rochester Institute of Technology)
5. 09:50
  
  Brief Announcement: Deterministic Edge Coloring with few Colors in CONGEST
  Tijn de Vos, Yannic Maus (TU Graz); Joakim Blikstad (Centrum Wiskunde & Informatica (CWI))
6. 09:55
  
  Brief Announcement: 2-Coloring Cycles in One Round
  Maxime Flin, Alesya Raevskaya, Ronja Stimpert, Jukka Suomela, Qingxin Yang (Aalto University)
09:00–10:00
ICALP

Algebraic Proof Systems - An Algebraic Approach to Analysing Proofs (ICALP Invited Talk)

Windsor Building Auditorium

Nutan Limaye (IT University of Copenhagen)

Abstract

Proof complexity aims to analyse the power of formal proof systems. Specifically, it is the study of the resources required to certify the truth of mathematical statements. It plays a crucial role in computational complexity and it has close connections to circuit complexity, automated reasoning, and mathematical logic.

A key direction in proof complexity is algebraic proof complexity, which analyses proof systems that use algebraic representations of logical formulas. These systems provide insight into the power and limitations of algebraic methods in proof complexity.

Among them, the Ideal Proof System (IPS), introduced by Grochow and Pitassi, is the focus of this talk. IPS represents proofs as algebraic circuits verifying the unsatisfiability of polynomial equations. In this talk, we will explore the IPS proof system, its connections to algebraic complexity, and recent developments in its study.

The talk is intended for the general ICALP audience and will assume only a basic background in theoretical computer science.
10:00–10:30

Coffee Break (ICALP/PODC/SPAA)

Shilling/Windsor Building Foyers
10:30–11:20
PODC
PODC Session 2

Shilling Building Auditorium, chaired by Naama Ben-David [stream] [qs]
1. 10:30
  
  Simple and Efficient Randomized Wait-Free Locks
  Kahbod Aeini, Dante Bencivenga (University of Calgary); George Giakkoupis (INRIA Rennes); Philipp Woelfel (University of Calgary, Canada)
2. 10:50
  
  Generalized and Reinitializable Concurrent Fast Arrays
  N. Efe Çekirge, Owen Chen, Siddhartha Jayanti, Evan Lucca (Dartmouth College)
3. 11:10
  
  Brief Announcement: A Space-Efficient Lock-Free Linear-Probing Hash Table
  Hagit Attiya (Technion); Rotem Oshman (Tel Aviv University and NYU); Noa Schiller (Tel Aviv University)
4. 11:15
  
  Brief Announcement: Computing Least Fixed Points with Overwrite Semantics in Parallel and Distributed Systems
  Vijay K. Garg (The University of Texas at Austin); Rohan Garg (Purdue University)
10:30–11:30
SPAA
SPAA Session 2: Parallel (Shared-Memory) Graph Algorithms

Queens Building Lecture Theatre, chaired by Gokarna Sharma (Kent State University) [stream] [qs]
1. 10:30
  
  A Practical Parallel Algorithm for Expander Decompositions
  Robin Münk (Technical University of Munich)
2. 10:50
  
  Efficient Parallel (Δ + 1)-Edge-Coloring
  Ariel Khuzman (Ben-Gurion University of the Negev), Michael Elkin (Ben-Gurion University of the Negev)
3. 11:10
  
  Parallel Spectral Graph Sparsification via Low Diameter Decompositions
  Yves Baumann (ETH Zurich), Gernot Zöcklein (ETH Zurich)
10:30–12:30
ICALP (Track A)
ICALP Session 1.1

Windsor 0-04, chaired by Nutan Limaye
1. 10:30
  
  VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
  Balagopal Komarath, Harshil Mittal, Jayalal Sarma
2. 10:54
  
  Proving Algebraic Independence in Zero-Knowledge
  Michael A. Forbes, Andrei Staicu
3. 11:18
  
  Alternation Depth of Threshold Decision Lists
  Vladimir Podolskii, Morgan Prior
4. 11:42
  
  Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
  Susanna F. de Rezende, David Engström, Yassine Ghannane, Duri Andrea Janett, Artur Riazanov
5. 12:06
  
  Back in the Saddle: Toward Parallel Approximate Minimum-Cost Flow
  Aurelio Sulser, Rasmus Kyng
10:30–12:30
ICALP (Track A)
ICALP Session 1.2

Windsor 1-02/03, chaired by Sukanya Pandey
1. 10:30
  
  Tight Bounds for Feedback Vertex Set Parameterized by Clique-Width
  Narek Bojikian, Stefan Kratsch
2. 10:54
  
  Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
  Narek Bojikian, Alexander Firbas, Robert Ganian, Hung Hoang, Krisztina Szilagyi
3. 11:18
  
  Well-Quasi-Ordering Eulerian Digraphs: Bounded Carving Width
  Dario Giuliano Cavallaro, Stephan Kreutzer, Ken-ichi Kawarabayashi
4. 11:42
  
  Determining the Outerthickness of Graphs is NP-Hard
  Pin-Hsian Lee, Te-Cheng Liu, Meng-Tsung Tsai
5. 12:06
  
  Lower Bounds on Pure Dynamic Programming for Connectivity Problems on Graphs of Bounded Path-Width
  Kacper Kluk, Jesper Nederlof
10:30–12:30
ICALP (Track A)
ICALP Session 1.3

Windsor 1-04, chaired by Marek Sokołowski
1. 10:30
  
  Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
  Bernhard Haeupler, Antti Röyskö, Zhijun Zhang
2. 10:54
  
  Thin Trees for Near Minimum Cuts
  Nathan Klein, Neil Olver, Zi Song Yeoh
3. 11:18
  
  A Faster Directed Single-Source Shortest Path Algorithm
  Ran Duan, Xiao Mao, Xinkai Shu, Longhui Yin
4. 11:42
  
  Expander Decomposition with Almost Optimal Overhead
  Nikhil Bansal, Arun Jambulapati, Thatchaphol Saranurak
5. 12:06
  
  Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
  Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Nikos Parotsidis
10:30–12:30
ICALP (Track A)
ICALP Session 1.4

Windsor 1-05, chaired by Benjamin Aram Berendsohn
1. 10:30
  
  Preprocessed 3SUM for Unknown Universes with Subquadratic Space
  Yael Kirkpatrick, John Kuszmaul, Surya Mathialagan, Virginia Vassilevska Williams
2. 10:54
  
  Improved Time-Space Tradeoffs for 3SUM-Indexing
  Itai Dinur, Alexander Golovnev
3. 11:18
  
  On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
  Jeremy Ahrens Huang, Young Kun Ko, Chunhao Wang
4. 11:42
  
  Mind the Gap? Not for SVP Hardness under ETH!
  Divesh Aggarwal, Rishav Gupta, Aditya Morolia, Chuanqi Zhang
5. 12:06
  
  Persistence Meets Resistance: Doubling Down on Hardness
  Benedikt Kolbe, Tim Mayr
10:30–12:30
ICALP (Track B)
ICALP Session 1.5 (Transducers)

Windsor 0-02/03, chaired by Benedikt Pago, University of Cambridge
1. 10:30
  
  Expregular Functions
  Thomas Colcombet, Nathan Lhote, Pierre Ohlmann
2. 10:54
  
  Edit Distance of Finite-valued Transducers
  Prince Mathew, Saina Sunny
3. 11:18
  
  Transducers on Compressed Strings
  Mikolaj Bojanczyk, Markus Lohrey
4. 11:42
  
  Transducing Linear Decompositions of Tournaments
  Colin Geniet, Fatemeh Ghasemi, Mamadou Moustapha Kanté
5. 12:06
  
  From Sets to Points: Simplifying MSO Interpretations over Countable Chains
  Alexander Rabinovich
11:20–12:20
PODC
PODC Session 3

Shilling Building Auditorium, chaired by Isabella Ziccardi [stream] [qs]
1. 11:20
  
  Undecided State Dynamics with Many Opinions
  Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik (King’s College London); Nobutaka Shimizu (Institute of Science Tokyo); Takeharu Shiraga (Chuo University)
2. 11:40
  
  Fast Gossip-Based Rumor Spreading Using Small Messages
  Fabien Dufoulon (Lancaster University); William K. Moses Jr. (Durham University); Gopal Pandurangan (University of Houston)
3. 12:00
  
  Complementary Time–Space Tradeoff for Self-Stabilizing Leader Election
  Yuichi Sudo (Hosei University)
11:40–12:20
SPAA
SPAA Session 3: Brief Announcements: Fault Tolerance, Dispersion, and Consensus

Queens Building Lecture Theatre, chaired by Yihan Sun (University of California, Riverside) [stream] [qs]
1. 11:40
  
  Brief Announcement: Asynchronous Dispersion with Optimal Time Complexity
  Debasish Pattanayak (Indian Institute of Technology Indore), Ajay Kshemkalyani (University of Illinois at Chicago), Manish Kumar (Indian Institute of Technology Madras), Anisur Rahaman Molla (Indian Statistical Institute, Kolkata), Gokarna Sharma (Kent State University)
2. 11:50
  
  Brief Announcement: An Improved Lower Bound for Local Failover Routing on Directed Networks
  Erik van den Akker (TU Dortmund), Klaus-Tycho Foerster (TU Dortmund)
3. 12:00
  
  Brief Announcement: Byzantine Generals with Stuttering Madness
  Bo Pan (Sorbonne Université, CNRS, LIP6, Paris, France), Maria Potop-Butucaru (Sorbonne Université, CNRS, LIP6, Paris, France)
4. 12:10
  
  Brief Announcement: Discrete Incremental Voting - New Bounds for General Graphs and Expanders
  Petra Berenbrink (University of Hamburg), Colin Cooper (King's College London), Thorsten Götte (University of Hamburg), Lukas Hintze (University of Hamburg), Tomasz Radzik (King's College London)
12:30–14:00

Lunch

Students' Union Building
14:00–14:45
ICALP

Algorithmic Robust Statistics (Gödel Award)

Windsor Building Auditorium

Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, Alistair Stewart

Abstract

We discuss recent developments in the field of algorithmic robust statistics as initiated by the paper "Robust Estimators in High Dimensions without the Computational Intractability". We begin with the history and underpinnings of the field of robust statistics and explain why previous approaches have been computationally intractable. We then discuss the key ideas behind the recent innovations that broke these barriers. Finally, we will provide a brief overview of more recent developments in the field.
14:00–15:00
PODC
PODC Session 4

Shilling Building Auditorium, chaired by Sebastian Brandt [stream] [qs]
1. 14:00
  
  Informative Trains: A Memory-Efficient Journey to a Self-Stabilizing Leader Election Algorithm in Anonymous Graphs
  Lélia Blin (IRIF, Université Paris Cité); Sylvain Gay (IRIF, Université Paris Cité, École Normale Supérieure); Isabella Ziccardi (IRIF, CNRS, Université Paris Cité)
2. 14:20
  
  Early-Stabilizing Counting
  Christoph Lenzen (Aalto University); Julian Loss (Ruhr University Bochum)
3. 14:40
  
  Gradient Clock Synchronization with Practically Constant Local Skew
  Christoph Lenzen (CISPA Helmholtz Center for Information Security)
14:00–15:00
SPAA
SPAA Session 4: Concurrent Data Structures

Queens Building Lecture Theatre, chaired by Erez Petrank (Technion) [stream] [qs]
1. 14:00
  
  uSTM: A Lightweight and Efficient STM Supporting General Types and Deferred Aborts
  Zachary Kent (Carnegie Mellon University), Guy Blelloch (Carnegie Mellon University), André Costa (Carnegie Mellon University)
2. 14:20
  
  KDB: A Scalable Persistent Key-Value Store with Atomic Batches and Snapshots
  Tadeusz Kobus (Poznan University of Technology), Maciej Kokociński (Poznan University of Technology), Krzysztof Kortas (Poznan University of Technology), Paweł T. Wojciechowski (Poznan University of Technology)
3. 14:40
  
  Big Atomics: Non-Blocking Algorithms with a Direct Fast Path
  Guy Blelloch (Carnegie Mellon University), Daniel Anderson (Carnegie Mellon University), Zachary Kent (Carnegie Mellon University), Siddhartha Jayanti (Dartmouth College)
14:45–15:15
ICALP

Dimensionality, Metrics, and Compression: A Decade of Algorithmic Advances in Clustering (Presburger Award)

Windsor Building Auditorium

Vincent Cohen-Addad

Abstract

Clustering algorithms form the fundamental bedrock of unsupervised machine learning, enabling the extraction of meaningful structure from massive, unannotated datasets. Given a set of data elements, the objective is to partition the space such that intra-cluster similarities are maximized while inter-cluster relationships are minimized. Over the last decade, the theoretical understanding of these classic optimization objectives—specifically $k$-means, $k$-median, and correlation clustering—has undergone a significant transformation. This presentation navigates the algorithmic evolution of center-based and graph-based clustering over the past ten years.

The analysis begins by exploring the geometric structure of low-dimensional Euclidean clustering. Moving beyond low dimensions, the discussion introduces new primal-dual frameworks, such as nested quasi-independent sets and Lagrangian Multiplier Preserving (LMP) adaptations, which have recently improved long-standing approximation barriers for high-dimensional Euclidean and general metric k-means and k-median. Addressing the era of massive datasets, the presentation outlines a unified coreset framework that yields optimal bounds across diverse metric spaces,. Finally, the lecture concludes with advances in graph clustering, showcasing how Sherali-Adams relaxations, dynamic data structures, and combinatorial modifications have pushed the boundaries of the classic correlation clustering objective.
"
15:05–16:00
PODC
PODC Session 5

Shilling Building Auditorium, chaired by Gopal Pandurangan [stream] [qs]
1. 15:05
  
  Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
  Arnold Filtser, Orr Fischer (Bar-Ilan University)
2. 15:25
  
  Distributed Algorithms for Potential Problems
  Alkida Balliu, Thomas Boudier, Francesco d’Amore (Gran Sasso Science Institute); Fabian Kuhn (University of Freiburg); Dennis Olivetti (Gran Sasso Science Institute); Gustav Schmid (University of Freiburg); Jukka Suomela (Aalto University)
3. 15:45
  
  Brief Announcement: Exponential Quantum Advantage for Message Complexity in Distributed Algorithms
  Maël Luce (Nagoya University); Mathieu Roget (Université Aix-Marseille); Joseph Marchand (Ecole normale supérieure Paris-Saclay); François Le Gall (Nagoya University)
4. 15:50
  
  Brief Announcement: Distributed Statistical Zero-Knowledge Proofs via Sumcheck
  Benjamín Jauregui (Universidad de Chile & Université Paris Cité); Masayuki Miyamoto (University of Tsukuba)
5. 15:55
  
  Brief Announcement: Distributed Non-Interactive Zero-Knowledge Proofs
  Alex Bredariol Grilo (CNRS, Sorbonne Université); Ami Paz (LISN, CNRS, Paris-Saclay University); Mor Perry (The Academic College of Tel-Aviv-Yaffo)
15:05–16:05
SPAA
SPAA Session 5: Fault Tolerance in Distributed Systems

Queens Building Lecture Theatre, chaired by Hagit Attiya (Technion) [stream] [qs]
1. 15:05
  
  Asynchronous Verifiable Information Dispersal with Low Space and Communication Complexity
  Thomas Locher (DFINITY), Yvonne-Anne Pignolet (DFINITY)
2. 15:25
  
  Towards Reliable Broadcast with Optimal Communication and Round Complexity
  Thomas Locher (DFINITY), Victor Shoup (Category Labs)
3. 15:35
  
  Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
  Dariusz R. Kowalski (Augusta University), Jan Olkowski (Independent Researcher)
15:15–15:45
ICALP

Coffee Break (ICALP)

Windsor Building Foyer
15:45–17:45
ICALP (Track A)
ICALP Session 2.1

Windsor 0-04, chaired by Benedikt Kolbe
1. 15:45
  
  Touring a Sequence of Orthogonal Polygons
  Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist, Jeroen S.K. Lamme, Eunjin Oh, Yanheng Wang
2. 16:09
  
  Visibility Queries in Simple Polygons
  Sujoy Bhore, Chih-Hung Liu, Anurag Murty Naredla, Yakov Nekrich, Eunjin Oh, André van Renssen, Frank Staals, Haitao Wang, Jie Xue
3. 16:33
  
  Incremental k-Lowest Planes and Planar k-Nearest Neighbor with Optimal Query Time
  John Iacono, Yakov Nekrich, Martin P. Seybold
4. 16:57
  
  A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D
  Jan Erik Swiadek, Sampson Wong, Kevin Buchin, Maike Buchin
5. 17:21
  
  The Impossibility of Simultaneous Time and I/O Optimality for the Planar Maxima and Convex Hull Problems
  Peyman Afshani, Gerth Stølting Brodal, Nodari Sitchinava
15:45–17:45
ICALP (Track A)
ICALP Session 2.2

Windsor 1-02/03, chaired by Mikkel Thorup
1. 15:45
  
  Dynamic Rank, Basis and Matching
  Jan van den Brand, Vishal Kumar, Daniel Zhang
2. 16:09
  
  Incremental (k,z)-Clustering on Graphs
  Antonis Skarlatos, Sebastian Forster, Emilio Cruciani
3. 16:33
  
  Online Matroid Embeddings
  Andrés Cristi, Paul Duetting, Robert Kleinberg, Renato Paes Leme, Neel Patel
4. 16:57
  
  Competitive Bundle Trading
  Yossi Azar, Niv Buchbinder, Roie Levin, Or Vardi
5. 17:21
  
  Online Monotone Metric Embeddings
  Christian Coester, Yichen Huang
15:45–17:45
ICALP (Track A)
ICALP Session 2.3

Windsor 1-04, chaired by Sasha Golovnev
1. 15:45
  
  An Algorithmic Proof of Kruskal’s Tensor Uniqueness Theorem
  Vishwas Bhargava, Shiri Sivan, Leonard J. Schulman
2. 16:09
  
  Kronecker Scaling of Tensors with Applications to Arithmetic Circuits and Algorithms
  Andreas Björklund, Petteri Kaski, Tomohiro Koana, Jesper Nederlof
3. 16:33
  
  Algorithms for Finite Group Epimorphism Testing
  Joshua A. Grochow, Pranjal Srivastava, Dhara Thakkar
4. 16:57
  
  Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction
  Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
5. 17:21
  
  Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
  Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg, Mursalin Habib, Bernhard Haeupler, Karthik C. S., Michal Koucký
15:45–17:45
ICALP (Track A)
ICALP Session 2.4

Windsor Building Auditorium, chaired by David Saulpic
1. 15:45
  
  Hardness, Tractability and Density Thresholds of Finite Pinwheel Scheduling Variants
  Sotiris Kanellopoulos, Giorgos Mitropoulos, Christos Pergaminelis, Thanos Tolias
2. 16:09
  
  Optimal Parallel Basis Finding in Graphic and Related Matroids
  Sanjeev Khanna, Aaron Putterman, Junkai Song
3. 16:33
  
  Multiplicative Assignment with Upgrades
  Alexander Armbruster, Lars Rohwedder, Stefan Weltge, Andreas Wiese, Ruilong Zhang
4. 16:57
  
  Towards Tight Robust Coresets for k-Medians Clustering
  Lingxiao Huang, Zhenyu Jiang, Yi Li, Xuan Wu
5. 17:21
  
  Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs
  David Aleman Espinosa, Niklas Schlomberg
15:45–17:45
ICALP (Track B)
ICALP Session 2.5 (Constraint Satisfaction, Codes, and Semi-ring Semantics)

Windsor 0-02/03, chaired by Alex Rabinovich, Tel Aviv University
1. 15:45
  
  Approximating 1-in-3 Sat by Linearly Ordered Hypergraph 3-colouring is NP-hard
  Andrei Krokhin, Danny Vagnozzi
2. 16:09
  
  The Complexity of Finding Coset-generating Polymorphisms and the Promise Metaproblem
  Manuel Bodirsky, Armin Weiß
3. 16:33
  
  The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
  Manuel Bodirsky, Moritz Jahn, Matěj Konečný, Simon Knäuer, Paul Winkler
4. 16:57
  
  Gray Codes with Constant Delay and Constant Auxiliary Space
  Antoine Amarilli, Claire David, Nadime Francis, Victor Marsault, Mikael Monet, Yann Strozecki
5. 17:21
  
  Preservation Theorems in Semiring Semantics
  Sophie Brinke, Anuj Dawar, Erich Grädel, Benedikt Pago
16:00–16:25
PODC/SPAA

Coffee Break (PODC/SPAA)

Shilling Building Foyer
16:25–17:35
PODC/SPAA
Parallel Algorithm Engineering Reconsidered (Invited Talk)

Shilling Building Auditorium, chaired by Charles Leiserson (Massachusetts Institute of Technology) [stream] [qs]

Peter Sanders (Karlsruhe Institute of Technology)
Abstract

Algorithm engineering is a view on the methodology of algorithmic research. At its core is a feedback cycle of modeling,design, analysis, implementation, and experimental evaluation [1, 3]. At each stage, we learn new things about an algorithmic problem that drives the development of better solutions. This is inspired by the hypothesis-driven cycle of scientific discovery prevalent in the natural sciences [2]. The invited talk reflects on the role of algorithm engineering with particular focus on parallel computing. Modeling is particularly important there because no standard model has emerged after more than half a century of research on parallel algorithms. For example, MapReduce computations have become a popular high level theoretical model but their connection to the real world is an interesting question [4]. On the low-level end of this spectrum, we need models that enable extensive algorithm-hardware codesign needed for future energy-efficient AI hardware. On the design side, it emerges that we do not just need a single algorithm but rather a spectrum of solutions selected from a huge design space of possible algorithms. This spectrum can then cover a range of inputs and machines. To grasp this on the analysis side, we need to take constant factors into account and handle complex models. Implementation has moved from a simple transition stage to extensive performance engineering to take various kinds of parallelism into account, e.g., bits, SIMD, instructions, threads in hierarchies of caches, and multiple compute nodes. This can result in orders of magnitude performance differences, often outstripping asymptotic behavior. Experiments and the entire cycle are now in a revolutionary stage where AI assisted algorithm engineering can drive the cycle at unprecedented speed. As human researchers, we rapidly have to learn how to control it.

References
- [1] D. Bader, B. Moret, and P. Sanders. 2002. Algorithm Engineering for Parallel Computation. In Experimental Algorithmics — From Algorithm Design to Robust and Efficient Software. LNCS, Vol. 2547. Springer, 1–23.
- [2] K. R. Popper. 1934. Logik der Forschung. Springer. English Translation: The Logic of Scientific Discovery, Hutchinson, 1959.
- [3] P. Sanders. 2009. Algorithm Engineering– An Attempt at a Definition. In Efficient Algorithms. LNCS, Vol. 5760. Springer, 321–340.
- [4] Peter Sanders. 2020. Connecting MapReduce Computations to Realistic Machine Models. In IEEE Conference on Big Data. 84–93. doi:10.1109/BigData50022.2020. 9378039
17:45–19:15
PODC

PODC Business Meeting

Shilling Building Auditorium [stream] [qs]
17:45–19:15
SPAA

SPAA Business Meeting

Queens Building Lecture Theatre [stream] [qs]
19:30–21:30
ICALP

Banquet (ICALP)

Founders Square

Legend

SPAA PODC INVITED/AWARD TALK ICALP BREAKS BUSINESS MEETING SOCIAL

08:40–10:00
SPAA
SPAA Session 1: Parallel and (More) Concurrent Data Structures

Queens Building Lecture Theatre, chaired by Siddhartha Jayanti (Dartmouth College) [stream] [qs]
1. 08:40
  
  Parallel Metric Skip Lists and Nearest Neighbor Search
  Xiangyun Ding (University of California, Riverside), Rohin Garg (Massachusetts Institute of Technology), Yan Gu (University of California, Riverside), Yihan Sun (University of California, Riverside)
2. 09:00
  
  Fast Concurrent Primitives Despite Contention
  Michael A. Bender (Stony Brook University), Guy Blelloch (Carnegie Mellon University), Martin Farach-Colton (New York University), Yang Hu (Tsinghua University), Rob Johnson (VMware Research), Rotem Oshman (Tel-Aviv University and New York University), Renfei Zhou (Carnegie Mellon University)
3. 09:20
  
  Fast and Theoretically Efficient Batch-Parallel Link-Cut Trees, Euler Tour Trees, and Treaps
  Quinten De Man (University of Maryland), Laxman Dhulipala (University of Maryland)
4. 09:40
  
  CleanANN: Efficient and Robust Full Dynamism in Graph-based Approximate Nearest Neighbor Search
  Ziyu Zhang (Massachusetts Institute of Technology), Yuanhao Wei (University of British Columbia), Joshua Engels (Massachusetts Institute of Technology), Julian Shun (Massachusetts Institute of Technology)
08:40–10:00
PODC
PODC Session 6

Shilling Building Auditorium, chaired by Frederik Mallmann-Trenn [stream] [qs]
1. 08:40
  
  From Few to Many Faults: Optimal Adaptive Byzantine Agreement
  Andrei Constantinescu, Marc Dufay, Anton Paramonov, Roger Wattenhofer (ETH Zurich)
2. 09:00
  
  Reaching Univalency with Subquadratic Communication
  Andrew Lewis-Pye (London School of Economics)
3. 09:20
  
  Why Canonical-Round Algorithms Fail for Optimal Byzantine Resilience
  Hagit Attiya, Itay Flam (Technion); Jennifer Welch (TAMU)
4. 09:40
  
  Brief Announcement: Communication Efficient Byzantine Agreement with Predictions
  Muhammad Ayaz Dzulfikar, Seth Gilbert (National University of Singapore)
5. 09:45
  
  Brief Announcement: BumbleBee: Best-of-Both-Worlds MVBA with Optimal Communication, Latency and Resilience Tradeoffs
  Fatima Elsheimy (Yale University); Simon Kamp (Ruhr University Bochum)
6. 09:50
  
  Brief Announcement: What is Agreement About if not Common Knowledge?
  Or David, Yoram Moses (Technion)
7. 09:55
  
  Brief Announcement: Byzantine Machine Learning, MultiKrum and an Optimal Notion of Robustness
  Gilles Bareilles (École Polytechnique); Wassim Bouaziz (Mistral AI); Julien Fageot (EPFL); El-Mahdi El-Mhamdi (École Polytechnique)
09:00–10:00
ICALP

Decidability and Complexity Borders of Reachability Problems (ICALP Invited Talk)

Windsor Building Auditorium

Georg Zetzsche (MPI-SWS)

Abstract

Reachability problems are arguably one of the most fundamental type of decision problems in the area of infinite-state systems: Essentially every non-trivial decision problem involves solving reachability problems of one kind or another.

Because of this, reachability has continuously received attention since the very early days of automata theory. It therefore seems worthwhile to characterize the decidability and complexity borders of reachability problems. By this we mean results that consider a family of decision problems and describe precisely where, within this family, a decidability or complexity border lies.

The talk will focus on two such settings: One is about decidability, where we aim to describe the state spaces for which reachability is decidable. The other is about complexity, where we aim to describe which kinds of target sets permit polynomial-time algorithms.
10:00–10:30

Coffee Break (ICALP/PODC/SPAA)

Shilling/Windsor Building Foyers
10:25–11:25
SPAA
SPAA Session 2: Energy-Efficient Computing

Queens Building Lecture Theatre, chaired by Julian Shun (Massachusetts Institute of Technology) [stream] [qs]
1. 10:25
  
  Exponential Energy Savings in Local Distributed Graph Algorithms
  Mohsen Ghaffari (Massachusetts Institute of Technology), Zi Song Yeoh (Boston University)
2. 10:45
  
  Energy-Efficient Aggregation and Minimum-Degree Spanning Trees in Radio Networks
  Yi-Jun Chang (National University of Singapore), Yang Ze Guan (National University of Singapore)
3. 11:05
  
  Minimizing Total Flow Time in the Online Active-Time Scheduling Model
  Susanne Albers (Technische Universität München), Gorsha Wessel van der Heijden (Technische Universität München)
10:30–11:30
PODC

The Omega(D+sqrt(n)) Lower Bound Story of Distributed Algorithms (Dijkstra Prize Talk)

Gopal Pandurangan (University of Houston)
10:30–12:30
ICALP (Track A)
ICALP Session 3.1

Windsor 0-04, chaired by Loukas Georgiadis
1. 10:30
  
  Partially-Dynamic Maximum Flow in Dense Graphs
  Egor Kravchenko, Maximilian Probst
2. 10:54
  
  Dynamic Set Cover with Worst-Case Recourse
  Shay Solomon, Amitai Uzrad
3. 11:18
  
  Static to Dynamic Correlation Clustering
  Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, Hanwen Zhang
4. 11:42
  
  Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
  Sepehr Assadi, Helia Yazdanyar
5. 12:06
  
  Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
  Yibin Zhao
10:30–12:30
ICALP (Track A)
ICALP Session 3.2

Windsor 1-02/03, chaired by Kazuo Iwama
1. 10:30
  
  Permutation Patterns in Streams
  Benjamin Aram Berendsohn
2. 10:54
  
  On the Complexity of the Matching Problem of Regular Expressions with Backreferences
  Soh Kumabe, Yuya Uezato
3. 11:18
  
  Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
  Panagiotis Charalampopoulos, Taha El Ghazi, Jonas Ellert, Pawel Gawrychowski, Tatiana Starikovskaya
4. 11:42
  
  Compressing Suffix Trees by Path Decompositions
  Nicola Prezza, Travis Gagie, Ruben Becker, Davide Cenzato, Ragnar Groot Koerkamp, Sung-Hwan Kim, Giovanni Manzini
5. 12:06
  
  Random Access in Grammer-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
  Anouk Duyster, Tomasz Kociumaka
10:30–12:30
ICALP (Track A)
ICALP Session 3.3

Windsor 1-04, chaired by Jakub Kozik
1. 10:30
  
  Learning Multinomial Logits in O(n log n) Time
  Flavio Chierichetti, Mirko Giacchini, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi, Erasmo Tani, Andrew Tomkins
2. 10:54
  
  A Scalable and Unified Framework to Weighted Rank Aggregation
  Amir Carmel, Debarati Das, Tien Long Nguyen
3. 11:18
  
  Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
  Tian Bai, Fedor Fomin, Petr A. Golovach, Yash Hiren More, Simon Wietheger
4. 11:42
  
  Classification of Local Optimization Problems in Directed Cycles
  Thomas Boudier, Fabian Kuhn, Augusto Modanese, Ronja Stimpert, Jukka Suomela
5. 12:06
  
  Going beyond Twin-p? CSPs with Unbounded Domain and Few Variables
  Peter Jonsson, Victor Lagerkvist, Jorke de Vlas, Magnus Wahlstrom
10:30–12:30
ICALP (Track A)
ICALP Session 3.4

Windsor 1-05, chaired by Dhara Thakkar
1. 10:30
  
  Hiding, Shuffling, and Cycle Finding: Quantum Algorithms on Edge Lists
  Amin Shiraz Gilani, Daochen Wang, Pei Wu, Xingyu Zhou
2. 10:54
  
  The Compressed Oracle is a Worthy (Multiplicative) Adversary
  Sebastian Zur, Stacey Jeffery
3. 11:18
  
  Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer
  Qisheng Wang, Zhicheng Zhang
4. 11:42
  
  On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
  Sabee Grewal, Dorian Rudolph
5. 12:06
  
  Quantum Advantage in Proof Systems without Entanglement
  Krishna Agaram, Nick Spooner, Yuxi Zheng
10:30–12:30
ICALP (Track A)
ICALP Session 3.5

Windsor Building Auditorium, chaired by Thore Husfeldt
1. 10:30
  
  Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
  Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, Da Wei Zheng
2. 10:54
  
  Geometric Optimization Parameterized by Piercing Complexity
  Aritra Banik, Rajiv Raman, Saurabh Ray
3. 11:18
  
  Near-Optimal Dynamic Data Structures for Maximum Depth and Klee’s Measure of Boxes
  Sujoy Bhore, Subhash Suri, Jie Xue, Xiongxin Yang, Jiumu Zhu
4. 11:42
  
  Coordinated Motion Planning is FPT on Discretized Simple Polygons
  Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj
5. 12:06
  
  Plane Strong Connectivity Augmentation
  Stéphane Bessy, Daniel Goncalves, Amadeus Reinald, Dimitrios M. Thilikos
10:30–12:30
ICALP (Track B)
ICALP Session 3.6 (Advanced Automata Models)

Windsor 0-02/03, chaired by Manuel Bodirsky, TU Dresden
1. 10:30
  
  Set Automata and Limits of Decidability of Two-variable Logic on Data Words
  Shibashis Guha, Amaldev Manuel, S P Rishal
2. 10:54
  
  Scoped MSO, Register Automata, and Expressions: Equivalences over Data Words
  Radosław Piórkowski
3. 11:18
  
  Unambiguisability and Register Minimisation of Min-Plus Models
  Shaull Almagor, Guy Arbel, Sarai Sheinvald
4. 11:42
  
  Automata on S-adic Words
  Valérie Berthé, Toghrul Karimov, Mihir Vahanwala
5. 12:06
  
  The Role of Counting Quantifiers in Laminar Set Systems
  Rutger Campbell, Noleen Köhler
11:40–12:20
SPAA
SPAA Session 3: Brief Announcements: Performance Modeling, Analysis, and Optimization

Queens Building Lecture Theatre, chaired by Peter Sanders (Karlsruhe Institute of Technology) [stream] [qs]
1. __:__
  
  Brief Announcement: An Automatic Framework for High Performance Alternative Basis Fast Matrix Multiplication (Moved to Thursday Session 3)
  Niv Bruker (Hebrew University of Jerusalem), Oded Schwarz (Hebrew University of Jerusalem), Noa Vaknin (Hebrew University of Jerusalem)
2. 11:40
  
  Brief Announcement: An I/O-Efficient Parallel FFT for Heterogeneous Architectures via a Single Global Exchange
  Shina Guo (College of Computer Science and Artificial Intelligence, Fudan University), Weiguo Gao (School of Mathematics, School of Data Science, Fudan University), Yuan Tang (College of Computer Science and Artificial Intelligence, Fudan University)
3. 11:50
  
  Brief Announcement: PRESERVE: Prefetching Model Weights and KV-Cache in Distributed LLM Serving
  Ahmet Caner Yüzügüler (Huawei Research Zurich), Jiawei Zhuang (Huawei Research Zurich), Lukas Cavigelli (Huawei Research Zurich)
4. 12:00
  
  Brief Announcement: Tiered Memory Computation
  Marcos K. Aguilera (NVIDIA), Naama Ben-David (Technion), N. Efe Çekirge (Dartmouth College), Siddhartha Jayanti (Dartmouth College)
5. 12:10
  
  Brief Announcement: Energy-Time Trajectories: A Tool to Understand Complex Parallel Efficiency
  Peter M. Kogge (University of Notre Dame)
11:35–12:20
PODC
PODC Session 7

Shilling Building Auditorium, chaired by Avery Miller [stream] [qs]
1. 11:35
  
  Efficient Counting and Simulation in Content-Oblivious Rings
  Jérémie Chalopin (CNRS, Aix-Marseille université); Yi-Jun Chang (National University of Singapore); Giuseppe Antonio Di Luna (Sapienza University); Haoran Zhou (National University of Singapore)
2. 11:55
  
  Brief Announcement: Toward Uniform Content-Oblivious Leader Election on General Graphs
  Fabian Frei (MIT); Ran Gelles (Bar-Ilan University); Ahmed Ghazy (CISPA Helmholtz Center for Information Security); Alexandre Nolin (Télécom SudParis)
3. 12:00
  
  Distinct Gathering and the Virtue of Self-Consistency
  Fabian Frei (MIT); Koichi Wada (Hosei U. Japan)
12:30–14:00

Lunch

Students' Union Building
14:00–15:40
ICALP
ICALP Best Papers Session

Windsor Building Auditorium
1. 14:00
  
  Canonical labelling of random regular graphs (Best Paper, Track A)
  Mikhail Isaev, Tamás Makai, Brendan McKay, Paweł Prałat, Jane Tan, Maksim Zhukovskii
2. 14:25
  
  Recursive Jump Operators and Optimal Proof Systems (Best Student Paper, Track A)
  Fabian Egidy
3. 14:50
  
  Optimal Lower Bounds for Symmetric Modular Circuits (Best Paper, Track B)
  Benedikt Pago
4. 15:15
  
  Deciding DFA-Primality is NP-Hard (Best Student Paper, Track B)
  Daniel Alexander Spenner
14:00–15:30
PODC
PODC Session 8

Shilling Building Auditorium, chaired by Hagit Attiya [stream] [qs]
1. 14:00
  
  Nearly Quadratic Asynchronous Distributed Key Generation from Recursive Consensus
  Ittai Abraham (A16Z); Renas Bacho (CISPA Helmholtz Center for Information Security); Julian Loss (Ruhr University Bochum); Gilad Stern (Tel Aviv University, Israel)
2. 14:20
  
  Information-Theoretic Optimistic Verifiable Secret Sharing
  Chen-Da Liu-Zhang (Lucerne University of Applied Sciences and Arts); Martin Hirt, Emanuele Marsicano (ETH Zurich)
3. 14:40
  
  Balanced and Adaptively Secure Asynchronous Common Coin and Byzantine Agreement With Sub-Quadratic Communication
  Hanwen Feng, Tiancheng Mai, Qiang Tang (The University of Sydney)
4. 15:00
  
  Byzantine Consensus in the Partially Authenticated Setting
  Christoph Lenzen (Reykjavik University); Julian Loss (Ruhr University Bochum); Kecheng Shi (CISPA Helmholtz Center for Information Security); Benedikt Wagner (Ethereum Foundation)
5. 15:20
  
  Brief Announcement: Cryptographically Secure Domain Extension for Byzantine Agreement with Improved Round Complexity
  Ashish Choudhury, Madhav Natarajan H (IIIT Bangalore)
6. 15:25
  
  Brief Announcement: Subcubic Coin Tossing in Asynchrony without PKI
  Mose Mizrahi, Roger Wattenhofer (ETH Zurich)
14:10–15:30
SPAA
SPAA Session 4: Distributed Graph Algorithms

Queens Building Lecture Theatre, chaired by Yi-Jun Chang (National University of Singapore) [stream] [qs]
1. 14:10
  
  Distributed Dominating Set With Optimal Rounds and Message Size in Bounded Arboricity Graphs
  Sharareh Alipour (Tehran Institute for Advanced Studies (TeIAS), Khatam University), Ermiya Farokhnejad (University of Warwick)
2. 14:30
  
  Time-, Message- and Memory-Optimal Distributed Minimum Spanning Tree and Partwise Aggregation
  Michael Elkin (Ben-Gurion University of the Negev), Tanya Goldenfeld (Ben-Gurion University of the Negev)
3. 14:50
  
  Near-Optimal Bounds for Adversarial Wake-up in Distributed Networks
  Peter Robinson (Augusta University), Ming Ming Tan (Augusta University)
4. 15:10
  
  Deterministic Distance Approximation in MPC via Improved Hitting Sets
  Kyungjin Cho (TU Graz), Michal Dory (University of Haifa), Yannic Maus (TU Graz), Tijn de Vos (TU Graz)
15:30–16:00

Coffee Break
15:55–16:55
PODC
PODC Session 9

Shilling Building Auditorium, chaired by Yi-Jun Chang [stream] [qs]
1. 15:55
  
  New Hardness Results for the LOCAL Model via a Simple Self-Reduction
  Alkida Balliu, Filippo Casagrande, Francesco d’Amore, Dennis Olivetti (Gran Sasso Science Institute)
2. 16:15
  
  The Distributed Complexity Landscape on Trees Depends on the Knowledge About the Network Size
  Gustav Schmid (University of Freiburg); Alkida Balliu (Gran Sasso Science Institute); Fabian Kuhn (University of Freiburg); Dennis Olivetti (GSSI, L’Aquila, Italy); Sebastian Brandt (CISPA Helmholtz Center for Information Security); Timothe Picavet (LaBRI, Université de Bordeaux)
3. 16:35
  
  Brief Announcement: Is a LOCAL Algorithm Computable?
  Antonio Cruciani, Avinandan Das, Massimo Equi, Henrik Lievonen (Aalto University); Diep Luong-Le (Columbia University); Augusto Modanese (CISPA Helmholtz Center for Information Security); Jukka Suomela (Aalto University)
4. 16:40
  
  Brief Announcement: It Does Not Matter How You Define Locally Checkable Labelings
  Antonio Cruciani, Avinandan Das, Alesya Raevskaya, Jukka Suomela (Aalto University)
5. 16:45
  
  Brief Announcement: Fast Deterministic Distributed Degree Splitting
  Yannic Maus (TU Graz); Alexandre Nolin (Télécom SudParis); Florian Schager (TU Graz)
6. 16:50
  
  Brief Announcement: Sinkless Orientation Made Trivial
  Alexandre Nolin (Télécom SudParis)
16:00–16:10
ICALP

Distinguished Dissertation Awards

Windsor Building Auditorium
16:00–17:00
SPAA
SPAA Session 5: Paging and PIM Scheduling

Queens Building Lecture Theatre, chaired by Guy Blelloch (Carnegie Mellon University) [stream] [qs]
1. 16:00
  
  Tight Latency Guarantees for Weighted Caching with Delayed Hits
  Tomer Tsachor (Technion), Joseph (Seffi) Naor (Technion)
2. 16:20
  
  Non-Clairvoyant Scheduling for Processing-in-Memory
  Hongbo Kang (Tsinghua University), Yiwei Zhao (Carnegie Mellon University), Kunal Agrawal (Washington University in St. Louis), Yongwei Wu (Tsinghua University), Phillip B. Gibbons (Carnegie Mellon University)
3. 16:40
  
  The Local/Global Disk Problem: How to Use Shared High-Bandwidth Storage Economically
  Michael A. Bender (Stony Brook University), Philip Bille (DTU Compute), Martin Farach-Colton (New York University), Jeremy Fineman (Georgetown University), Inge Li Gørtz (DTU Compute), Michael Goodrich (University of California, Irvine), Hanna Komlós (Max Planck Institute for Informatics), Bradley C. Kuszmaul (RelationalAI), William Kuszmaul (Carnegie Mellon University), Rose Silver (Carnegie Mellon University), Todd Veldhuizen (RelationalAI), Renfei Zhou (Carnegie Mellon University)
16:10–17:00
ICALP

ML and TCS - A Personal Perspective (EATCS Award)

Windsor Building Auditorium

Yishay Mansour (Tel Aviv University)
17:00–19:00
ICALP

EATCS Assembly and ICALP Business Meeting

Windsor Building Auditorium
17:00–18:00
PODC
PODC Session 10

Shilling Building Auditorium, chaired by Fabien Dufoulon [stream] [qs]
1. 17:00
  
  Supervised Distributed Computing: Efficiency and Robustness under a Majority of Adversarial Workers
  John Augustine (Indian Institute of Technology Madras); Henning Hillebrandt (Paderborn University); Manish Kumar (Indian Institute of Technology Madras); Christian Scheideler, Julian Werthmann (Paderborn University)
2. 17:20
  
  The Task Completion Problem and its Application to Crash-Resilient Computation
  Orr Fischer, Ran Gelles (Bar-Ilan University)
3. 17:40
  
  A Separation Between Optimal Demand-Oblivious and Demand-Aware Network Throughput
  Matthias Bentert (TU Berlin); Chen Avin (Ben Gurion University of the Negev); Stefan Schmid (TU Berlin)
19:30–21:30
PODC/SPAA

Banquet (PODC/SPAA)

Founders Square

Legend

SPAA PODC INVITED/AWARD TALK ICALP BREAKS BUSINESS MEETING SOCIAL

08:40–10:00
SPAA
SPAA Session 1: Performance Analysis and Optimization for Modern Computing Systems

Queens Building Lecture Theatre, chaired by Bradley C. Kuszmaul (RelationalAI) [stream] [qs]
1. 08:40
  
  Reducing Off-Chip Prefetch Request Latency of LLC Hardware Prefetchers via Neural Prediction
  Zhengwei Huang (NUDT, Changsha, China), Wei Guo (NUDT, Changsha, China), Yongwen Wang (NUDT, Changsha, China)
2. 09:00
  
  PaHiS: A Hierarchical Synchronous Parallel Model for Irregular Workloads
  Petros Anastasiadis (Computing Systems Laboratory, Huawei Technologies, Zurich, Switzerland), Denis Jelovina (Computing Systems Laboratory, Huawei Technologies, Zurich, Switzerland), Albert-Jan N. Yzelman (Computing Systems Laboratory, Huawei Technologies, Zurich, Switzerland)
3. 09:20
  
  Design Tradeoffs in Backend Organization in Out-Of-Order RISC-V Processors
  Esther Alonso (University of Cantabria), Pablo Prieto (University of Cantabria), Pablo Abad (University of Cantabria), Valentin Puente (University of Cantabria)
4. 09:40
  
  Scheduler Augmentation: A Lightweight, Customizable, Low-Cost Profiling Technique for Fork-Join Parallel Programs
  Sam Westrick (New York University), Darshan Dinesh Kumar (New York University), Seong-Heon Jung (New York University)
08:40–10:00
PODC
PODC Session 11

Shilling Building Auditorium, chaired by Alexandre Nolin [stream] [qs]
1. 08:40
  
  Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
  Peter Davies-Peck (Durham University)
2. 09:00
  
  Meta-Theorems for Cuttable Distributed Problems
  Marthe Bonamy (LaBRI – CNRS, University of Bordeaux); Cyril Gavoille (LaBRI – University of Bordeaux); Avinandan Das, Jukka Suomela (Aalto University); Timothé Picavet (LaBRI – University of Bordeaux); Alexandra Wesolek (LaBRI – CNRS, University of Bordeaux)
3. 09:20
  
  Distributed Stochastic Graph Algorithms
  Keren Censor-Hillel (Technion); Aditi Dudeja (The Chinese University of Hong Kong, Shenzhen); George Giakkoupis (Inria)
4. 09:40
  
  Improved Bounds for Distributed Random Walks and Spanning Trees
  Gopal Pandurangan (University of Houston); Sriram V. Pemmaraju, Sourya Roy, Joshua Z. Sobel (University of Iowa)
09:00–10:00
ICALP

The Power of Subspace Designs: Optimal List Decoding, Proximity Gaps, and More (ICALP Invited Talk)

Windsor Building Auditorium

Venkatesan Guruswami (UC Berkeley)

Abstract

A subspace design is a collection of linear subspaces with a pseudorandomness property: no low-dimensional subspace has a large total intersection dimension with the collection. Subspace designs were originally introduced as a derandomization tool in coding theory, where they were used to precode algebraic codes and improve their list-decodability, and subsequently found several applications in linear-algebraic pseudorandomness.

Intriguingly, near-optimal constructions of subspace designs are themselves built from algebraic codes such as folded Reed-Solomon and multiplicity codes. Several recent works have revealed an exciting reverse connection: these codes, by virtue of their subspace design properties, admit optimal list-size bounds for list decoding, optimal proximity gaps, and random-like local behavior. The proximity-gap questions are particularly relevant to modern proof systems, including IOPs and SNARKs. I will also briefly mention a surprising recent appearance of subspace designs in the NC algorithm for bipartite perfect matching.

The talk will survey this circle of ideas and explain how subspace designs have become a powerful unifying tool for derandomization in coding theory and theoretical computer science.
10:00–10:30

Coffee Break (ICALP/PODC/SPAA)

Shilling/Windsor Building Foyers
10:30–11:20
PODC
PODC Session 12

Shilling Building Auditorium, chaired by Robin Vacus [stream] [qs]
1. 10:30
  
  Ranking Opinions with Few States in Population Protocols
  Tom-Lukas Breitkopf, Julien Dallot (TU Berlin); Antoine El-Hayek (Institute of Science and Technology Austria); Stefan Schmid (TU Berlin)
2. 10:50
  
  Order Statistics in Population Protocols via Simple Dynamics
  Niccolò D’Archivio (INRIA); Hind AlMahmoud (Kings College London); Emanuele Natale (CNRS, COATI, I3S, Université Côte d’Azur); Frederik Mallmann-Trenn (King’s College London)
3. 11:10
  
  Brief Announcement: DéjàVu: A Minimalistic Mechanism for Distributed Plurality Consensus
  Francesco d’Amore (Gran Sasso Science Institute); Niccolò D’Archivio (Inria); George Giakkoupis (Inria Rennes); Frédéric Giroire (CNRS/Université Côte d’Azur); Emanuele Natale (CNRS, COATI, I3S, Université Côte d’Azur)
4. 11:15
  
  Brief Announcement: Limit Laws for Consensus Protocols on the Complete Graph
  Julian Becker, Konstantinos Panagiotou (LMU Munich)
10:30–11:30
SPAA

SPAA Session 2: Lessons Learned from Four Decades of Parallel Computing (Parallel Computing Award Talk)

Queens Building Lecture Theatre, chaired by Michael A. Bender (Stony Brook University) [stream] [qs]

Phillip Gibbons (Carnegie Mellon University)

Abstract

In this keynote, I reflect on my four decades in parallel computing—from the early surge of parallel computer companies, through a decade of the field’s seeming irrelevance, to its resurgence with multicore architectures and its current acceleration in the era of GenAI. Drawing on years of work at the intersection of theory and systems, I will share lessons on the challenge and value of bridging these perspectives as technologies and workloads continue to evolve. Using examples from my own research, I will show that while the basic research strategy—choosing important problems and publishing in the right venues—remains sound, the ultimate impact of the work is often unpredictable and may take years to emerge. Similarly, one’s professional career can take unpredictable turns, as I will highlight through personal anecdotes of a career in both industry and academia.
10:30–12:30
ICALP (Track A)
ICALP Session 4.1

Windsor 0-04, chaired by Artur Czumaj
1. 10:30
  
  Relative Error Unateness Testing
  Xi Chen, Diptaksho Palit, Kabir Peshawaria, William Pires, Rocco A. Servedio, Yiding Zhang
2. 10:54
  
  Sublinear-Query Relative-Error Testing of Halfspaces
  Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
3. 11:18
  
  Testing Sparse Functions over the Reals
  Vipul Arora, Arnab Bhattacharyya, Philips George John, Sayantan Sen
4. 11:42
  
  Streaming Complexity Separations for Dense and Sparse Graphs
  Yang P. Liu, Hoai-An Nguyen, Noah G. Singer, David P. Woodruff
5. 12:06
  
  Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes
  Naomi Green-Maimon, Or Zamir
10:30–12:30
ICALP (Track A)
ICALP Session 4.2

Windsor 1-02/03, chaired by Magnús M. Halldórsson
1. 10:30
  
  On (In)approximability of MaxMin Independent Set Reconfiguration
  Hung Hoang, Naoto Ohsaka, Rin Saito, Yuma Tamura
2. 10:54
  
  New Convex Programming Technique for Nash Social Welfare and Scheduling
  Yuda Feng, Weijiang Hu, Shi Li
3. 11:18
  
  Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
  Lin Chen, Tingwei Hu, Yuchen Mao, Yong Chen, Lili Mei, An Zhang, Guangting Chen, Guochuan Zhang
4. 11:42
  
  The Dirichlet Mechanism for Rounding with Strong Negative Correlation, with Applications
  David Harris, George Z. Li, Nitya Raju, Renata Valieva
5. 12:06
  
  Hardness and Approximation for Coloring Digraphs
  Parinya Chalermsook, Pierre Charbit, Samuel Coulomb, Harmender Gahlawat, Felix Klingelhoefer, Alantha Newman, Chaoliang Tang
10:30–12:30
ICALP (Track A)
ICALP Session 4.3

Windsor 1-04, chaired by Augusto Modanese
1. 10:30
  
  Quantum Multi-Level Estimation of Functionals of Discrete Distributions
  Kean Chen, Minbo Gao, Tongyang Li, Qisheng Wang, Xinzhao Wang
2. 10:54
  
  How Hard is it to Verify a Classical Shadow?
  Georgios Karaiskos, Dorian Rudolph, Johannes Jakob Meyer, Jens Eisert, Sevag Gharibian
3. 11:18
  
  A Quantum Time-Space Tradeoff for Directed s-t Connectivity
  Stacey Jeffery, Galina Pass
4. 11:42
  
  Strict Hierarchy for Quantum Channel Certification to Unitary
  Kean Chen, Qisheng Wang, Zhicheng Zhang
5. 12:06
  
  Pseudo-Deterministic Quantum Algorithms
  Jiawei Li, Hugo Aaronson, Tom Gur
10:30–12:30
ICALP (Track A)
ICALP Session 4.4

Windsor 1-05, chaired by Shyan Akmal
1. 10:30
  
  Faster and Simpler Greedy Algorithm for k-Median and k-Means
  Max Dupre la Tour, David Saulpic
2. 10:54
  
  Counting Perfect Matchings and Hamiltonian Cycles Faster
  Baitian Li
3. 11:18
  
  Witness-Sensitive Detection of Induced Diamonds
  Keren Censor-Hillel, Tomer Even, Nathan Wallheimer, Virginia Vassilevska Williams
4. 11:42
  
  A Fine-Grained Dichotomy for the Center Problem on Gromov Hyperbolic Graphs
  Guillaume Ducoffe
5. 12:06
  
  Deterministic Monotone Min-Plus Product and Convolution
  Ce Jin, Jaewoo Park, Barna Saha, Yinzhan Xu
10:30–12:30
ICALP (Track A)
ICALP Session 4.5

Windsor Building Auditorium, chaired by Andrei Bulatov
1. 10:30
  
  Solving Random Planted CSPs below the n^{k/2} Threshold
  Arpon Basu, Jun-Ting Hsieh, Andrew D. Lin, Peter Manohar
2. 10:54
  
  When does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
  Timo Fritsch, Marvin Künnemann, Mirza Redžić, Julian Stieß
3. 11:18
  
  Faster Mixing for Triangulations: Breaking the Cheeger Barrier via Transport Flows
  Vedat Levi Alev, Daniel Frishberg, Michalis Sarantis, Prasad Tetali
4. 11:42
  
  Tight Bounds for Sampling q-Colorings via Coupling from the Past
  Tianxing Ding, Hongyang Liu, Yitong Yin, Can Zhou
5. 12:06
  
  Sampling Colorings with Fixed Color Class Sizes
  Aiya Kuchukova, Will Perkins, Xavier Povill
10:30–12:30
ICALP (Track B)
ICALP Session 4.6 (Language Theory)

Windsor 0-02/03, chaired by Mishel Carelli, CISPA
1. 10:30
  
  Exploring VASS Parameterized by Geometric Dimension
  Wojciech Czerwiński, Roland Guttenberg, Łukasz Orlikowski, Henry Sinclair-Banks, Yangluo Zheng
2. 10:54
  
  Shuffles of Context-free Languages Along Regular Trajectories
  Corentin Barloy, Michaël Cadilhac, Kyle Ockerlund
3. 11:18
  
  Out of Order Membership to Regular Languages
  Antoine Amarilli, Sebastien Labbe, Charles Paperman
4. 11:42
  
  Asymptotic Hausdorff and Language Similarity
  Dana Fisman, Gal Meirom
5. 12:06
  
  A Diagrammatic Axiomitisation of Behavioral Distance of Nondeterministic Processes
  Wojciech Różowski, Robin Piedeleu, Alexandra Silva, Fabio Zanasi
11:20–12:20
PODC
PODC Session 13

Shilling Building Auditorium, chaired by Faith Ellen [stream] [qs]
1. 11:20
  
  Impossibility Results for Strong Linearizability: The Difficulty of Consistent Refereeing
  Hagit Attiya (Technion); Armando Castañeda (Instituto de Matemáticas, Universidad Nacional Autónoma de México (UNAM)); Constantin Enea (Ecole Polytechnique, LIX)
2. 11:40
  
  Conflict-Freedom as a Progress Condition
  Petr Kuznetsov (Télécom Paris, Institut Polytechnique Paris); Pierre Sutra (Télécom SudParis, Institut Polytechnique de Paris); Guillermo Toyos-Marfurt (Télécom Paris, Institut Polytechnique de Paris)
3. 12:00
  
  Generalized Compare-and-Swap and Space-Efficient Universal Constructions for the Infinite-Arrival Model
  Vassos Hadzilacos, Myles Thiessen, Sam Toueg (University of Toronto)
11:40–12:30
SPAA
SPAA Session 3: Brief Announcements: Concurrency, Partitioning, and Scheduling

Queens Building Lecture Theatre, chaired by Yan Gu (University of California, Riverside) [stream] [qs]
1. 11:40
  
  Brief Announcement: QPID: A Scalable, Strict Concurrent Priority Queue
  Olivia Grimes (Lehigh University), Matthew Rodriguez (Commonwealth University - Bloomsburg), Ahmed Hassan (Lehigh University), Michael Spear (Lehigh University), Roberto Palmieri (Lehigh University)
2. 11:50
  
  Brief Announcement: Recyclable Optimistic-Traversal Data Structures
  Md Amit Hasan Arovi (The Pennsylvania State University), Ruslan Nikolaev (The Pennsylvania State University)
3. 12:00
  
  Brief Announcement: Direction-incentivized Spectral Partitioning for Acyclic Graphs
  Dimosthenis Pasadakis (Università della Svizzera italiana (USI)), Raphael S. Steiner (Huawei Research Center Zurich, Computing Systems Lab), Pál András Papp (Huawei Research Center Zurich, Computing Systems Lab), Toni Böhnlein (Huawei Research Center Zurich, Computing Systems Lab), Albert-Jan N. Yzelman (Huawei Research Center Zurich, Computing Systems Lab)
4. 12:10
  
  Brief Announcement: Scheduling Problems with Constrained Rejections
  Sami Davies (UC Berkeley and Relational AI), Venkatesan Guruswami (Simons Institute and UC Berkeley), Xuandi Ren (UC Berkeley)
5. 12:20
  
  Brief Announcement: An Automatic Framework for High Performance Alternative Basis Fast Matrix Multiplication (Moved from Wednesday Session 3)
  Niv Bruker (Hebrew University of Jerusalem), Oded Schwarz (Hebrew University of Jerusalem), Noa Vaknin (Hebrew University of Jerusalem)
12:30–14:00

Lunch

Students' Union Building
14:00–14:45
ICALP

From Logic to Standards (Church Award)

Windsor Building Auditorium

Pablo Barceló, Leonid Libkin, Wim Martens, Juan Reutter, Miguel Romero, Moshe Vardi, Domagoj Vrgoč

Abstract

Querying graph data is a well-established topic in both theoretical and applied database research. While its origins lie in foundational papers from the 1980s, the field underwent a seismic transformation about fifteen years ago. At that time, the property graph model took over the database industry, winning rapid adoption by leading software vendors and ultimately resulting in new international standards for graph query languages—both native (GQL) and embedded within SQL. Around then, we examined the theoretical challenges posed by this industry-led language design and sought to build a formal foundation for it. This talk tells the story of three papers that directly influenced these new standards, and outlines the new research directions they opened up.
14:00–15:05
PODC
PODC Session 14

Shilling Building Auditorium, chaired by Diana Ghinea [stream] [qs]
1. 14:00
  
  Forget-IT: Optimal Good-Case Latency For Information-Theoretic BFT
  Ittai Abraham (A16Z); Sourav Das (Category Labs); Yuval Efron (Ritual); Jovan Komatovic (Category Labs)
2. 14:20
  
  FEAT: Fair and Efficient Adversarial Transaction Ordering
  Tien Tuan Anh Dinh (Deakin University); Dakai Kang (University of California, Davis); Mohammad Sadoghi (University of California, Davis)
3. 14:40
  
  Fast Byzantine Total Order Broadcast
  Matteo Monti (HES-SO Valais-Wallis); Martina Camaioni (EPFL); Pierre-Louis Roman
4. 15:00
  
  Brief Announcement: Delay-Optimal Transaction Order Fairness
  Zhuo Cai (Hong Kong University of Science and Technology); Amir K. Goharshady (University of Oxford)
14:00–15:00
SPAA
SPAA Session 4: More Distributed Algorithms

Queens Building Lecture Theatre, chaired by MohammadTaghi Hajiaghayi (University of Maryland) [stream] [qs]
1. 14:00
  
  Non-Uniform Content-Oblivious Leader Election on Oriented Asynchronous Rings
  Jérémie Chalopin (CNRS, Aix-Marseille Université), Yi-Jun Chang (National University of Singapore), Lyuting Chen (National University of Singapore), Di Luna Giuseppe Antonio (University of Rome - Sapienza), Haoran Zhou (National University of Singapore)
2. 14:20
  
  Universal Deterministic Symmetry Breaking Between Anonymous Agents in Networks
  Bibhuti Das (Université du Québec en Outaouais, Canada), Andrzej Pelc (Université du Québec en Outaouais, Canada)
3. 14:40
  
  Composable Coresets for Fair Diversity Maximization
  Ali Ahmadvand (Sharif University of Technology), Mohammad Ansari (Sharif University of Technology), Mobin Razavi (Sharif University of Technology), Hamid Zarrabi-Zadeh (Sharif University of Technology)
14:45–15:15
ICALP

Algorithms for Differentially Private Estimation (Presburger Award)

Windsor Building Auditorium

Gautam Kamath

Abstract

I'll talk about algorithms for performing certain fundamental estimation tasks under differential privacy. A particular focus will be on computational efficiency and the multivariate setting. Unexpected connections with robust estimation will be emphasized.
15:10–16:15
PODC
PODC Session 15

Shilling Building Auditorium, chaired by Eric Ruppert [stream] [qs]
1. 15:10
  
  Distributed Renaming with Subquadratic Bits via Scalable Committee Election
  Sirui Bai, Xinyu Fu (Nanjing University); Yuyi Wang (CRRC Zhuzhou Institute & Tengen Intelligence Institute); Chaodong Zheng (Nanjing University)
2. 15:30
  
  Network-Agnostic Multidimensional Approximate Agreement with Optimal Resilience
  Diana Ghinea (Lucerne University of Applied Sciences and Arts); Darya Melnyk, Tijana Milentijević (TU Berlin)
3. 15:50
  
  Round and Resilience-Optimal Approximate Agreement on Trees and Block Graphs
  Marc Fuchs (University of Freiburg); Diana Ghinea (Lucerne University of Applied Sciences and Arts); Zahra Parsaeian (University of Freiburg); Joel Rybicki (Humboldt University of Berlin)
4. 16:10
  
  Brief Announcement: Amortized Asynchronous Byzantine Reliable Broadcast with Optimal Resilience
  Michael Yiqing Hu, Hong Yao Alvin Yan, Jialin Li (National University of Singapore)
15:15–16:15
SPAA
SPAA Session 5: Lower Bounds and Optimality

Queens Building Lecture Theatre, chaired by Nodari Sitchinava (University of Hawaii at Manoa) [stream] [qs]
1. 15:15
  
  Cell-Probe Lower Bounds for Data Structures in CRCW PRAM
  Peyman Afshani (Aarhus University), Magnus Christian Ring Merrild (Aarhus University)
2. 15:35
  
  Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices
  Hussam Al Daas (Rutherford Appleton Laboratory), Grey Ballard (Wake Forest University), Laura Grigori (École Polytechnique Fédérale de Lausanne), Md Taufique Hussain (Wake Forest University), Suraj Kumar (INRIA Lyon), Mohammad Marufur Rahman (Wake Forest University), Kathryn Rouse (Inmar Intelligence)
3. 15:55
  
  Near-Optimal Parallel Approximate Counting via Sampling
  David G. Harris (University of Maryland), Vladimir Kolmogorov (Institute of Science and Technology Austria), Hongyang Liu (Nanjing University), Yitong Yin (Nanjing University), Yiyao Zhang (Nanjing University)
15:15–15:45
ICALP

Coffee Break (ICALP)

Windsor Building Foyer
15:45–17:45
ICALP (Track A)
ICALP Session 5.1

Windsor 0-04, chaired by Peter Davies-Peck
1. 15:45
  
  Node-Weighted Triangles: Faster and Simpler
  Shyan Akmal, Nick Fischer
2. 16:09
  
  Colour Fault-Tolerant Distance Preservers: ~{O}ptimal Size in Conditionally ~{O}ptimal Time
  Merav Parter, Asaf Petruschka
3. 16:33
  
  Faster Weak Expander Decompositions and Approximate Max Flow
  Henry Fleischmann, Jason Li, George Z. Li
4. 16:57
  
  Faster Deterministic Streaming Vertex Coloring
  Hongyi Chen, Shiri Chechik, Tianyi Zhang
5. 17:21
  
  Faster Algorithms for (2k-1)-Stretch Distance Oracles
  Avi Kadria, Liam Roditty
15:45–17:45
ICALP (Track A)
ICALP Session 5.2

Windsor 1-02/03, chaired by Hanna Komlos
1. 15:45
  
  Online Steiner Forest with Recourse
  Yaowei Long, Sepideh Mahabadi, Sherry Sarkar, Jakub Tarnawski
2. 16:09
  
  Chasing Small Sets Optimally Against Adaptive Adversaries
  Christian Coester, Alexa Tudose
3. 16:33
  
  Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
  Michael Dinitz, Jeremy Fineman, Seeun William Umboh
4. 16:57
  
  Online Metric TSP: Beyond the \sqrt{n} Barrier
  Yossi Azar, Debmalya Panigrahi, Or Vardi
5. 17:21
  
  Randomized k-Server in Polynomial Time
  Christian Coester, Romain Cosson
15:45–17:45
ICALP (Track A)
ICALP Session 5.3

Windsor 1-04, chaired by Venkat Guruswami
1. 15:45
  
  Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors
  Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang
2. 16:09
  
  Tracing AG Codes: Toward Meeting the Gilbert-Varshamov Bound
  Noam Goldgraber, Gil Cohen, Dean Doron, Tomer Manket
3. 16:33
  
  Local Samplers for Product Distributions
  Jordan Horacsek, Chin Ho Lee, Igor Shinkar, Emanuele Viola, Renfei Zhou
4. 16:57
  
  A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
  Xudong Wu, Guangxu Yang, Penghui Yao
5. 17:21
  
  Equivalence Between Coding and Complexity Lower Bounds
  Jinqiao Hu, Zhenjian Lu, Igor C. Oliveira
15:45–17:45
ICALP (Track A)
ICALP Session 5.4

Windsor Building Auditorium, chaired by Daniel Vaz
1. 15:45
  
  A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover
  Yezhou Zhang, Amey Bhangale
2. 16:09
  
  On the Average-Case Performance of Greedy for Maximum Coverage
  Jason Chatzitheodorou, Eric Balkanski, Flore Sentenac
3. 16:33
  
  Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
  Anne Driemel, Jan Höckendorff, Ioannis Psarros, Christian Sohler, Di Yue
4. 16:57
  
  A 9/4-Approximation for Directed Feedback Vertex Sets in Quasi-Transitive Digraphs
  Ebrahim Ghorbani, Matthias Mnich
5. 17:21
  
  Tight Regret Bounds for Fixed-Price Bilateral Trade
  Houshuang Chen, Yaonan Jin, Pinyan Lu, Chihao Zhang
15:45–17:45
ICALP (Track B)
ICALP Session 5.5 (Circuits and Real Analysis)

Windsor 0-02/03, chaired by Michael Cadilhac, DePaul University
1. 15:45
  
  Recursion and Proof Theoretical Characterization of Small Circuit Classes with Modulo Counting via Discrete Differential Equations
  Melissa Antonelli, Arnaud Durand, Rui Li
2. 16:09
  
  The Complexity of Bisimulation in Finitary Diagrams
  Sagnik Dutta, Markus Bläser, Samuel Okyay
3. 16:33
  
  On the Constructive Dimension of Polynomials
  Prajval Koul, Satyadev Nandakumar
4. 16:57
  
  Revisiting Finiteness of Matrix Monoids
  Rida Ait El Manssour, Roland Guttenberg, Nathan Lhote, Mahsa Shirmohammadi, James Worrell
5. 17:21
  
  Loop Termination and Generalized Collatz Sequences
  Mishel Carelli
16:15–16:45
PODC/SPAA

Coffee Break (PODC/SPAA)

Shilling Building Foyer
16:45–17:55
PODC/SPAA

Highly Asynchronous Concurrency in Data Structures (Invited Talk)

Shilling Building Auditorium, chaired by Eric Ruppert (York University) [stream] [qs]

Robert Tarjan (Princeton University)

Abstract

This talk will explore whether and by how much operations on data structures can be sped up by using multiple highly unsynchronized threads. Taking advantage of concurrency in this setting is a challenge. The talk will describe work by Siddhartha Jayanti and the speaker on the efficiency of concurrent disjoint set union algorithms, including recent unpublished work that uses new ideas to eliminate the need for randomization. It will also discuss ongoing work with Laxman Dhulipala, Jakub Łącki, and Siddhartha Jayanti on finding maximal matchings, as well as the general question of what we should require in a realistic but theoretically tractable model of highly asynchronous concurrency.
17:55–18:00
PODC

Closing (PODC)

Shilling Building Auditorium [stream] [qs]
17:55–18:00
SPAA

Closing (SPAA)

Queens Building Lecture Theatre [stream] [qs]

Legend

SPAA PODC INVITED/AWARD TALK ICALP BREAKS

09:00–10:00
ICALP

Fine-Grained Complexity of Optimization: The Case of 2D Knapsack (ICALP Invited Talk)

Windsor Building Auditorium

Karl Bringmann (ETH Zurich)

Abstract

Fine-grained complexity theory provides a framework for proving conditional lower bounds on the time complexity of computational problems, based on the Strong Exponential Time Hypothesis and similar conjectures. Over the last 15 years, conditional lower bounds have become a powerful tool for explaining the (conditional) optimality of algorithms across many domains including graph algorithms, computational geometry, string processing, databases, etc.

Optimization problems provide a particularly rich setting for this theory. For problems such as Subset Sum, Knapsack, and scheduling, the central algorithmic questions involve pseudopolynomial time, approximation schemes, and the dependence on numerical parameters. This talk will survey how fine-grained lower bounds have shaped our understanding of these classical problems.

Our main case study will be recent work on approximation schemes for 2D Knapsack. We show a conditional lower bound based on the k-SUM Hypothesis. Guided by this lower bound we then design a faster approximation scheme based on the meet-in-the-middle technique as well as methods for generating and exploiting slack. This example illustrates a broader theme: fine-grained complexity can be useful not only for proving limitations, but also for identifying running time goals and the algorithmic ideas needed to reach them.
09:00–10:00
PODC

Gems of Distributed Computing: Two Complexity Lower Bounds (GODC@PODC)

Shilling Building Lecture Theatre [stream] [qs]

Faith Ellen (University of Toronto)

Abstract

In this talk, I will present the key ideas of the proofs of two lower bounds, both of which are asymptotically optimal. They are elegant, focusing on carefully chosen aspects of the problems. The first proof, by Laurinharju and Suomela, uses round elimination to show that Ω(log*n) rounds are necessary to colour a ring of n processes with 3 colours so that adjacent processes have different colours. The second proof is a covering argument by Zhu, which shows that Ω(n) registers are needed to solve randomized wait-free binary consensus among n processes.
10:00–10:30

Coffee Break (ICALP/PODC/SPAA)

Shilling/Windsor Building Foyers
10:30–12:30
ICALP (Track A)
ICALP Session 6.1

Windsor 0-04, chaired by Peter Kiss
1. 10:30
  
  Submodular Maximization over a Matroid k-Intersection: Multiplicative Improvement over Greedy
  Moran Feldman, Justin Ward
2. 10:54
  
  Combinatorial Perpetual Scheduling
  Mirabel Mendoza, Arturo Merino, Mads Anker Nielsen, Kevin Schewior
3. 11:18
  
  Tight Algorithm and Hardness for Submodular Linear Ordering
  Evan Abboud, Roy Schwartz
4. 11:42
  
  An Õ(n^3/7) Round Parallel Algorithm for Matroid Bases
  Sanjeev Khanna, Aaron Putterman, Junkai Song
5. 12:06
  
  The SBM has OGP for MOD
  Sreekalyani Shankar Bhamidi, David Gamarnik, Remco van der Hofstad, Nelly Litvak, Pawel Pralat, Fiona Skerman, Yasmin Tousinejad
10:30–12:30
ICALP (Track A)
ICALP Session 6.2

Windsor 1-02/03, chaired by Amey Bhangale
1. 10:30
  
  A Linear Bound for the Size of the Finite Terminal Assembly of a Directed Non-cooperative Tile Assembly System
  Damien Regnault, Sergiu Ivanov
2. 10:54
  
  The Quantum Smooth Label Cover Problem is Undecidable
  Eric Culf, Kieran Mastel, Connor Paddock, Taro Spirig
3. 11:18
  
  Spiky Rank and Its Applications to Rigidity and Circuits
  Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov, Morgan Shirley, Adi Shraibman
4. 11:42
  
  Partial Derivative Complexity of a Product of Linearly Independent Quadratics
  Nir Shalmon, Amir Shpilka
5. 12:06
  
  Inapproximability of Counting Permutation Patterns
  Michal Opler
10:30–12:30
ICALP (Track A)
ICALP Session 6.3

Windsor 1-04, chaired by Guillaume Ducoffe
1. 10:30
  
  New Diameter Approximations via Distance Oracle Techniques
  Yael Kirkpatrick, Liam Roditty, Richard Qi, Virginia Vassilevska Williams
2. 10:54
  
  Improved Tree Sparsifiers in Near-Linear Time
  Daniel Agassy, Dani Dorfman, Haim Kaplan
3. 11:18
  
  Optimal Sequential Flows
  Hugo Gimbert, Corto Mascle, Patrick Totzke
4. 11:42
  
  Connected Dominating Sets in Triangulations
  Prosenjit Bose, Vida Dujmovic, Hussein Houdrouge, Pat Morin, Saeed Odak
5. 12:06
  
  On the Hardness of Recognizing Graphs of Small Mim-Width and its Variants
  Manuel Lafond, Max Dupre la Tour, Ndiame Ndiaye
10:30–12:30
ICALP (Track A)
ICALP Session 6.4

Windsor Building Auditorium, chaired by Dani Dorfman
1. 10:30
  
  A Tight Double-Exponential Lower Bound for High-Multiplicity Bin Packing
  Klaus Jansen, Felix Ohnesorge, Lis Pirotton
2. 10:54
  
  Faster Algorithms for k-Orthogonal Vectors in Low Dimension
  Anita Dürr, Evangelos Kipouridis, Michael Lampis, Karol Wegrzycki
3. 11:18
  
  Colourful Minors
  Evangelos Protopapas, Dimitrios Thilikos, Sebastian Wiederrecht
4. 11:42
  
  Quickly Excluding an Annotated Planar Graph
  Maximilian Gorsky, Evangelos Protopapas, Sebastian Wiederrecht
5. 12:06
  
  Odd-Cycle-Packing-Treewidth: On the Maximum Independent Set Problem in Odd-Minor-Free Graph Classes
  Mujin Choi, Maximilian Gorsky, Gunwoo Kim, Caleb McFarland, Sebastian Wiederrecht.
10:30–12:30
ICALP (Track B)
ICALP Session 6.5 (Quantitative Languages)

Windsor 0-02/03, chaired by Anton Lorenzen, Edinburgh University
1. 10:30
  
  Infinite-state Games with Energy Objectives Beyond Counters
  Irmak Saglam, Georg Zetzsche
2. 10:54
  
  Optimally Controlling a Random Population
  Hugo Gimbert, Corto Mascle, Patrick Totzke
3. 11:18
  
  Population Protocols Over Ordered Agents
  Michael Blondin, Michaël Cadilhac, Benjamin Courchesne, Lucie Guillou, Corto Mascle, Isa Vialard
4. 11:42
  
  Multi-environment MDPs with Prior and Universal Semantics
  Benjamin Bordais, Jean-François Raskin
5. 12:06
  
  Witnesses for Fixpoint Games on Lattices
  Barbara König, Karla Messing
10:30–12:15
PODC
Tutorial: Erasure Coding in Distributed Protocols (Session 1)

Shilling Building Lecture Theatre [stream] [qs]

Vivien Bammert (University of Bern), Mariarosaria Barbaraci (University of Bern), Annalisa Cimatti (University of Bern), and Christian Cachin (University of Bern)

Abstract

An erasure code is a method to divide large volumes of data into pieces so that some pieces may be lost but the data itself can still be recovered. Starting with RAID storage devices, erasure codes have been deployed widely in local and in networked storage systems to increase resilience against failures. More recently erasure codes have been combined with distributed protocols in many ways, often for protocols that tolerate Byzantine faults. When used within broadcast and consensus protocols, erasure codes can reduce the communication complexity of such algorithms to the minimally required cost. Erasure codes have also found compelling applications to blockchain and cryptocurrency platforms where they ensure that transaction data is available. The tutorial will consist of multiple parts that illustrate the basic concepts of erasure codes and how they are used in recent theoretical protocols and practical systems.
1. Fundamentals
  Vivien Bammert
2. Verifiable Information Dispersal and Optimizations
  Annalisa Cimatti
3. Applications to Consensus and Blockchains
  Mariarosaria Barbaraci
12:30–14:00

Lunch

Students' Union Building
14:00–15:12
ICALP (Track A)
ICALP Session 7.1

Windsor 0-04, chaired by Daniel Vaz
1. 14:00
  
  Parallel Reachability and Shortest Paths on Non-Sparse Digraphs: Near-Linear Work and Sub-Square-Root Depth
  Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2. 14:24
  
  Fast Shortest Paths in Graphs with Sparse Signed Tree Models and Applications
  Édouard Bonnet, Colin Geniet, Eun Jung Kim, Sungmin Moon
3. 14:48
  
  Undirected Replacement Paths: Dual Fault Reduces to Single Source
  Jakob Nogler, Virginia Vassilevska Williams
14:00–15:12
ICALP (Track A)
ICALP Session 7.2

Windsor 1-02/03, chaired by Benedikt Pago
1. 14:00
  
  The Price of Homogeneity is Polynomial
  Maximilian Gorsky, Michał Seweryn, Sebastian Wiederrecht
2. 14:24
  
  On Tight FPT Time Approximation Algorithms for k-Clustering Problems
  Han Dai, Shi Li, Sijin Peng
3. 14:48
  
  Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
  Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth
14:00–15:12
ICALP (Track A)
ICALP Session 7.3

Windsor 1-04, chaired by Jukka Suomela
1. 14:00
  
  Computing Flows in Subquadratic Space
  Jan van den Brand, Zhao Song, Albert Weng
2. 14:24
  
  White-Box Adversarial Streaming Lower Bounds beyond Two-Party Communication
  Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
3. 14:48
  
  Beyond Brooks: (\Delta-1)-Coloring in Semi-Streaming
  Maxime Flin, Magnus M. Halldorsson
14:00–15:12
ICALP (Track A)
ICALP Session 7.4

Windsor Building Auditorium, chaired by Christian Coester
1. 14:00
  
  Edge-Weighted Online Stochastic Matching Under Jaillet-Lu LP
  Shuyi Yan
2. 14:24
  
  Online Correlation Clustering: Simultaneously Optimizing All \ell_p-Norms
  Sami Davies, Benjamin Moseley, Heather Newman
3. 14:48
  
  Online Preemptive Matching Revisited
  Peter Kiss, Mohammad Sharifi.
14:00–15:12
ICALP (Track B)
ICALP Session 7.5 (Programming Models, Topology, and Analysis)

Windsor 0-02/03, chaired by Georg Zetzsche, Max Planck Institute for Software Systems, Kaiserslautern
1. 14:00
  
  Persistent Amortized Analysis, Operationally
  Anton Lorenzen
2. 14:24
  
  Stone Duality Proofs for Colorless Distributed Computability Theorems
  Cameron Calk, Emmanuel Godard
3. 14:48
  
  Everyone Wants to be a Seed: Arbitrary Single-tile Seeds in the Abstract Tile Assembly Model
  Florent Becker, Marie de Sainte Marie
14:00–15:00
PODC
Tutorial: Erasure Coding in Distributed Protocols (Session 2)

Shilling Building Lecture Theatre [stream] [qs]

Vivien Bammert (University of Bern), Mariarosaria Barbaraci (University of Bern), Annalisa Cimatti (University of Bern), and Christian Cachin (University of Bern)

Abstract

An erasure code is a method to divide large volumes of data into pieces so that some pieces may be lost but the data itself can still be recovered. Starting with RAID storage devices, erasure codes have been deployed widely in local and in networked storage systems to increase resilience against failures. More recently erasure codes have been combined with distributed protocols in many ways, often for protocols that tolerate Byzantine faults. When used within broadcast and consensus protocols, erasure codes can reduce the communication complexity of such algorithms to the minimally required cost. Erasure codes have also found compelling applications to blockchain and cryptocurrency platforms where they ensure that transaction data is available. The tutorial will consist of multiple parts that illustrate the basic concepts of erasure codes and how they are used in recent theoretical protocols and practical systems.
1. Fundamentals
  Vivien Bammert
2. Verifiable Information Dispersal and Optimizations
  Annalisa Cimatti
3. Applications to Consensus and Blockchains
  Mariarosaria Barbaraci
15:00–15:30

Coffee Break (ICALP/PODC/SPAA)

Shilling/Windsor Building Foyers
15:30–16:42
ICALP (Track A)
ICALP Session 8.1

Windsor 0-04, chaired by Benjamin Aram Berendsohn
1. 15:30
  
  Fast Decremental Tree Sums in Forests
  Benjamin Aram Berendsohn, Marek Sokołowski
2. 15:54
  
  Simpler and Improved Replacement Path Coverings
  Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Martin Schirneck
3. 16:18
  
  Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
  Xizhe Li, Yaowei Long, David Pidugu, Thatchaphol Saranurak, Benyu Wang
15:30–16:42
ICALP (Track A)
ICALP Session 8.2

Windsor 1-02/03, chaired by Thore Husfeldt
1. 15:30
  
  From Worst-Case Hardness of NP to Quantum Cryptography via Quantum Indistinguishability Obfuscation
  Tomoyuki Morimae, Yuki Shirakawa, Takashi Yamakawa
2. 15:54
  
  Mutable Batch Arguments and Applications
  Rishab Goyal
3. 16:18
  
  On Randomness Complexity of 1-Private Protocols
  Samuel Dittmer, Rafail Ostrovsky
15:30–16:18
ICALP (Track A)
ICALP Session 8.3

Windsor 1-04, chaired by Peter Kiss
1. 15:30
  
  The Expiration Streaming Model: Diameter, k-Center, Counting, Sampling, and Friends
  Lotte Blank, Sergio Cabello, MohammadTaghi Hajiaghayi, Robert Krauthgamer, Sepideh Mahabadi, André Nusser, Jeff Phillips, Jonas Sauer
2. 15:54
  
  Optimal k-Secretary with Logarithmic Memory
  Mingda Qiao, Wei Zhang
3. 16:18
  
  Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
  Pan Peng, Yuyang Wang
15:30–16:42
ICALP (Track A)
ICALP Session 8.4

Windsor Building Auditorium, chaired by Benedikt Pago
1. 15:30
  
  Unsplittable Transshipments
  Srinwanti Debgupta, Sarah Morell, Martin Skutella
2. 15:54
  
  Optimal Inapproximability of Generalized Linear Equations over a Finite Group
  Yezhou Zhang, Amey Bhangale

Legend

INVITED/AWARD TALK ICALP GODC WORKSHOPS BREAKS PODC TUTORIAL

Programme

Monday 6 July - Workshop Day and Drinks Reception for All

ApPLIED Opening Remarks

Algorithmic Aspects of Temporal Graphs IX (Session 1)

Student Spotlight Workshop 2026 (Session 1)

Efficient Randomized Shared Memory Primitives and Algorithms (ApPLIED Keynote)

Quantum Constraint Satisfaction Problems (Arrival)

Infinity 2026 Welcome

Fine-Grained Complexity and Formal Languages (Infinity 2026)

Introductions (Infinity 2026)

Coffee Break (ICALP/PODC/SPAA)

Student Spotlight Workshop 2026 (Session 2)

Shared Memory, Consensus, Causality, and Distributed Systems (ApPLIED Session 1)

Algorithmic Aspects of Temporal Graphs IX (Session 2)

Precise Complexity Analysis of Coverability in Vector Addition Systems (Infinity 2026)

Quantum Constraint Satisfaction Problems (Session 2)

Spotlight talks (Infinity 2026)

Lunch

Parallel Spatial Data Structures

Algorithmic Aspects of Temporal Graphs IX (Session 3)

Grassroots Computing

Quantum Constraint Satisfaction Problems (Session 3)

Relaxed Concurrent Data Structures (ApPLIED Keynote)

Fine-Grained Dichotomies for evaluating database queries (Infinity 2026)

Coffee Break (ICALP/PODC/SPAA)

On The Fine Grained Complexity of Multi-Stack Reachability (Infinity 2026)

Grassroots Computing

Student Spotlight Workshop 2026 (Poster Session)

Data Structures, AI, and Cloud Verification (ApPLIED Session 2)

Algorithmic Aspects of Temporal Graphs IX (Session 4)

Infinity 2026 (Session 4)

Quantum Constraint Satisfaction Problems (Session 4)

On the Fine-Grained Complexity of Concurrency Testing (Infinity 2026)

A Celebration of Prasad Jayanti

Decentralized Services, Time, and Byzantine Communication (ApPLIED Session 3)

Online Orthogonal Vectors Revisited (Infinity 2026)

Drinks Reception (ICALP/PODC/SPAA)

Legend

Tuesday 7 July

Opening (SPAA)

Opening (PODC)

SPAA Session 1: Scheduling Algorithms

PODC Session 1

Algebraic Proof Systems - An Algebraic Approach to Analysing Proofs (ICALP Invited Talk)

Coffee Break (ICALP/PODC/SPAA)

PODC Session 2

SPAA Session 2: Parallel (Shared-Memory) Graph Algorithms

ICALP Session 1.1

ICALP Session 1.2

ICALP Session 1.3

ICALP Session 1.4

ICALP Session 1.5 (Transducers)

PODC Session 3

SPAA Session 3: Brief Announcements: Fault Tolerance, Dispersion, and Consensus

Lunch

Algorithmic Robust Statistics (Gödel Award)

PODC Session 4

SPAA Session 4: Concurrent Data Structures

Dimensionality, Metrics, and Compression: A Decade of Algorithmic Advances in Clustering (Presburger Award)

PODC Session 5

SPAA Session 5: Fault Tolerance in Distributed Systems

Coffee Break (ICALP)

ICALP Session 2.1

ICALP Session 2.2

ICALP Session 2.3

ICALP Session 2.4

ICALP Session 2.5 (Constraint Satisfaction, Codes, and Semi-ring Semantics)

Coffee Break (PODC/SPAA)

Parallel Algorithm Engineering Reconsidered (Invited Talk)

PODC Business Meeting

SPAA Business Meeting

Banquet (ICALP)

Legend

Wednesday 8 July

SPAA Session 1: Parallel and (More) Concurrent Data Structures

PODC Session 6

Decidability and Complexity Borders of Reachability Problems (ICALP Invited Talk)

Coffee Break (ICALP/PODC/SPAA)

SPAA Session 2: Energy-Efficient Computing

The Omega(D+sqrt(n)) Lower Bound Story of Distributed Algorithms (Dijkstra Prize Talk)