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:

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

  • 09:00–10:00
    PODC/SPAA
    Student Spotlight Workshop 2026 (Session 1)

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

  • 09:00–10:00
    ICALP
    ICALP Workshops

  • 10:00–10:30
    Coffee Break

  • 10:30–12:30
    PODC/SPAA
    Student Spotlight Workshop 2026 (Session 2)

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

  • 10:30–12:30
    ICALP
    ICALP Workshops

  • 12:30–14:00
    Lunch

    Students' Union Building

  • 14:00–15:00
    SPAA
    Parallel Spatial Data Structures

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

  • 14:00–15:00
    ICALP
    ICALP Workshops

  • 15:00–15:30
    Coffee Break

  • 15:30–18:00
    PODC/SPAA
    Grassroots Computing

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

  • 15:30–18:00
    ICALP
    ICALP Workshops

  • 18:00–19:30
    Drinks Reception

    Windsor Building

Legend
WORKSHOPS BREAKS SOCIAL
  • 08:35–08:40
    SPAA
    Opening (SPAA)

  • 08:40–08:45
    PODC
    Opening (PODC)

  • 08:40–10:00
    SPAA
    SPAA Session 1: Scheduling Algorithms

    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

    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
    ICALP Invited Talk

    Nutan Limaye (IT University of Copenhagen)

  • 10:00–10:30
    Coffee Break

  • 10:30–11:20
    PODC
    PODC Session 2

    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

    1. 10:30
      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. 10:50
      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. 11:10
      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)
  • 10:30–12:30
    ICALP (Track A)
    ICALP Session 1.1

    1. 10:30
      The SBM has OGP for MOD
      Sreekalyani Shankar Bhamidi, David Gamarnik, Remco van der Hofstad, Nelly Litvak, Pawel Pralat, Fiona Skerman, Yasmin Tousinejad
    2. 10:54
      VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
      Balagopal Komarath, Harshil Mittal, Jayalal Sarma
    3. 11:18
      Proving Algebraic Independence in Zero-Knowledge
      Michael A. Forbes, Andrei Staicu
    4. 11:42
      Alternation Depth of Threshold Decision Lists
      Vladimir Podolskii, Morgan Prior
    5. 12:06
      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
  • 10:30–12:30
    ICALP (Track A)
    ICALP Session 1.2

    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

    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

    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)

    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

    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

    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–15:15
    ICALP
    Gödel and Presburger Awards (ICALP)

  • 14:00–15:00
    PODC
    PODC Session 4

    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: Parallel (Shared-Memory) Graph Algorithms

    1. 14:00
      A Practical Parallel Algorithm for Expander Decompositions
      Robin Münk (Technical University of Munich)
    2. 14:20
      Efficient Parallel (Δ + 1)-Edge-Coloring
      Ariel Khuzman (Ben-Gurion University of the Negev), Michael Elkin (Ben-Gurion University of the Negev)
    3. 14:40
      Parallel Spectral Graph Sparsification via Low Diameter Decompositions
      Yves Baumann (ETH Zurich), Gernot Zöcklein (ETH Zurich)
  • 15:05–16:00
    PODC
    PODC Session 5

    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

    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)

  • 15:45–17:45
    ICALP (Track A)
    ICALP Session 2.1

    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

    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

    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

    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)

    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)

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

    Peter Sanders (Karlsruhe Institute of Technology)

  • 17:45–19:15
    PODC/SPAA
    Business Meeting (PODC/SPAA)

  • 19:30–21:30
    ICALP
    Banquet (ICALP)

    Founders Square

Legend
SPAA PODC INVITED TALK BREAKS ICALP BUSINESS MEETING SOCIAL
  • 08:40–10:00
    SPAA
    SPAA Session 1: Parallel and (More) Concurrent Data Structures

    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

    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
    ICALP Invited Talk

    George Zetzsche (MPI-SWS)

  • 10:00–10:30
    Coffee Break

  • 10:25–11:25
    SPAA
    SPAA Session 2: Energy-Efficient Computing

    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

    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

    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

    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

    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

    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)

    1. 10:30
      Set Automata and Limits of Decidability of Two-variable Log 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:30–12:20
    SPAA
    SPAA Session 3: Brief Announcements: Performance Modeling, Analysis, and Optimization

    1. 11:30
      Brief Announcement: An Automatic Framework for High Performance Alternative Basis Fast Matrix Multiplication
      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

    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

    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

    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

    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

    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 Award

  • 16:00–17:00
    SPAA
    SPAA Session 5: Paging and PIM Scheduling

    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
    EATCS Award

  • 17:00–19:00
    ICALP
    EATCS Assembly and ICALP Business Meeting

  • 17:00–18:00
    PODC
    PODC Session 10

    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 TALK BREAKS ICALP BUSINESS MEETING SOCIAL
  • 08:40–10:00
    SPAA
    SPAA Session 1: Performance Analysis and Optimization for Modern Computing Systems

    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

    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
    ICALP Invited Talk

    Venkatesan Guruswami (UC Berkeley)

  • 10:00–10:30
    Coffee Break

  • 10:30–11:20
    PODC
    PODC Session 12

    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)

    Phillip Gibbons (Carnegie Mellon University)

  • 10:30–12:30
    ICALP (Track A)
    ICALP Session 4.1

    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

    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

    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

    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

    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)

    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

    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:20
    SPAA
    SPAA Session 3: Brief Announcements: Concurrency, Partitioning, and Scheduling

    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)
  • 12:30–14:00
    Lunch

    Students' Union Building

  • 14:00–15:15
    ICALP
    Church & Presburger Awards

  • 14:00–15:05
    PODC
    PODC Session 14

    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

    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)
  • 15:10–16:15
    PODC
    PODC Session 15

    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

    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)

  • 15:45–17:45
    ICALP (Track A)
    ICALP Session 5.1

    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

    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

    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

    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)

    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)

  • 16:45–17:55
    PODC/SPAA
    Highly Asynchronous Concurrency in Data Structures (Invited Talk)

    Robert Tarjan (Princeton University)

  • 17:55–18:00
    PODC/SPAA
    Closing (PODC/SPAA)

Legend
SPAA PODC INVITED TALK BREAKS ICALP
  • 09:00–10:00
    ICALP
    ICALP Invited Talk

    Karl Bringmann (ETH Zurich)

  • 09:00–10:00
    PODC/SPAA
    Workshop Session 1

  • 10:00–10:30
    Coffee Break

  • 10:30–12:06
    ICALP (Track A)
    ICALP Session 6.1

    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 \tilde{O}(n^{3/7}) Round Parallel Algorithm for Matroid Bases
      Sanjeev Khanna, Aaron Putterman, Junkai Song
  • 10:30–12:30
    ICALP (Track A)
    ICALP Session 6.2

    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

    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

    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
      Quickly Excluding an Annotated Planar Graph
      Maximilian Gorsky, Evangelos Protopapas, Sebastian Wiederrecht
    4. 11:42
      Colourful Minors
      Evangelos Protopapas, Dimitrios Thilikos, 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)

    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/SPAA
    Workshop Session 2

  • 12:30–14:00
    Lunch

    Students' Union Building

  • 14:00–15:12
    ICALP (Track A)
    ICALP Session 7.1

    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

    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

    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

    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)

    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/SPAA
    Workshop Session 3

  • 15:00–15:30
    Coffee Break

  • 15:30–16:42
    ICALP (Track A)
    ICALP Session 8.1

    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

    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:42
    ICALP (Track A)
    ICALP Session 8.3

    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

    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
    3. 16:18
      Back in the Saddle: Toward Parallel Approximate Minimum-Cost Flow
      Aurelio Sulser, Rasmus Kyng
  • 15:30–18:00
    PODC/SPAA
    Workshop Session 4

Legend
INVITED TALK WORKSHOPS BREAKS ICALP