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

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.

Organizers (contact person): Michal Koucký (Charles University).

Participation

We expect about 45 participants. A limited amount of funding is available to support the stay of junior participans at the school. Interested graduate students and postdocs are invited to apply to attend the school by April 15, 2018. They should send their name, affiliation, status (student/postdoc) by email to koucky@iuuk.mff.cuni.cz and arrange with their supervisor to send a supporting letter to the above address. Questions should be directed to the same address.

Tentative program

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.

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