HIGHLIGHTS OF ALGORITHMS

TU Berlin, June 9-11, 2017

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
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
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
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, MA001
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, MA001 Stream B, MA005

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

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

Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi and Dana Ron - Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

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, MA001
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, MA001 Stream B, MA005

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, MA001
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, MA001
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, MA001
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, MA001
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, MA001
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

Veronika Loitzenbauer - 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

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

Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi and Dana Ron - Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

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(n2) for Longest Common Weakly Increasing Subsequence?

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