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

J. Chuzhoy, D. H.K. Kim and R. Nimavat:

Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary

A. Schmid and J. M. Schmidt:

Computing Tutte Paths

P. Sankowski:

NC Algorithms for Weighted Planar Perfect Matching and Related Problems

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

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

A. Louis and R. Venkat:

Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery

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

Optimally Sorting Evolving Data

M. Charikar, O. Geri, M. Kim and W. Kuszmaul:

On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings

P. Gawrychowski and P. Uznański:

Towards Unified Approximate Pattern Matching for Hamming and \(L_1\) Distance

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

A Faster Construction of Greedy Consensus Tree

B. Dudek and P. Gawrychowski:

Edit Distance between Unrooted Trees in Cubic Time

Talk moved to Thursday 11:40.

M. Raskin:

A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton

G. Douéneau-Tabot:

On the complexity of infinite advice strings

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

Resynchronizing Classes of Word Relations

Track B - Best Student Paper

S. Winter:

Uniformization Problems for Synchronizations of Automatic Relations on Words

C. Rösner and M. Schmidt:

Privacy preserving clustering with constraints

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

A. Romashchenko and M. Zimand:

An operational characterization of mutual information in algorithmic information theory

B. Berger and Z. Brakerski:

Brief Announcement: Zero-Knowledge Protocols for Search Problems

N. Agarwal, S. Anand and M. Prabhakaran:

Brief Announcement: On Secure m-Party Computation, Commuting Permutation Systems and Unassisted Non-Interactive MPC

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

J. Byrka, P. Skowron and K. Sornat:

Proportional Approval Voting, Harmonic k-median, and Negative Association

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

Ranking with Fairness Constraints

J. Chen, B. Li, Y. Li and P. Lu:

Brief Announcement: Bayesian Auctions with Efficient Queries

D. Graf, K. Labib and P. Uznański:

Brief Announcement: Hamming distance completeness and sparse matrix multiplication

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?

B. Haeupler, A. Shahrasbi and M. Sudan:

Synchronization Strings: List Decoding for Insertions and Deletions

B. Haeupler, A. Shahrasbi and E. Vitercik:

Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions

S. Raskhodnikova and N. Varma:

Brief Announcement: Erasure-Resilience Versus Tolerance to Errors

J. Blocki, V. Gandikota, E. Grigorescu and S. Zhou:

Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels; TALK CANCELLED

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

B. Gamlath, S. Huang and O. Svensson:

Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering

D. Chakrabarty and Ch. Swamy:

Interpolating between \(k\)-Median and \(k\)-Center: Approximation Algorithms for Ordered \(k\)-Median

S. Liu:

Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT

A. Bogdanov:

Small bias requires large formulas

A. Abboud and K. Bringmann:

Tighter Connections Between Formula-SAT and Shaving Logs

S. Kiefer:

On Computing the Total Variation Distance of Hidden Markov Models

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

T. Gur, Y. Liu and R. Rothblum:

An Exponential Separation Between MA and AM Proofs of Proximity

R. Gurjar, T. Thierauf and N. Vishnoi:

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

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?

J. Jeong, E. J. Kim and S.-I. Oum:

Finding branch-decompositions of matroids, hypergraphs, and more

E. Eiben and I. Kanj:

How to navigate through obstacles?

F. Reidl and M. Wahlström:

Parameterized Algorithms for Zero Extension and Metric Labelling Problems

M. Xiao and H. Nagamochi:

Brief Announcement: Bounded-Degree Bipartition is Fixed-Parameter Tractable

A. Babay, M. Dinitz and Z. Zhang:

Brief Announcement: Characterizing Demand Graphs for (Fixed-Parameter) Shallow-Light Steiner Network

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

Geodesic Obstacle Representation of Graphs

P. Agarwal, H. Kaplan and M. Sharir:

Union of hypercubes and 3d Minkowski sums with random sizes

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

G. Sénizergues and A. Weiss:

The isomorphism problem for finite extensions of free groups is in PSPACE

I. Klimann:

To Infinity and Beyond

S.-K. Ko, R. Niskanen and I. Potapov:

On the Identity Problem for the Special Linear Group and the Heisenberg Group

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

V. Bilò, L. Moscardelli and C. Vinci:

Uniform Mixed Equilibria in Network Congestion Games with Link Failures

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

T. Kesselheim and B. Kodric:

Price of Anarchy for Mechanisms with Risk-Averse Agents

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

M. Lampis:

Finer Tight Bounds for Coloring on Clique-Width

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

Z. Huang, Z. G. Tang, X. Wu and Y. Zhang:

Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals

A. Gupta, R. Mehta and M. Molinaro:

Maximizing Profit with Convex Costs in the Random-order Model

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

J. Leroux:

Polynomial Vector Addition Systems With States

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

R. Arnon-Friedman and H. Yuen:

Noise-tolerant testing of high entanglement of formation

Ch. Nirkhe, U. Vazirani and H. Yuen:

Approximate low-weight check codes and circuit lower bounds for noisy ground states

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

M. Koutecky, A. Levin and S. Onn:

A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs

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

Faster Algorithms for Integer Programs with Block Structure

H. Fu, J. Li and P. Xu:

A PTAS for a Class of Stochastic Dynamic Programs

T. Soma and Y. Yoshida:

A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity

R. Ostrovsky, Y. Rabani and A. Yousefi:

Strictly Balancing Matrices in Polynomial Time Using Osborne’s Iteration

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

Reachability Switching Games

L. Clemente and S. Lasota:

Binary reachability of timed pushdown automata via quantifier elimination

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

M. Carmosino, R. Impagliazzo and M. Sabin:

Fine-Grained Derandomization: From Problem-Centric Complexity to Resource-Centric Complexity

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

P. Gawrychowski and A. Karczmarz:

Improved Bounds for Shortest Paths in Dense Distance Graphs

R. Duan, K. Lyu and Y. Xie:

Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs

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

R. Duan and H. Ren:

Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time

R. Duan, Y. Gu and L. Zhang:

Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs

M. Forbes, S. Ghosh and N. Saxena:

Towards blackbox identity testing of log-variate circuits

A. Bhangale:

NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors

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

A note on two-colorability of nonuniform hypergraphs

Z. Dvorak and K.-I. Kawarabayashi:

Additive non-approximability of chromatic number in proper minor-closed classes

S. Chillara, N. Limaye and S. Srinivasan:

A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas

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

A. Atserias, S. Kreutzer and M. Noy:

On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface

D. Kuske and N. Schweikardt:

Gaifman normal forms for counting extensions of first-order logic

M. Skrzypczak:

Unambiguous languages exhaust the index hierarchy

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

R. B. Basat, G. Einziger and R. Friedman:

Brief Announcement: Give Me Some Slack: Efficient Network Measurements

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

D. Kane, S. Lovett and S. Moran:

Generalized comparison trees for point-location problems

S. Walzer:

Load Thresholds for Cuckoo Hashing with Overlapping Blocks

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

S. Golan, T. Kopelowitz and E. Porat:

Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams

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

Revisiting Frequency Moment Estimation in Random Order Streams

Track B - Best Paper

D. Nowotka and A. Saarela:

An optimal bound on the solution sets of one-variable word equations and its consequences

M. Ganardi, D. Hucke and M. Lohrey:

Randomized sliding window algorithms for regular languages

T. Place and M. Zeitoun:

Separating without any ambiguity

A. Amarilli and C. Paperman:

Topological Sorting with Regular Constraints

F. Chierichetti and S. Haddadan:

On the Complexity of Sampling Vertices Uniformly from a Graph

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

M. Charikar and S. Solomon:

Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier

and

M. Arar, S. Chechik, S. Cohen, C. Stein and D. Wajc:

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms

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

M. Gupta and A. Singh:

Generic Single Edge Fault Tolerant Exact Distance Oracle

L. S. Chandran, D. Issac and Y. K. Cheung:

Spanning Tree Congestion and Computation of Generalized Győri-Lovász Partition

H. Fichtenberger, R. Levi, Y. Vasudev and M. Wötzel:

A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error

and

C. Lenzen and R. Levi:

A Centralized Local Algorithm for the Sparse Spanning Graph Problem

M. Parter:

\((\Delta+1)\) Coloring in the Congested Clique Model

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

D. Bilò:

New algorithms for Steiner tree reoptimization

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

F. Mallmann-Trenn, C. Musco and C. Musco:

Eigenvector Computation and Community Detection in Asynchronous Gossip Models

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

Improved Algorithms for the Noisy Broadcast Model under Erasures

E. Ben-Sasson and E. Saig:

Brief Announcement: Towards an Abstract Model of User Retention Dynamics

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

H. Guo and M. Jerrum:

Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling

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

A Faster FPTAS for #Knapsack

S.-W. Cheng and Y. Mao:

Restricted Max-Min Fair Allocation

A. Gupta, A. Kumar and J. Li:

Non-Preemptive Flow-Time Minimization via Rejections

K. Hayashi:

A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes

M. Backens:

A complete dichotomy for complex-valued Holant^c

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