The conference will start at 8:50am on Monday, June 6, and the last talks will finish around 5:30pm on Wednesday, June 8.

HALG 2016 Program (in pdf format).

All invited talks will take place in Amphitheater Buffon.

All short contributions will take place in Amphitheater 1 and 2 of Building Olympe de Gouges. (This building is less than 5 minutes walk from Amphitheater Buffon.)


Amphitheater Buffon

8:50 –   9:00 Welcome remarks
9:00 – 10:00 Daniel Marx (Hungarian Academy of Sciences)

The optimality program for parameterized algorithms


10:00 – 10:30 Stephan Kreutzer (TU Berlin)

The directed grid theorem (joint work with Ken-ichi Kawarabayashi)


10:30 – 11:00 Coffee break
11:00 – 11:30 Ken-ichi Kawarabayashi (National Institute of Informatics, Japan)

Deterministic global minimum cut of a simple graph in near-linear time (joint work with Mikkel Thorup)


11:30 – 12:00 Clifford Stein (Columbia University)

Faster fully dynamic matchings with small approximation ratios (joint work with Aaron Bernstein)


12:00 – 12:30 Monika Henzinger (Universität Wien)

Using the primal-dual method to design dynamic graph algorithms (joint work with Sayan Bhattacharya and Giuseppe F. Italiano)


12:30 – 14:00 Lunch break
14:00 – 15:00 Costis Daskalakis (MIT)

Reduction from mechanism design to optimization


15:00 – 15:30 Stephen Alstrup (University of Copenhagen)

Recent results in labeling schemes

15:30 – 16:00 Shiri Chechik (Tel Aviv University)

Approximate distance oracles with improved bounds


16:00 – 16:30 Coffee break
16:30 – 17:00 Anupam Gupta (CMU)

Greedy algorithms for Steiner forest (joint work with Amit Kumar)


17:00 – 17:30 Nikhil Bansal (Eindhoven University of Technology)

Minimizing flow-time on unrelated machines (joint work with Janardhan Kulkarni)


17:30 – 18:00 Yossi Azar (Tel Aviv University)

Speed scaling in the non-clairvoyant model (joint work with Nikhil Devanur, Zhiyi Huang, and Debmalya Panigrah)



Amphitheater Buffon

9:00 – 10:00 Virginia Vassilevska Williams (Stanford)

On complexity/hardness in P


10:00 – 10:30 Arturs Backurs (MIT)

Edit distance cannot be computed in strongly subquadratic time (unless SETH is false) (joint work with Piotr Indyk)


10:30 – 11:00 Coffee break
11:00 – 11:30 Ilias Diakonikolas (University of Southern California)

Hypothesis testing for structured probability distributions (joint work with Daniel M. Kane and Vladimir Nikishkin)


11:30 – 12:00 Christian Sohler (TU Dortmund)

Testing cluster structure of graphs (joint work with Artur Czumaj and Pan Peng)


12:00 – 14:00 Lunch break



Amphitheater 1 and 2 of Building Olympe de Gouge

Session A (Amphitheater 1) Session B (Amphitheater 2)
Parinya Chalermsook

Pattern-avoiding Access in Binary Search Trees

Erik Jan van Leeuwen

Do Long Paths Block the Way to Easy Independence?

John Iacono

Weighted Dynamic Finger in Binary Search Trees

Valia Mitsou

Double-exponential and Triple-exponential Bounds for Choosability Problems Parameterized by Treewidth

Ferdinando Cicalese

On the Simultaneous Optimization of Worst and Expected Testing Cost in Decision Tree Problems

Seeun William Umboh

Robust Algorithms for Noisy Minor Free and Bounded Treewidth Graphs

Thatchaphol Saranurak

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

Pavel Dvořák

Parameterized Complexity of Length-bounded Cuts and Multi-cuts


Shashwat Garg

Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems

Rajesh Chitnis

Parameterized and Promised Streaming Algorithms


Khaled Elbassioni

Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-dimension

Mateus de Oliveira Oliveira

An Algorithmic Metatheorem for Directed Treewidth

Samuel Hopkin

SoS and Planted Clique: an Almost Optimal Lower Bound

Pavel Kolev

A Note on Spectral Clustering


Klaus-Tycho Förster

On Consistent Migration of Flows in SDNs

Tselil Schramm

Overcomplete Tensor Decomposition: Fast Spectral Algorithms from Sum-of-Squares Analyses

Amitabh Trehan

Compact Routing Messages in Self-Healing Trees

Aurélien Ooms

Solving k-SUM Using Few Linear Queries

Peter Davies

Faster Deterministic Communication in Radio Networks

Thomas Kesselheim

Secretary Problems with Non-Uniform Arrival Order

Emanuele Natale

Dynamics, Consensus, and Distributed Community Detection

Rani Izsak

The Supermodular Degree


Petr Kuznetsov

On the Space Complexity of Set Agreement

Paul Duetting

Algorithms as Mechanisms: The Price of Anarchy of Relax-and-Round

16:00 – 16:30 Coffee break


16:30 – 17:30 Ryan Williams (Stanford)

New applications of the polynomial method to algorithm design



Amphitheater 1 and 2 of Building Olympe de Gouge

Session A (Amphitheater 1) Session B (Amphitheater 2)
Bartosz Walczak

Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace

Jiří Sgall

General Caching Is Hard: Even with Small Pages


Nicolas Schabanel

Folding Turing is Hard but Feasible

Moti Medina

Better Online Deterministic Packet Routing on Grids

Nithin Varma

Erasure-Resilient Property Testing

Kevin Schewior

Improvements on Online Machine Minimization

Arkadiusz Socała

Tight Lower Bounds on Graph Embedding Problems

Jakub Łącki

Algorithmic Complexity of Power Law Networks

Elazar Goldenberg

Streaming Algorithms for Embedding and Computing Edit Distance in the Low Distance Regime

Sebastian Krinninger

A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

Arnold Filtser

On Notions of Distortion

19:15 – 20:15 Business meeting



Amphitheater Buffon

9:00 –   9:30 Greg Bodwin (Stanford)

The 4/3 additive spanner exponent is tight (joint work with Amir Abboud)


9:30 – 10:00 Huacheng Yu (Stanford)

An improved combinatorial algorithm for Boolean matrix multiplication


10:00 – 10:30 Ola Svensson (EPFL)

Approximating ATSP by relaxing connectivity


10:30 – 11:00 Coffee break


11:00 – 12:00 Aleksander Mądry (MIT)

Fast graph algorithms and continuous optimization


12:00 – 12:30 Shayan Oveis Gharan (University of Washington)

Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP (joint work with Nima Anari)

12:30 – 14:00 Lunch break
14:00 – 15:00 Aaron Sidford (MIT)

Faster algorithms for convex optimization

15:00 – 15:30 David Mount (University of Maryland)

A fast and simple algorithm for computing approximate Euclidean minimum spanning trees (joint work with Sunil Arya)


15:30 – 16:00 Coffee break
16:00 – 16:30 Moshe Lewenstein (Bar Ilan University)

Clustered integer 3SUM via additive combinatorics (joint work with Timothy M. Chan)

16:30 – 17:00 Alexandr Andoni (Columbia University)

Optimal data-dependent hashing for approximate near neighbors (joint work with Ilya Razenshteyn)


17:00 – 17:30 Robert Krauthgamer (Weizmann Institute)

Sketching and embedding are equivalent for norms (joint work with Alexandr Andoni and Ilya P. Razenshteyn)


17:30 Conference adjourned