Summer School on Algorithms and Lower Bounds 2018

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.

Tutorial speakers

  • 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 and location

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.

Tentative programme

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

Participants

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.

Previous school

Summer School on Lower Bounds 2015

Funding info

ERC logo 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. FP7 logo