Invited talk

Richard Ryan Williams:

Lower Bounds by Algorithm Design: A Progress Report

Chair: D. Marx

Track A

Chair: D. Marx

Track A

Chair: J. Suomela

Track B

Chair: A. Muscholl

Track A

Chair: E. Ben-Sasson

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:

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:

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:

B. Dudek and P. Gawrychowski:

Talk moved to Thursday 11:40.

G. Douéneau-Tabot:

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

Track B - Best Student Paper

S. Winter:

Uniformization Problems for Synchronizations of Automatic Relations on Words

C. Rösner and M. Schmidt:

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

D. Micciancio and J. Sorrell:

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:

Track A

Chair: P. Sankowski

Track A

Chair: M. Jerrum

Track B

Chair: D. Sannella

Track A

Chair: E. Ben-Sasson

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

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

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

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:

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:

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

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

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:

Track A

Chair: P. Sankowski

Track A

Chair: R. Williams

Track B

Chair: P.-L. Curien

Track A

Chair: P. Golovach

D. Chakrabarty and M. Negahbani:

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

Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering

D. Chakrabarty and Ch. Swamy:

A. Bogdanov:

A. Abboud and K. Bringmann:

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

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

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

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

Chair: D. Sannella

Pierre-Louis Curien:

Un honnête homme

(talk will be in English)

Giorgio Ausiello:

Maurice Nivat: Building a scientific community