Programme

Wednesday, 4th June

08:30 - 09:10

Coffee/Tea

Session chair: Michal Dory

09:10 - 10:00	Yael Kalai — Survey on verifying quantum computation
10:00 - 10:30	Jeremy Fineman — Single-Source Shortest Paths with Negative Real Weights in Õ(mn^8/9) Time
10:30 - 11:00	Coffee Break

Session chair: Michal Dory

11:00 - 11:30	Richard Hladik — Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
11:30 - 12:00	Christoph Grunau — Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
12:00 - 12:30	Maximilian Probst Gutenberg — Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality

Session chair: Paul Duetting

14:00 - 15:30	Contributed (21 Talks of 3+1 Minutes)
Mikkel Abrahamsen, Ioana Bercea, Lorenzo Beretta, Jonas Klausen and László Kozma Online Sorting and Online TSP: Randomized, Stochastic, and High-Dimensional Martin G. Herold, Evangelos Kipouridis and Joachim Spoerhase Clustering to Minimize Cluster-Aware Norm Objectives Matthias Gehnen Online Algorithms with Estimates Matthijs Ebbens, Nicole Funk, Jan Höckendorff, Christian Sohler and Vera Weil A Subquadratic Time Approximation Algorithm for Individually Fair k-Center Eric Balkanski, Vasilis Gkatzelis and Golnoosh Shahkarami Randomized Strategic Facility Location with Predictions Nir Petruschka and Robert Krauthgamer Lipschitz Decompositions of Finite l_p Metrics Yongho Shin Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem Jannis Blauth, Nathan Klein and Martin Nägele A Better-Than-1.6-Approximation for Prize-Collecting TSP Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson and Morteza Zadimoghaddam The Cost of Consistency: Submodular Maximization with Constant Recourse Christian Coester and Tze-Yang Poon Online 3-Taxi on General Metrics Sander Borst, Danish Kashaev and Zhuan Khye Koh Online Matching on 3-Uniform Hypergraphs Matteo Russo, Andrea Celli, Riccardo Colini-Baldeschi, Federico Fusco, Daniel Haimovich, Dima Karamshuk, Stefano Leonardi and Niek Tax Online Learning with Sublinear Best-Action Queries Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran and Maximilian Thiessen Of Dice and Games: A Theory of Generalized Boosting Neta Singer and Theophile Thiery Better Approximation for Weighted k-Matroid Intersection Mathieu Molina, Nicolas Gast, Patrick Loiseau and Vianney Perchet Prophet Inequalities: Competing with the Top ℓ Items is Easy Lars Rohwedder and Leander Schnaars 3.415-Approximation for Coflow Scheduling via Iterated Rounding Neel Patel and David Wajc Combinatorial Stationary Prophet Inequalities Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson and Sergei Vassilvitskii Data-Driven Solution Portfolios Sandip Banerjee, Yair Bartal, Lee-Ad Gottlieb and Alon Hovav Novel properties of hierarchical probabilistic partitions and their algorithmic applications Alexander Munteanu and Simon Omlor Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation Euiwoong Lee, Ola Svensson and Théophile Thiery Asymptotically Optimal Hardness for k-Set Packing and k-Matroid Intersection
15:30 - 16:30	Coffee Break & Poster Session

Session chair: Yossi Azar

16:30 - 17:20	Shay Solomon — Survey on spanners
17:20 - 17:50	Greg Bodwin — An Alternate Proof of Near-Optimal Light Spanners
17:50 - 18:20	Yasamin Nazari — On Dynamic Graph Algorithms with Predictions

18:30 - 19:30

Business Meeting (with drinks)

Thursday, 5th June

08:30 - 09:10

Coffee/Tea

Session chair: Robi Krauthgamer

09:10 - 10:00	Sergei Vassilvitskii — Survey on learning-augmented algorithms
10:00 - 10:30	Ewin Tang — High-Temperature Gibbs States are Unentangled and Efficiently Preparable
10:30 - 11:00	Coffee Break

Session chair: Artur Czumaj

11:00 - 11:30	Michal Feldman — Fair Division via Quantile Shares
11:30 - 12:00	Soheil Behnezhad — Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
12:00 - 12:30	Mihir Singhal — Optimal Quantile Estimation: Beyond the Comparison Model

Session chair: Christian Coester

14:00 - 15:30	Contributed (21 Talks of 3+1 Minutes)
Sepideh Mahabadi, Mohammad Roghani and Jakub Tarnawski A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time Martin G. Herold, Danupon Nanongkai, Joachim Spoerhase, Nithin Varma and Zihang Wu Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions John Augustine, Christian Scheideler and Julian Werthmann Supervised Distributed Computing Merav Parter, Asaf Petruschka, Shay Sapir and Elad Tzalik Parks and Recreation: Color Fault-Tolerant Spanners Made Local Koustav Bhanja and Surender Baswana Vital Edges for (s,t)-mincut: Efficient Algorithms, Compact Structures, & Optimal Sensitivity Oracles Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein Approximating Maximum Matching Requires Almost Quadratic Time Yonggang Jiang, Joakim Blikstad, Sagnik Mukhopadhyay and Sorrachai Yingchareonthawornchai Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations Lukas Vogl, Nairen Cao, Vincent Cohen-Addad, Euiwoong Lee, Shi Li, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Shuyi Yan and Hanwen Zhang Solving the Correlation Cluster LP in Sublinear Time Joakim Blikstad, Ola Svensson, Radu Vintan and David Wajc Deterministic Online Bipartite Edge Coloring Martin Böhm, Matej Lieskovský, Sören Schmitt, Jiří Sgall and Rob van Stee Improved online load balancing with known makespan Sebastian Forster and Antonis Skarlatos Dynamic Consistent k-Center Clustering with Optimal Recourse Antoine El-Hayek, Monika Henzinger and Jason Li Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation Gramoz Goranci, Peter Kiss, Neel Patel, Martin P. Seybold, Eva Szilagyi and Da Wei Zheng Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time Jacob Holm, Wojciech Nadara, Eva Rotenberg and Marek Sokołowski Fully Dynamic Biconnectivity in Õ(log² n) Time Sayan Bhattacharya, Martin Costa and Ermiya Farokhnejad Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse Gramoz Goranci, Adam Karczmarz, Ali Momeni and Nikos Parotsidis Fully Dynamic Algorithms for Transitive Reduction Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj and Lakshay Saggi Maximum-Flow and Minimum Cut Sensitivity Oracles for Directed Graphs Junhao Gan, Seeun William Umboh, Hanzhi Wang, Anthony Wirth and Zhuo Zhang Optimal Dynamic Parameterized Subset Sampling Pierre Fraigniaud, Minh Hang Nguyen and Ami Paz A Simple Lower Bound for Set Agreement in Dynamic Networks Aryan Agarwala and Guy Even A Space Lower Bound for Approximate Membership with Duplicate Insertions or Deletions of Nonelements Bernhard Haeupler, Yaowei Long, Thatchaphol Saranurak and Shengzhe Wang Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
15:30 - 16:30	Coffee Break & Poster Session

Session chair: Fabrizio Grandoni

16:30 - 17:20	Mohsen Ghaffari — Survey on deterministic distributed algorithms
17:20 - 17:50	Prasanna Ramakrishnan — Breaking the Metric Voting Distortion Barrier
17:50 - 18:20	Xi Chen — Computing a Fixed Point of Contraction Maps in Polynomial Queries

18:30 - 22:00

Reception / Dinner

Friday, 6th June

08:30 - 09:10

Coffee/Tea

Session chair: Vera Traub

09:10 - 10:00	Matus Telgarsky — Survey on Mathematical Questions in LLMs and Deep Learning
10:00 - 10:30	Mohammad T. Hajiaghayi — Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why a Lot of Randomness is Needed?
10:30 - 11:00	Coffee Break

Session chair: Vera Traub

11:00 - 11:30	Shuyi Yan — Edge-Weighted Online Stochastic Matching: Beating 1−1/e
11:30 - 12:00	Louis Golowich — New Explicit Constant-Degree Lossless Expanders
12:00 - 12:30	Oliver Hinder — The Price of Adaptivity in Stochastic Convex Optimization

Session chair: Yasamin Nazari

14:00 - 15:30	Contributed (21 Talks of 3+1 Minutes)
Erik van den Akker, Kevin Buchin and Klaus-Tycho Foerster Multi-agent Online Graph Exploration on Cycles and Tadpole Graphs Johannes Brustle, Simone Fioravanti, Tomasz Ponitka, Jeremy Vollen The Panel Complexity of Sortition: Is 12 Angry Men Enough? Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Krzysztof Sornat, Stanisław Szufa and Nimrod Talmon How Similar are Two Elections? Foivos Fioravantes, Abhiruk Lahiri, Antonio Lauerbach, Lluis Sabatar, Marie Diana Sieper and Samuel Wolf Eliminating Majority Illusions Andreas Charalampopoulos, Dimitris Fotakis, Panagiotis Patsilinakos and Thanos Tolias A Competitive Posted-Price Mechanism for Online Budget-Feasible Auctions Radu Curticapean, Simon Döring, Daniel Neuen and Jiaheng Wang Can You Link Up With Treewidth? Sophia Heimann, Hung Hoang and Stefan Hougardy The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$ Dani Dorfman, Haim Kaplan, Robert Tarjan, Mikkel Thorup and Uri Zwick Faster all-pairs optimal electric car routing Michal Opler An Optimal Algorithm for Sorting Pattern-Avoiding Sequences Radu Curticapean and Daniel Neuen Counting Small Induced Subgraphs: Hardness via Fourier Analysis Mads Anker Nielsen, Gregory Gutin, Yacong Zhou and Anders Yeo Feedback Arc Sets and Feedback Arc Set Decompositions in Weighted and Unweighted Oriented Graphs Dariusz Dereniowski, Aleksander Łukasiewicz and Przemysław Uznański Noisy (Binary) Searching: Simple, Fast and Correct Pranjal Dutta, Amit Sinhababu and Thomas Thierauf Derandomizing Multivariate Polynomial Factoring for Low Degree Factors Eleon Bach and Sophie Huiberts Optimal Smoothed Analysis of the Simplex Method Leo Wennmann, Holger Dell, Anselm Haak and Melvin Kallmayer Solving Polynomial Equations Over Finite Fields Christian Coester and Alexa Tudose Optimal Deterministic Algorithms for Chasing Small Sets Christian Nöbel and Raphael Steiner Complexity of polytope diameters via perfect matchings L. Sunil Chandran, Rishikesh Gajjala and Abraham M. Illickan Krenn-Gu conjecture for sparse graphs L. Sunil Chandran, Rishikesh Gajjala, Shravan Mehra and Saladi Rahul Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery using Drones L. Sunil Chandran and Rishikesh Gajjala Graph-theoretic insights on the constructability of complex entangled states Andreas Padalkin and Christian Scheideler Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter Johannes B.S. Petersen, Akbar Davoodi, Thomas Gartner, Marc Hellmuth, Daniel Merkle Enumerating All Connected Maximum-Sized Common Substructure in Multiple Molecular Graphs
15:30 - 16:00	Coffee Break

Session chair: Yasamin Nazari

16:00 - 16:50	Sebastian Forster — Survey on dynamic algorithms
16:50 - 17:50	Poster Session

Building plan