Invited talk

Richard Ryan Williams:

Lower Bounds by Algorithm Design: A Progress Report

Track A

Chair:

Track A

Chair:

Track B

Chair:

Track A

Chair:

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

M. Skrzypczak:

Unambiguous languages exhaust the index hierarchy

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

Track A

Chair:

Track A

Chair:

Track B

Chair:

Track A

Chair:

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

Track A

Chair:

Track A

Chair:

Track B

Chair:

Track A

Chair:

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

Pierre-Louis Curien:

Un honnête homme

(talk will be in English)

Giorgio Ausiello:

Maurice Nivat: Building a scientific community