Menu

Programme

Tuesday 10 July Wednesday 11 July Thursday 12 July Friday 13 July

Sun 1

S1

Sun 2

S2

Earth

E

Jupiter

J

8:15–8:30
Opening
8:30

Invited talk

Richard Ryan Williams:

Lower Bounds by Algorithm Design: A Progress Report

Chair: D. Marx

9:30–10:00
Coffee break

Track A

Chair: D. Marx

Track A

Chair: J. Suomela

Track B

Chair: A. Muscholl

Track A

Chair: E. Ben-Sasson

10:00
10:25
10:50
11:15
11:40

A. Schmid and J. M. Schmidt:

Computing Tutte Paths

J. Fox, T. Roughgarden, C. Seshadhri, F. Wei and N. Wein:

Finding Cliques in Social Networks: A New Distribution-Free Model

T. Johnson, M. T. Goodrich, W. E. Devanny, J. J. B. Vial and D. Eppstein:

Optimally Sorting Evolving Data

P. Gawrychowski, G. Landau, W.-K. Sung and O. Weimann:

A Faster Construction of Greedy Consensus Tree

Talk moved to Thursday 11:40.

M. E. Descotte, D. Figueira and G. Puppis:

Resynchronizing Classes of Word Relations

E. Boyle, A. Jain, M. Prabhakaran and C.-H. Yu:

The Bottleneck Complexity of Secure Multiparty Computation

D. Micciancio and J. Sorrell:

Ring packing and amortized FHEW bootstrapping

12:00–13:30
Lunch break

Track A

Chair: P. Sankowski

Track A

Chair: M. Jerrum

Track B

Chair: D. Sannella

Track A

Chair: E. Ben-Sasson

13:30
13:55
14:20

M. Grohe, D. Neuen, P. Schweitzer and D. Wiebking:

An improved isomorphism test for bounded-tree-width graphs

H. Dell, M. Grohe and G. Rattan:

Lovász Meets Weisfeiler and Leman

A. Kolla, I. Koutis, V. Madan and A. K. Sinop:

Spectrally Robust Graph Isomorphism

L. Elisa Celis, D. Straszak and N. K. Vishnoi:

Ranking with Fairness Constraints

S. Staton, D. Stein, H. Yang, N. Ackerman, C. Freer and D. Roy:

The Beta-Bernoulli process and algebraic effects

A. Aguirre, G. Barthe, J. Hsu and A. Silva:

Almost Sure Productivity

L. Daviaud, R. Lazić, M. Jurdziński, F. Mazowiecki, G. Perez and J. Worrell:

When is Containment Decidable for Probabilistic Automata?

14:40–14:50
Short break

Track A

Chair: P. Sankowski

Track A

Chair: R. Williams

Track B

Chair: P.-L. Curien

Track A

Chair: P. Golovach

14:50
15:15
15:40

D. Chakrabarty and M. Negahbani:

Generalized Center Problems with Outliers

S. Almagor, D. Chistikov, J. Ouaknine and J. Worrell:

O-Minimal Invariants for Linear Loops

J. Gajarský, S. Kreutzer, J. Nešetřil, P. Ossona de Mendez, M. Pilipczuk, S. Siebertz and S. Toruńczyk:

First-order interpretations of bounded expansion classes

E. Ben-Sasson, I. Bentov, Y. Horesh and M. Riabzev:

Fast Reed-Solomon Interactive Oracle Proofs of Proximity

16:00–16:45
Coffee break
16:45–17:45
A special session in honor of Prof. Maurice Nivat

Chair: D. Sannella

Pierre-Louis Curien:

Un honnête homme

(talk will be in English)

Giorgio Ausiello:

Maurice Nivat: Building a scientific community

18:00–20:00
Welcome party
8:30

Invited talk

Jaroslav Nešetřil:

Sparsity - an algorithmic perspective

Chair: D. Marx

9:30–10:00
Coffee break

Track A

Chair: D. Marx

Track A

Chair: S. Venkatasubramanian

Track B

Chair: A. Kučera

Track C

Chair: G. Mertzios

10:00
10:25
10:50
11:15
11:40

J. Chen, D. Hermelin, M. Sorge and H. Yedidsion:

How hard is it to satisfy (almost) all roommates?

E. Eiben and I. Kanj:

How to navigate through obstacles?

P. Bose, P. Carmi, V. Dujmovic, S. Mehrabi, F. Montecchiani, P. Morin and L. Schultz:

Geodesic Obstacle Representation of Graphs

T. Biedl, A. Biniaz, R. Cummings, A. Lubiw, F. Manea, D. Nowotka and J. Shallit:

Rollercoasters and Caterpillars

T. M. Chan, Y. Nekrich, S. Rahul and K. Tsakalidis:

Orthogonal Point Location and Rectangle Stabbing Queries in 3-d

N. Mamano, D. Eppstein, M. Goodrich and G. Barequet:

Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

A. Grandjean, B. Hellouin de Menibus and P. Vanier:

Aperiodic Points in \(\mathbb{Z}^2\)-subshifts

M. Hoyrup, D. Nava Saucedo and D. Stull:

Semicomputable geometry

T. Harks, M. Hoefer, A. Huber and M. Surek:

Efficient Black-Box Reductions for Separable Cost Sharing

G. Christodoulou, M. Gairing, Y. Giannakopoulos and P. Spirakis:

The Price of Stability of Weighted Congestion Games

R. Colini-Baldeschi, M. Klimm and M. Scarsini:

Demand-Independent Optimal Tolls

12:00–13:30
Lunch break

Track A

Chair: F. Eisenbrand

Track A

Chair: M. Farach-Colton

Track B

Chair: S. Lasota

Track A

Chair: M. Jerrum

13:30
13:55
14:20

F. Fomin, P. Golovach and F. Panolan:

Parameterized Low-Rank Binary Matrix Approximation

D. Lokshtanov, Ramanujan M. S., S. Saurabh, R. Sharma and M. Zehavi:

Brief Announcement: Treewidth Modulator: Emergency Exit for DFVS

S. Chaplick, M. De, A. Ravsky and J. Spoerhase:

Brief Announcement: Approximation Schemes for Geometric Coverage Problems

B. Feldkord, M. Feldotto, A. Gupta, G. Guruganesh, A. Kumar, S. Riechers and D. Wajc:

Fully-Dynamic Bin Packing with Little Repacking

W. Czerwiński, P. Hofman and G. Zetzsche:

Unboundedness problems for languages of vector addition systems

S. Datta, A. Mukherjee, N. Vortmeier and T. Zeume:

Reachability and Distances under Multiple Changes

P. Gregor, S. Jäger, T. Mütze, J. Sawada and K. Wille:

Gray codes and symmetric chains

14:40–14:50
Short break

Track A

Chair: G. F. Italiano

Track A

Chair: M. Halldórsson

Track B

Chair: J.-F. Raskin

Track A

Chair: B. Patt-Shamir

14:50
15:15
15:40

F. Eisenbrand, C. Hunkenschröder and K.-M. Klein:

Faster Algorithms for Integer Programs with Block Structure

J. Fearnley, M. Gairing, M. Mnich and R. Savani:

Reachability Switching Games

M. Fränzle, M. Shirmohammadi, M. Swaminathan and J. Worrell:

Costs and Rewards in Priced Timed Automata

A. Bar-On, I. Dinur, O. Dunkelman, R. Hod, N. Keller, E. Ronen and A. Shamir:

Tight Bounds on Online Checkpointing Algorithms

B. Gärtner, T. D. Hansen, P. Hubáček, K. Král, H. Mosaad and V. Slívová:

ARRIVAL: Next Stop in CLS

16:00–16:30
Coffee break
16:30–19:00
EATCS general assembly
8:30

Invited talk

Sam Staton:

Probability theory from a programming perspective

Chair: D. Sannella

9:30–10:00
Coffee break

Track A

Chair: S. Solomon

Track A

Chair: P. Pudlak

Track B

Chair: M. Benedikt

Track C

Chair: M. Gairing

10:00
10:25
10:50
11:15
11:40

T. Bläsius, C. Freiberger, T. Friedrich, M. Katzmann, F. Montenegro-Retana and M. Thieffry:

Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry

L. Duraj, G. Gutowski and J. Kozik:

A note on two-colorability of nonuniform hypergraphs

A. Blumensath and F. Wolf:

Bisimulation Invariant Monadic-Second Order Logic in the Finite

Talk was cancelled.

Ramanujan M. S., D. Lokshtanov, S. Saurabh and M. Zehavi:

Reducing CMSO Model Checking to Highly Connected Graphs

S. Dehghani, S. Ehsani, M. Hajiaghayi, V. Liaghat and S. Seddighin:

Greedy Algorithms for Online Survivable Network Design

B. Aronov, G. Bar-On and M. Katz:

Resolving SINR Queries in a Dynamic Setting

M. M. Halldorsson, G. Kortsarz, P. Mitra and T. Tonoyan:

Spanning Trees With Edge Conflicts and Wireless Connectivity

E. C. Akrida, G. Mertzios, P. Spirakis and V. Zamaraev:

Temporal Vertex Covers and Sliding Time Windows

M. Bateni, S. Behnezhad, M. Derakhshan, M. Hajiaghayi and V. Mirrokni:

Brief Announcement: MapReduce Algorithms For Massive Trees

12:00–13:30
Lunch break

Track A

Chair: D. Marx

Track A

Chair: M. Koucký

Track B

Chair: S. Staton

Track C

Chair: G. Christodoulou

13:30
13:55
14:20
14:55

A. Conway, M. Farach-Colton and P. Shilane:

Optimal Hashing in External Memory

A. Aamand, M. B. T. Knudsen and M. Thorup:

Power of d Choices with Simple Tabulation

S. Ganguly and D. Woodruff:

High Probability Frequency Moment Sketches

A. Blum, V. Braverman, A. Kumar, H. Lang and L. Yang:

Approximate Convex Hull of Data Streams

V. Braverman, E. Viola, D. P. Woodruff and L. Yang:

Revisiting Frequency Moment Estimation in Random Order Streams

T. Place and M. Zeitoun:

Separating without any ambiguity

A. Amarilli and C. Paperman:

Topological Sorting with Regular Constraints

S. A. Amiri, S. Dudycz, S. Schmid and S. Wiederrecht:

Congestion-Free Rerouting of Flows on DAGs

O. Kupferman and G. Vardi:

The Unfortunate-Flow Problem

15:15–15:45
Coffee break
15:45–17:45
Awards session
15:45

ICALP Best Paper Awards

Appointment of EATCS Fellows

EATCS Distinguished Dissertation Award

Bas Ketsman, Ilya Razenshteyn, Aviad Rubinstein

16:15

Presburger Award

Alexander Mądry

16:45

EATCS Award

Noam Nisan

17:15

Gödel Prize

Oded Regev

19:00–22:00
Conference dinner
8:30

Invited talk

Alexander A. Schwarzmann:

Consistent Distributed Memory Services: Resilience and Efficiency

Chair: C. Kaklamanis

9:30–10:00
Coffee break

Track A

Chair: S. Leonardi

Track A

Chair: Z. Dvořák

Track A

Chair: A. Bogdanov

Track C

Chair: A. Schwarzmann

10:00

Z. K. Koh and L. Sanità:

Stabilizing Weighted Graphs

U. Feige, B. Patt-Shamir and S. Vardi:

On the Probe Complexity of Local Computation Algorithms

S. Bouchard, Y. Dieudonne and A. Lamani:

Byzantine Gathering in Polynomial Time

10:25
10:50
11:15
11:40

K. Onak, B. Schieber, S. Solomon and N. Wein:

Fully Dynamic MIS in Uniformly Sparse Graphs

S. Har-Peled, P. Indyk and S. Mahabadi:

Approximate Sparse Linear Regression

V. Nakos, X. Shi, D. P. Woodruff and H. Zhang:

Improved Algorithms for Adaptive Compressed Sensing

A. Aamand, N. Hjuler, J. Holm and E. Rotenberg:

One-Way Trail Orientations

A. Adamaszek, M. Mnich and K. Paluch:

New Approximation Algorithms for (1,2)-TSP

A. Bhaskara, S. Daruki and S. Venkatasubramanian:

Sublinear Algorithms for MAXCUT and Correlation Clustering

I. Diakonikolas, T. Gouleakis, J. Peebles and E. Price:

Sample-Optimal Identity Testing with High Probability

A. Bhattacharyya, S. Ghoshal, Karthik C. S. and P. Manurangsi:

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

O. Grossman, B. Haeupler and S. Mohanty:

Improved Algorithms for the Noisy Broadcast Model under Erasures

S. Das, D. Dereniowski and P. Uznański:

Brief Announcement: Energy Constrained Depth First Search

12:00–13:30
Lunch break

Track A

Chair: D. Stefankovic

Track A

Chair: P. Golovach

Track A

Chair: M. Koucký

Track C

Chair: M. Mosteiro

13:30
13:55

P. Gawrychowski, L. Markin and O. Weimann:

A Faster FPTAS for #Knapsack

S.-W. Cheng and Y. Mao:

Restricted Max-Min Fair Allocation

M. Ando, A. Lysyanskaya and E. Upfal:

Practical and Provably Secure Onion Routing

S. Patel, G. Persiano and K. Yeo:

CacheShuffle: A Family of Oblivious Shuffles

14:15–14:45
Coffee break
14:45

Track C - Best Paper

D. Kowalski and M. A. Mosteiro:

Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations

Chair: C. Kaklamanis

15:10

Track A - Best Student Paper

S. Garg:

Quasi-PTAS for Scheduling with Precedences using LP Hierarchies

Chair: D. Marx

15:35

Track A - Best Paper

H. Guo and M. Jerrum:

A polynomial-time approximation algorithm for all-terminal network reliability

Chair: D. Marx