Program

The conference will begin on Friday, June 9 at 8:45 and end on Sunday, June 11 at 17:45 . On Friday evening at 18:00 there will be a poster session with reception. On Saturday evening at 18:00 there will be another poster session and at 19:00 the Business Meeting will take place.

A detailed schedule and a list of all accepted posters can be found below. A pdf-version of the program can be downloaded here .

Schedule

Friday, June 9

8:45 - 9:00	Welcome Remarks, MA001
9:00 - 10:30	Session 1, MA001 - Session Chair: Stefano Leonardi
9:00 - 9:30 Ilias Diakonikolas - Robust Estimators in High Dimensions without the Computational Intractability 9:30 - 10:00 Mathias Bæk T. Knudsen - Linear Hashing is Awesome 10:00 - 10:30 Ilya P. Razenshteyn - Hardness of Similarity Search
10:30 - 11:00	Coffee Break

11:00 - 12:30	Session 2, MA001 - Session Chair: Artur Czumaj
11:00 - 12:00 Claire Mathieu - Local search for clustering problems 12:00 - 12:30 Zachary Friggstad - Local Search Yields a PTAS for k-Means in Doubling Metrics
12:30 - 14:00	Lunch Break

14:00 - 15:30	Session 3, MA001 - Session Chair: Silvio Lattanzi
14:00 - 14:30 David Karger - Faster and Simpler Network (Un)reliability Estimation 14:30 - 15:00 Aleksander Madry - Negative-Weight Shortest Paths and Unit Capacity Minimum Cost Flow in O(m10/7 log W) Time 15:00 - 15:30 Sanjeev Khanna - On Estimating Maximum Matching Size in Graph Streams
15:30 - 16:00	Coffee Break

16:00 - 18:00	Session 4, HE 101 - Session Chair: Martin Skutella
16:00-18:00 László Babai - Group theory and combinatorics: The Graph Isomorphism problem
18:00 - 19:30	Poster Session and Reception

Saturday, June 10

9:00 - 10:30	Session 5, Contributed Talks
Stream A, HE 101 - Session Chair: Aleksander Madry Stream B, MA005 - Session Chair: Stefano Leonardi Shiri Chechik, Thomas Dueholm Hansen, Monika Henzinger, Giuseppe F. Italiano, Sebastian Krinninger , Veronika Loitzenbauer and Nikos Parotsidis - Faster algorithms for maximal 2-connected subgraphs in directed graphs Robert Krauthgamer and Ohad Trabelsi - Conditional Lower Bounds for All-Pairs Max-Flow Danupon Nanongkai and Thatchaphol Saranurak - Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n1/2−ε)-Time Piotr Sankowski and Karol Węgrzycki - Improved Distance Queries and Cycle Counting by Frobenius Normal Form Fabrizio Grandoni, Tobias Mömke, Andreas Wiese and Hang Zhou - To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis and Piotr Sankowski - Improved Algorithms for Decremental Single-Source Reachability Aris Anagnostopoulos, Jakub Łącki, Silvio Lattanzi, Stefano Leonardi and Mohammad Mahdian - Community Detection on Evolving Graphs Miriam Schlöter and Martin Skutella - Fast and Memory-Efficient Algorithms for Evacuation Problems Ola Svensson and Jakub Tarnawski - The Matching Problem in General Graphs is in Quasi-NC Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger and Christoph Lenzen - Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt and José Verschae - A Local-Search Algorithm for Steiner Forest Sara Ahmadian, Ashkan Norouzi Fard, Ola Svensson and Justin Ward - Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms Josh Alman, Matthias Mnich and Virginia Vassilevska Williams - Dynamic Parameterized Problems and Algorithms Iyad Kanj, Christian Komusiewicz, Manuel Sorge and Erik Jan van Leeuwen - Parameterized Complexity of Vertex-Partitioning Problems Davis Issac, L. Sunil Chandran and Andreas Karrenbauer - Parameterized Complexity of Biclique Cover and Partition Klaus-Tycho Förster - Local Checkability, No Strings Attached: (A)cyclicity, Reachability, Loop Free Updates in SDNs Bhaskar Dasgupta, Marek Karpinski, Nasim Mobasheri and Farzane Yahyanejad - Effect of Gromov-hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications Fabrice Benhamouda, Tancrede Lepoint, Claire Mathieu and Hang Zhou - Optimization of Bootstrapping in Circuits Marek Cygan, Marcin Mucha, Karol Węgrzycki and Michal Włodarczyk - On problems equivalent to (min,+)-convolution Marcin Jurdzinski and Ranko Lazic - Succinct progress measures for solving parity games Alexander Tiskin - Semi-local LCS: superglue for string comparison Talya Eden, Dana Ron and C. Seshadhri - Approximating the number of k-cliques in a graph Michael A. Bender, Erik D. Demaine, Roozbeh Ebrahimi, Jeremy Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch and Samuel Mccauley - Cache-Adaptive Analysis Nikhil Bansal, Shashwat Garg, Jesper Nederlof and Nikhil Vyas - Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems
10:30 - 11:00	Coffee Break

11:00 - 12:30	Session 6, HE 101 - Session Chair: Christian Sohler
11:00 - 12:00 Sanjeev Arora - Unsupervised learning to uncover semantics of data and language 12:00 - 12:30 Gregory Valiant - Instance Optimal Learning of Discrete Distributions
12:30 - 14:00	Lunch Break

14:00 - 15:30	Session 7, Contributed Talks
Stream A, HE 101 - Session Chair: Stephan Kreutzer Stream B, MA005 - Session Chair: Fabrizio Grandoni Paul Duetting and Thomas Kesselheim - Best-Response Dynamics in Combinatorial Auctions with Item Bidding Ioannis Caragiannis, Aris Filos-Ratsikas, Søren Stiil Frederiksen, Kristoffer Arnsfelt Hansen and Zihan Tan - Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen and S. Matthew Weinberg - The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders Thomas Kesselheim and Andreas Tönnis - Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions Dušan Knop, Martin Koutecky and Matthias Mnich - Voting and Bribing in Single-Exponential Time Amir Ban, Yossi Azar and Yishay Mansour - When Should an Expert Make Predictions? Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang and Roger Wattenhofer - Min-cost Matching with Delays Joachim Spoerhase and Sumedha Uniyal - Maximizing a Monotone Submodular Function Subject to a Covering and a Packing Constraint Nikhil Bansal, Marek Elias, Lukasz Jez and Grigorios Koumoutsos - The (h,k)-Server Problem on Bounded Depth Trees Christian Coester, Elias Koutsoupias and Philip Lazos - The Infinite Server Problem Martin Böhm, Marek Chrobak, Łukasz Jeż, Fei Li, Jiří Sgall and Pavel Veselý - Online Packet Scheduling with Bounded Delay and Lookahead Eliav Buchnik and Edith Cohen - Reverse Ranking by Graph Structure: Model and Scalable Algorithms Artur Czumaj, Pan Peng and Christian Sohler - Relating Two Property Testing Models for Bounded Degree Directed Graphs Yun Kuen Cheung, Gramoz Goranci, Monika Henzinger, Pan Peng and Harald Räcke - Improved Upper and Lower Bounds for Vertex Sparsifiers Leo N. Geppert, Katja Ickstadt, Jens Quedenfeld, Alexander Munteanu and Christian Sohler - Random projections for Bayesian regression Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit and Daniel Vaz - Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs Alexandr Andoni, Lior Kamma, Robert Krauthgamer and Eric Price- Batch Sparse Recovery, or How to Leverage the Average Sparsity Michele Borassi, Pierluigi Crescenzi and Luca Trevisan - An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs Matthias Poloczek, Georg Schnitger, David Williamson and Anke van Zuylen - De-randomizing the Inherently(?) Probabilistic Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni and Lorenzo Orecchia - Expander via Local Edge Flips Artur Czumaj and Peter Davies - Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
15:30 - 16:00	Coffee Break

16:00 - 18:00	Session 8, HE 101 - Session Chair: Thomas Kesselheim
16:00-16:30 S. Matthew Weinberg - A Duality Based Unified Approach to Bayesian Mechanism Design 16:30-17:00 Aviad Rubinstein - Settling the Complexity of Computing Approximate Two-player Nash Equilibria 17:00-17:30 Renato Paes-Leme - Computing Walrasian Equilibria: Fast Algorithms and Structural Properties 17:30-18:00 Simon MacKenzie - A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents
18:00 - 19:00	Poster Session
19:00 - 20:00	Business Meeting with drinks

Sunday, June 11

9:00 - 10:30	Session 9, HE 101 - Session Chair: Ola Svensson
9:00-9:30 Sushant Sachdeva - Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple 9:30-10:00 Marco Mondelli - Reed-Muller Codes Achieve Capacity on Erasure Channels 10:00-10:30 Bart Jansen - Fine-grained complexity analysis of two classic TSP variants
10:30 - 11:00	Coffee Break

11:00 - 12:30	Session 10, HE 101 - Session Chair: Robert Krauthgamer
11:00 - 12:00 Tim Roughgarden - Beyond Worst-Case Analysis 12:00 - 12:30 Constantinos Daskalakis - Learning in Auctions: Regret is Hard, Envy is Easy
12:30 - 13:30	Lunch Break

13:30 - 15:00	Session 11, HE 101 - Session Chair: Pierre Fraigniaud
13:30-14:00 Mohsen Ghaffari - An Improved Distributed Algorithm for Maximal Independent Set. 14:00-14:30 Ami Paz - A (2 + ε )-Approximation for Maximum Weight Matching in the Semi-Streaming Model 14:30-15:00 Merav Parter - MST in Log-Star Rounds of Congested Clique
15:00 - 15:30	Coffee Break

15:30 - 17:30	Session 12, HE 101 - Session Chair: Artur Czumaj
15:30-16:30 Nikhil Bansal - Algorithmic Discrepancy beyond Partial Coloring 16:30-17:00 Karl Bringmann - Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product 17:00-17:30 Aravind Srinivasan - Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
17:30 - 17:45	Closing

Accepted Posters

Shiri Chechik, Thomas Dueholm Hansen, Monika Henzinger, Giuseppe F. Italiano, Sebastian Krinninger , Veronika Loitzenbauer and Nikos Parotsidis - Faster algorithms for maximal 2-connected subgraphs in directed graphs

Robert Krauthgamer and Ohad Trabelsi - Conditional Lower Bounds for All-Pairs Max-Flow

Danupon Nanongkai and Thatchaphol Saranurak - Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n^1/2−ε)-Time

Piotr Sankowski and Karol Węgrzycki - Improved Distance Queries and Cycle Counting by Frobenius Normal Form

Fabrizio Grandoni, Tobias Mömke, Andreas Wiese and Hang Zhou - To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack

Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis and Piotr Sankowski - Improved Algorithms for Decremental Single-Source Reachability

Aris Anagnostopoulos, Jakub Łącki, Silvio Lattanzi, Stefano Leonardi and Mohammad Mahdian - Community Detection on Evolving Graphs

Miriam Schlöter and Martin Skutella - Fast and Memory-Efficient Algorithms for Evacuation Problems

Ola Svensson and Jakub Tarnawski - The Matching Problem in General Graphs is in Quasi-NC

Ruben Becker, Andreas Karrenbauer, Sebastian Krinninger and Christoph Lenzen - Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models

Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt and José Verschae - A Local-Search Algorithm for Steiner Forest

Sara Ahmadian, Ashkan Norouzi Fard, Ola Svensson and Justin Ward - Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Klaus-Tycho Förster - Local Checkability, No Strings Attached: (A)cyclicity, Reachability, Loop Free Updates in SDNs

Bhaskar Dasgupta, Marek Karpinski, Nasim Mobasheri and Farzane Yahyanejad - Effect of Gromov-hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications

Fabrice Benhamouda, Tancrede Lepoint, Claire Mathieu and Hang Zhou - Optimization of Bootstrapping in Circuits

Marek Cygan, Marcin Mucha, Karol Węgrzycki and Michal Włodarczyk - On problems equivalent to (min,+)-convolution

Marcin Jurdzinski and Ranko Lazic - Succinct progress measures for solving parity games

Alexander Tiskin - Semi-local LCS: superglue for string comparison

Talya Eden, Dana Ron and C. Seshadhri - Approximating the number of k-cliques in a graph

Michael A. Bender, Erik D. Demaine, Roozbeh Ebrahimi, Jeremy Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch and Samuel Mccauley - Cache-Adaptive Analysis

Nikhil Bansal, Shashwat Garg, Jesper Nederlof and Nikhil Vyas - Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related Problems

Josh Alman, Matthias Mnich and Virginia Vassilevska Williams - Dynamic Parameterized Problems and Algorithms

Erik Jan van Leeuwen - Parameterized Complexity of Vertex-Partitioning Problems

Davis Issac, L. Sunil Chandran and Andreas Karrenbauer - Parameterized Complexity of Biclique Cover and Partition

Paul Duetting and Thomas Kesselheim - Best-Response Dynamics in Combinatorial Auctions with Item Bidding

Thomas Kesselheim and Andreas Tönnis - Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions

Joachim Spoerhase and Sumedha Uniyal - Maximizing a Monotone Submodular Function Subject to a Covering and a Packing Constraint

Ioannis Caragiannis, Aris Filos-Ratsikas, Søren Stiil Frederiksen, Kristoffer Arnsfelt Hansen and Zihan Tan - Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship

Alon Eden, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen and S. Matthew Weinberg - The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders

Nikhil Bansal, Marek Elias, Lukasz Jez and Grigorios Koumoutsos - The (h,k)-Server Problem on Bounded Depth Trees

Dušan Knop, Martin Koutecky and Matthias Mnich - Voting and Bribing in Single-Exponential Time

Amir Ban, Yossi Azar and Yishay Mansour - When Should an Expert Make Predictions?

Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang and Roger Wattenhofer - Min-cost Matching with Delays

Yiannis Giannakopoulos, Elias Koutsoupias and Philip Lazos - Online Market Intermediation

Christian Coester, Elias Koutsoupias and Philip Lazos - The Infinite Server Problem

Martin Böhm, Marek Chrobak, Łukasz Jeż, Fei Li, Jiří Sgall and Pavel Veselý - Online Packet Scheduling with Bounded Delay and Lookahead

Eliav Buchnik and Edith Cohen - Reverse Ranking by Graph Structure: Model and Scalable Algorithms

Artur Czumaj, Pan Peng and Christian Sohler - Relating Two Property Testing Models for Bounded Degree Directed Graphs

Yun Kuen Cheung, Gramoz Goranci, Monika Henzinger, Pan Peng and Harald Räcke - Improved Upper and Lower Bounds for Vertex Sparsifiers

Leo N. Geppert, Katja Ickstadt, Jens Quedenfeld, Alexander Munteanu and Christian Sohler - Random projections for Bayesian regression

Inbal Rika and Robert Krauthgamer - Refined Vertex Sparsifiers of Planar Graphs

Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit and Daniel Vaz - Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs

Alexandr Andoni, Lior Kamma, Robert Krauthgamer and Eric Price- Batch Sparse Recovery, or How to Leverage the Average Sparsity

Michele Borassi, Pierluigi Crescenzi and Luca Trevisan - An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs

Matthias Poloczek, Georg Schnitger, David Williamson and Anke van Zuylen - De-randomizing the Inherently(?) Probabilistic

Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni and Lorenzo Orecchia - Expander via Local Edge Flips

Artur Czumaj and Peter Davies - Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks

Omrit Filtser - On the Chain Pair Simplification Problem

Pascal Lenzner - How to optimally connect to a network under attack

Julian Dibbelt, Ben Strasser and Dorothea Wagner - Customizable Contraction Hierarchies

Adi Akavia, Dan Feldman and Hayim Shaul - Secure Search and Learning on the Cloud: Homomorphic Encryption meets Sketches

Stefan Schmid - Algorithms for Consistent Flow Rerouting

Andreas Emil Feldmann and Rajesh Chitnis - Parameterized Approximations of Symmetric and Planar Directed Steiner Networks

Arnold Filtser - Ramsey Spanning Trees and their Applications

Eliav Buchnik and Edith Cohen - Bootstrapped Graph Diusions: Exposing the Power of Nonlinearity

Martin Böhm and Pavel Veselý - Online Chromatic Number is PSPACE-Complete

Sebastian Schenker, Ralf Borndörfer and Martin Skutella - PolySCIP - Solving Multi-criteria Integer Programs

Pritam Bhattacharya, Subir Ghosh and Bodhayan Roy - Vertex Guarding in Weak Visibility Polygons

Adam Polak - Why is it hard to beat O(n²) for Longest Common Weakly Increasing Subsequence?

João Pedro Pedroso and Shiro Ikeda - Maximum-expectation matching under recourse