Friday, 2nd June

08:30 - 08:50 Welcome and Coffee/Tea
08:50 - 09:00 Welcome session

Session chair: Harald Räcke

09:00 - 10:00 Marcin Pilipczuk — Flow Augmentation
10:00 - 10:30 William Kuszmaul — A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits
10:30 - 11:00 Coffee/Tea Break

Session chair: Tuğkan Batu

11:00 - 11:30 Mohsen Ghaffari — Local Computation of Maximal Independent Set
11:30 - 12:00 Rasmus Kyng — Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
12:00 - 12:30 Nicole Wein — Online List Labeling: Breaking the $\log^2 n$ Barrier
12:30 - 14:00 Lunch (provided)

Session chair: Seffi Naor

14:00 - 15:30 Contributed Talks
15:30 - 16:30 Coffee Break and Poster Session

Session chair: Fabrizio Grandoni

16:30 - 17:30 Tillmann Miltzow — Existential Theory of the Reals
17:30 - 18:00 Alexandros Hollender — Pure-Circuit: Strong Inapproximability for PPAD
18:00 - 18:30 Andreas Wiese — A PTAS for Unsplittable Flow on a Path
18:30 - 21:00 Reception

Saturday, 3rd June

08:30 - 09:00 Welcome and Coffee/Tea

Session chair: Tobias Mömke

09:00 - 10:00 Sepehr Assadi — Lower Bound Techniques for Multi-Pass Streaming Algorithms
10:00 - 10:30 Ohad Feldheim — The Power of Two Choices in Graphical Allocation
10:30 - 11:00 Coffee/Tea Break

Session chair: Yannic Maus

11:00 - 11:30 Christian Coester — Shortest Paths without a Map, but with an Entropic Regularizer
11:30 - 12:00 Kent Quanrud — Densest Subgraph: Supermodularity, Iterative Peeling, and Flow
12:00 - 12:30 Ariel Kulik — Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
12:30 - 14:00 Lunch (provided)

Session chair: Robert Krauthgamer

14:00 - 15:30 Contributed Talks
15:30 - 16:30 Coffee Break and Poster Session

Session chair: Yossi Azar

16:30 - 17:30 Klaus Jansen — Approximation Schemes for Scheduling Problems
17:30 - 18:00 Xavier Allamigeon — No Self-concordant Barrier Interior Point Method is Strongly Polynomial
18:00 - 18:30 Balasubramanian Sivan — Approximately Efficient Bilateral Trade

Chair: Yossi Azar

18:30 - 19:30 Business Meeting

Sunday, 4th June

08:30 - 09:00 Welcome and Coffee/Tea

Session chair: Gramoz Goranci

09:00 - 10:00 Merav Parter — Recent Advances in Distributed Algorithms
10:00 - 10:30 Jie Gao — On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem
10:30 - 11:00 Coffee/Tea Break

Session chair: Jarosław Byrka

11:00 - 11:30 Michael Anastos — A Fast Algorithm on Average for Solving the Hamilton Cycle Problem
11:30 - 12:00 Linda Kleist — A Solution to Ringel’s Circle Problem
12:00 - 12:30 Ola Svensson — Flow Time Scheduling and Prefix Beck-Fiala
12:30 - 14:00 Lunch (provided)

Session chair: Artur Czumaj

14:00 - 15:30 Contributed Talks
15:30 - 16:00 Coffee Break

Session chair: Jiří Sgall

16:00 - 17:00 Uri Stemmer — Differential Privacy and Algorithms against an Adaptive Adversary
17:00 - 18:00 Poster Session

Contributed Talks

Friday, 2nd June

Michael Elkin, Yuval Gitlitz and Ofer Neiman — Improved Weighted Additive Spanners
Nathan Wallheimer and Amir Abboud — Worst-case to Expander-case Reductions
Sorrachai Yingchareonthawornchai and Thatchaphol Saranurak — Deterministic Small Vertex Connectivity in Almost Linear Time
Debarati Das, Jacob Gilbert, Mohammadtaghi Hajiaghayi, Tomasz Kociumaka and Barna Saha — Weighted Edit Distance Computation: Strings, Trees, and Dyck
Kyungjin Cho, Eunjin Oh and Seunghyeok Oh — Parameterized Algorithm for the Planar Disjoint Paths Problem: Exponential in $k^2$, and Linear in $n$
Ashish Chiplunkar, Monika Henzinger, Sagar Sudhir Kale and Maximilian Vötsch — Online Min-Max Paging
Piotr Mitosek — Constructing $NP^{\#P}$-complete Problems and $\#P$-hardness of Circuit Extraction in Phase-free $ZH$
Hugo Aaronson, Tom Gur and Ninad Rajgopal — Distribution-Free Proofs of Proximity
Sujoy Bhore, Robert Ganian, Liana Khazaliya, Fabrizio Montecchiani and Martin Nöllenburg — Extending Orthogonal Planar Graph Drawings is Fixed-Parameter Tractable
Sayan Bhattacharya, Peter Kiss and Thatchaphol Saranurak — Dynamic $(1+\varepsilon)$-Approximate Matching Size in Truly Sublinear Update Time
Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich and Tobias Stamm — New Results for Intractable Scheduling Problems
Oded Lachish, Felix Reidl and Chhaya Trehan — When You Come at the King You Best not Miss
François Dross, Krzysztof Fleszar, Karol Węgrzycki and Anna Zych-Pawlewicz — Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
Monika Henzinger, Stefan Neumann, Harald Räcke and Stefan Schmid — Dynamic Maintenance of Monotone Dynamic Programs and Applications
Sayan Bhattacharya, Martin Costa, Silvio Lattanzi and Nikos Parotsidis — Fully Dynamic $k$-Clustering in $\tilde{O}(k)$ Update Time
Meike Neuwohner — Passing the Limits of Pure Local Search for Weighted k-Set Packing
Fateme Abbasi, Marek Adamczyk, Miguel Bosch-Calvo, Jarosław Byrka, Fabrizio Grandoni, Krzysztof Sornat and Antoine Tinguely — An $O(\log\log n)$-Approximation for Submodular Facility Location
Amir Abboud, Karl Bringmann and Nick Fischer — Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics

Saturday, 3rd June

Jannis Blauth and Martin Nägele — An Improved Approximation Guarantee for Prize-Collecting TSP
Panagiotis Charalampopoulos, Tomasz Kociumaka and Philip Wellnitz — Faster Pattern Matching under Edit Distance
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra and Sayantan Sen — Exploring the Gap between Tolerant and Non-tolerant Distribution Testing
Yiannis Giannakopoulos, Alexander Grosz and Themistoklis Melissourgos — On the Smoothed Complexity of Combinatorial Local Search
Kunal Dutta, Arijit Ghosh and Shay Moran — Uniform Brackets, Containers, and Combinatorial Macbeath Regions
Parinya Chalermsook, Matthias Kaul, Matthias Mnich, Joachim Spoerhase, Sumedha Uniyal and Daniel Vaz — Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
Jakub Svoboda — Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth
Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek and Sorrachai Yingchareonthwornchai — Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
Sam Coy, Artur Czumaj and Gopinath Mishra — On Parallel k-Center Clustering
Nicolas Bousquet, Laurent Feuilloley and Théo Pierron — What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs
Arijit Ghosh, Gopinath Mishra, Rahul Raychaudhury and Sayantan Sen — Tolerant Bipartiteness Testing in Dense Graphs
Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat and Subir Kumar Ghosh — Complexity and Algorithms for Isometric Path Cover on Chordal Graphs and Beyond
Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomas Masarik, Marcin Pilipczuk, Roohani Sharma and Manuel Sorge — Fixed-parameter Tractability of Directed Multicut with Three Terminal pairs Parameterized by the Size of the Cutset: Twin-width Meets Flow-augmentation
Harald Räcke, Stefan Schmid and Ruslan Zabrodin — Polylog-Competitive Algorithms for Dynamic Balanced Graph Partitioning for Ring Demands
Niklas Schlomberg, Hanjo Thiele and Jens Vygen — Packing Cycles in Planar and Bounded-genus Graphs
Sven Jäger, Guillaume Sagnol, Daniel Schmidt Genannt Waldschmidt and Philipp Warode — Competitive Kill-and-Restart and Preemptive Strategies for Non-clairvoyant Scheduling
Sanjana Dey, Florent Foucaud, Subhas Nandy and Arun Sen — Complexity and Approximation for Discriminating and Identifying Code Problems in Geometric Setups

Sunday, 4th June

Amir Abboud, Seri Khoury, Oree Leibowitz and Ron Safier — Listing 4-Cycles
Sandip Das and Harmender Gahlawat — On the Cop Number of String Graphs
Itai Boneh, Shay Golan, Shay Mozes and Oren Weimann — Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings
Shahar Lewkowicz, Yossi Azar and Danny Vainstein — List Update with Delays or Time Windows
Jacob Focke, Dániel Marx, Fionn Mc Inerney, Daniel Neuen, Govind Sankar, Philipp Schepper and Philip Wellnitz — Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs
Diptarka Chakraborty, Debarati Das and Robert Krauthgamer — Clustering Permutations: New Techniques with Streaming Applications
Loukas Georgiadis, Evangelos Kipouridis, Charis Papadopoulos and Nikos Parotsidis — Faster Computation of 3-Edge-Connected Components in Digraphs
Marcel Dall’Agnol, Graham Cormode, Chris Hickey and Tom Gur — Streaming Zero-Knowledge Proofs
Aniket Basu Roy — Covering Simple Orthogonal Polygons with Rectangles
Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann and Martin Schirneck — Approximate Distance Sensitivity Oracles in Subquadratic Space
Andreas Emil Feldmann and Tung Anh Vu — Generalized $k$-Center: Distinguishing Doubling and Highway Dimension
Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek and Ziena Zeif — Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan and Shay Sapir — Lower Bounds for Pseudo-Deterministic Counting in a Stream
Antoine El-Hayek, Monika Henzinger and Stefan Schmid — Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
Alexandra Lassota, Aleksander Łukasiewicz and Adam Polak — Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs
Zachary Friggstad and Ramin Mousavi — An $O(\log k)$-Approximation for Directed Steiner Tree in Planar Graphs

Building plan

Lectures will be held in S3 and S4 lecture rooms on the third floor.