Programme

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.