The program of the school will consist of two tutorial series related to algorithms and lower bounds. The problems addressed are related using *fine-grained complexity*.
The school will run from Friday to Sunday with a follow-up workshop on Monday afternoon. The workshop is a satellite ICALP
workshop devoted to presentations of own research by selected participants of the school.
We expect the talks to include a fair amount of technical details. The school will also include plenty of time for discussions.

- Barna Saha (University of Massachusetts Amherst): Algorithms for edit distance and related problems
- Omri Weinstein (Columbia University): Data structure lower bounds

**Algorithms for edit distance and related problems (Barna Saha):** Computing edit distance between strings is a basic dynamic programming problem and can be solved exactly in O(n^2) time and O(n) space where n is the length of each string. However, for many applications quadratic time and/or linear space may not be ideal. In the three day tutorial, we will cover some important developments that have occurred over the last decade to improve the space and time complexity of edit distance computation and related hardness results. The tentative list of topics include fast approximation algorithms for edit distance, edit distance computation using sublinear space, edit distance embedding, computing edit distance in the streaming model, SETH based hardness results and generalization of edit distance to languages.

**Data structure lower bounds (Omri Weinstein):** Cell-probe model, static vs. dynamic data structures. Static lower bounds: Richness, Direct-Sum and Cell-Sampling, Round Elimination.
Dynamic lower bounds: The "Chronogram Method" (nearly tight Omega(lg n) lower bound for dynamic 1D range counting, a nearly tight ~Omega(lg^2 n) lower bound for dynamic weighted 2D range counting). Time permitting: Succinct data structures (sparse membership and the dictionary problems). An ~Omega(lg^{1.5} n) lower bound for classical 2D range counting.

**Date: July 6-9, 2018**, lectures start on Friday morning and end by the afternoon session on Sunday.

**Location:** Hostivice-Břve, Sporthotel Břve Hostivice (near Prague, Czech Republic)

The follow-up workshop will take place at Charles University in Malá Strana on Monday afternoon, July 9, 2018.

Friday 6.7.2018 10:00 - 11:15 Omri Weinstein: Data structure lower bounds 11:30 - 12:30 Omri Weinstein: ... 16:15 - 17:45 Introduction, Omri's extras, and Michal Koucky on constant factor approximation of edit distance Saturday 7.7.2018 9:00 - 10:30 Omri Weinstein: Data structure lower bounds 10:50 - 12:00 Omri Weinstein: ... 15:15 - 16:15 Barna Saha: Algorithms for edit distance and related problems 16:30 - 17:45 Barna Saha: ... Sunday 8.7.2018 9:00 - 10:30 Omri Weinstein: Data structure lower bounds 10:50 - 12:00 Omri Weinstein: ... 15:15 - 16:15 Barna Saha: Algorithms for edit distance and related problems 16:15 - 17:45 Barna Saha: ... Monday 9.7.2018 (Charles University, Malostranske nam. 25, Praha 1) 14:00 - 14:30 Diptarka Chakraborty: Tight cell probe bounds for succinct Boolean matrix-vector multiplication 14:30 - 15:00 Burno Loff: Simulation beats richness: New data-structure lower bounds 15:00 - 15:30 Ludmila Glinskih: Lower bound for read-once nondeterministic branching program for satisfiable Tseitin formula using tree-width 16:00 - 16:30 Danil Sagunov: Lower bounds and exact exponential algorithms for the Target Set Selection problem. 16:30 - 17:00 Thatchaphol Saranurak: Dynamic minimum spanning tree in sub-polynomial worst-case update time 17:10 - 17:40 Petr Ryšavý: Estimating Levenshtein distance from sequencing data 17:40 - 18:10 Debarati Das: Approximating edit distance within constant factor in truly sub-quadratic time ABSTRACTS

The school has about 50 confirmed participants and is full. The Monday workshop is open to all registered participants of ICALP pre-workshops.

**Organizers (contact person):**

- Michal Koucký (Charles University),
`koucky@iuuk.mff.cuni.cz`, - Karel Král (Charles University),
`kralka@iuuk.mff.cuni.cz`.

Summer School on Lower Bounds 2015

This workshop receives funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 616787. |