EPAC: Efficient approximation algorithms and circuit complexity

EPAC Workshop: Algorithms and Complexity

28-31 May 2023 Špindlerův Mlýn, Czech Republic

The workshop is focused on recent progress in algorithm design and computational complexity. The main speaker will be Tomasz Kociumaka who will give a tutorial series on recent advances in algorithms for edit distance. We hope to bring together researchers and advanced students with interests in algorithms for strings and complexity theory.

Tutorial

Modern Tools for Computing and Approximating Edit Distance - Tomasz Kociumaka, Max Planck Institute for Informatics, Germany.

Abstract: The edit distance between two strings is defined as the minimum number of character insertions, deletions, and substitutions needed to transform one string into another. It constitutes a fundamental string similarity measure with rich theoretical literature and a variety of applications across several disciplines. The textbook algorithm computes edit distance in quadratic time, and due to conditional lower bounds, there is little hope for significantly faster solutions. Nevertheless, the study of edit distance gives rise to numerous exciting questions, most of which still await definite answers: How fast can we approximate edit distance? Is the problem easier if the edit distance is small? What about maintaining the edit distance of dynamically changing strings? Can we support edits with different weights (costs) of individual edits? Is there hope for a quantum speed-up in computing edit distance?

In this three-day tutorial, I will present the main techniques behind multiple recent developments in the area. On the first day, after covering the basics, I will introduce the seaweed method, originally due to Tiskin, which became the central component of dynamic edit distance algorithms and the state-of-the-art for pattern matching with up to k edits. My second talk will uncover the connections between edit distance and lossless compression schemes, such as LZ77. Highly compressible strings constitute the bottleneck for computing the edit distance (when it is much smaller than the string length), and, in several settings, tools designed for handling compressed data are applied in (conditionally) optimal algorithms for computing edit distance. The last session will be devoted to approximating edit distance. I will introduce precision sampling, a technique dating back to a FOCS'10 paper of Andoni, Krauthgamer, and Onak, which explains most of the recent developments in sublinear-time algorithms for edit distance approximation.

Tentative programme

Program

Sunday, May 28 — Arrival

Monday, May 29:

  • 9:00 - 10:30, Tomasz Kociumaka, Modern Tools for Computing and Approximating Edit Distance

  • 10:30 - 11:00 coffee break

  • 11:00 - 11:30, Elazar Goldenberg, Can You Solve Closest String Faster than Exhaustive Search
  • 11:30 - 12:00, Νick Μatsakis, Better Approximations for Shortest Superstrings

  • 12:00 - 14:00 lunch break

  • 14:00 - 14:30, Bruno Loff, Communication Complexity is NP-Hard
  • 14:30 - 15:00, Lukáš Folwarczný, PPP-Completeness and Extremal Combinatorics

  • 15:00 - 15:30 coffee break

  • 15:30 - 17:30 Open problem session

Tuesday, May 30:
  • 9:00 - 10:30, Tomasz Kociumaka, Modern Tools for Computing and Approximating Edit Distance

  • 10:30 - 11:00 coffee break

  • 11:00 - 11:30, Philip Wellnitz, Faster Pattern Matching under Edit Distance
  • 11:30 - 12:00, Diptarka Chakraborty, Matrix Completion: Approximating the Minimum Diameter

  • 12:00 - 13:30 lunch break

  • 13:30 - 18:00 hike and discussions

Wednesday, May 31:
  • 9:00 - 10:30, Tomasz Kociumaka, Modern Tools for Computing and Approximating Edit Distance

  • 10:30 - 11:00 coffee break
    • >
  • 11:00 - 11:30, Sudatta Bhattacharya, Locally consistent decomposition of strings with applications to edit distance sketching
  • 11:30 - 12:00, Nick Fischer, Sparse pattern matching

  • 12:00 - 13:00 lunch break and departure

Venue

Hotel Erlebachova Bouda, Špindlerův Mlýn, Czech Republic.

Accommodation

Directly at the hotel in any of the Erlebachova bouda or Josefova Bouda. Most participants are expected to make their own reservations at the hotel.

Travel

There is an organized bus from Prague to Erlebachova Bouda on Sunday, May 28th at 15:00. The bus will departure from U Bruskych kasaren, Prague 1 which is near metro and tram station Malostranska:

On Wednesday, May 31st, there will be a returning bus from Erlebachova bouda leaving at 13:00.

On June 2-4, there will be HALG - Highlights of Algorithms 2023 in Prague.

Registration

There is no registration fee. Everybody is welcome to attend but we kindly ask prospective participants to register by filling out this form. Unless directed otherwise by the organizers please arrange your accommodation directly with the hotel. We have some funding to partially cover accommodation cost of students. Get in touch with Michal Koucký by April 24th, 2023 if you want to use that opportunity.

Organizers:

Previous workshops



This project is funded by the Grant Agency of the Czech Republic under the grant agreement no. 19-27871X.