Workshop Details

I will introduce the theory of average distortion embeddings, which has recently seen rapid development. Average distortion embeddings relax bi-Lipschitz embeddings, and in some cases they allow for much lower distortion. A striking example is Naor’s average John theorem, showing that *any* d-dimensional normed space embeds into Euclidean space with average distortion O(sqrt(log d)), in contrast to the sqrt(d) distortion necessary for a bi-Lipschitz embedding. Additionally, the ell_p and Schatten-p spaces embed into ell_1 with dimension-independent average distortion. At the same time, average distortion embeddings retain some of the algorithmic applications of bi-Lipschitz embeddings. In particular, an average distortion embedding of a metric space M into Euclidean space or into ell_1 implies a data-dependent LSH scheme for M, and, therefore, an efficient near neighbor search data structure. In addition to describing these results, I will also give some open problems about making average distortion embeddings computationally efficient.

Video: [Part one]  [Part two]

I will introduce the theory of average distortion embeddings, which has recently seen rapid development. Average distortion embeddings relax bi-Lipschitz embeddings, and in some cases they allow for much lower distortion. A striking example is Naor’s average John theorem, showing that *any* d-dimensional normed space embeds into Euclidean space with average distortion O(sqrt(log d)), in contrast to the sqrt(d) distortion necessary for a bi-Lipschitz embedding. Additionally, the ell_p and Schatten-p spaces embed into ell_1 with dimension-independent average distortion. At the same time, average distortion embeddings retain some of the algorithmic applications of bi-Lipschitz embeddings. In particular, an average distortion embedding of a metric space M into Euclidean space or into ell_1 implies a data-dependent LSH scheme for M, and, therefore, an efficient near neighbor search data structure. In addition to describing these results, I will also give some open problems about making average distortion embeddings computationally efficient.

Video: [Part one]  [Part two]

We give a new data-dependent LSH for the Earth Mover's Distance, and as a result improve on the approximation of nearest neighbor search for the Earth Mover's Distance by a quadratic factor. Our main technical contribution is to show that for any distribution supported on the EMD metric space, there exists a data-dependent LSH for dense regions of which achieves improved approximation, and that the data-independent LSH actually achieves a better outside of those dense regions. Finally, we “glue” together these two hashing schemes without any additional loss in the approximation.    

[Video]
 

[Video]

I consider two algorithmic problems that are fundamental when dealing with curves in the form of trajectory and time series data: clustering and proximity searching. The Fréchet distance provides a natural way to measure the similarity of curves under varying continuous reparametrizations. However, its mathematical simplicity disguises its computational complexity since it does not naturally behave like a doubling space. I will give a brief overview of recent data structure techniques for different variants of proximity searching under the Fréchet distance. The input is a set of polygonal curves and the query is a polygonal curve and should return the input curves that are closest to the query curve.

[Video]

In this second part of my talk I will review variants of clustering problems using the Fréchet distance measure. For each problem I will discuss what is known in terms of upper and lower bounds on the computational complexity and gauge the space of open problems.

[Video]

Given a d-dimensional continuous (resp. discrete) probability distribution A and a discrete distribution B, the semi-discrete (resp. discrete) optimal transport (OT) problem asks for computing a minimum-cost plan to transport mass from A to B; we assume $n$ to be the number of points in the support of the discrete distributions. This talk presents efficient approximation algorithms for both discrete and semi-discrete OT. It also presents an efficient algorithm for computing a Wasserstein barycenter of a family of discrete distributions.

We present a refined construction of emph{hierarchical probabilistic partitions} with novel properties, substantially stronger than previously known. Our construction provides a family of hierarchical partitions enabling fast dynamic programming algorithms, by guaranteeing that given a sparse set of balls, emph{each cell} of the partition intersects only a small number of balls. The number of balls intersecting a cell is bounded solely as a function of the padding parameter of the partition (which is bounded in particular by the doubling dimension). This is in contrast to the standard guarantee for probabilistic partitions which holds only in expectation. In addition, each cell has a significantly smaller description than in previous constructions.    

[Video]

Designing efficient, effective, and consistent metric clustering algorithms is a significant challenge that is attracting growing attention. Traditional approaches focus on the stability of cluster centers. Unfortunately, this neglects the real-world need for stable point labels. We address this gap by initiating the study of label-consistent metric clustering. We first introduce a new notion of consistency, measuring the label distance between two consecutive solutions. Then, armed with this new definition, we design new consistent algorithms for the classic k-center and k-median problems.

The edit distance (also known as the Levenshtein distance) of two strings is the minimum number of character insertions, deletions, and substitutions needed to transform one string into the other. The textbook algorithm determines the edit distance of two length-n strings in O(n²) time, and any polynomial-factor improvement upon this runtime would violate the Orthogonal Vectors Hypothesis (OVH). An established way of circumventing this lower bound is to consider the bounded edit distance problem, where the running time is expressed in terms of not only the length n of the input strings but also the value k of the edit distance: the classic algorithm of Landau and Vishkin [JCSS’88] achieves O(n + k²) time, which is optimal (up to sub-polynomial factors and conditioned on OVH) as a function of n and k. Another direction, with multiple ground-breaking results over the last decade, is approximating edit distance, where the runtime has been brought down to truly sub-quadratic, almost-linear, and even sub-linear at the cost of introducing approximation ranging from constant-factor to sub-polynomial in n.

In this tutorial, I will focus on the dynamic version of the edit distance problem, which asks to maintain the edit distance of two strings that change dynamically, with each update modeled as a single edit (character insertion, deletion, or substitution). First, I will introduce some basic concepts, such as the edit-distance alignment graph, and a folklore approach that combines the Landau–Vishkin algorithm with a classic dynamic strings implementation to achieve Õ(k²) time per update, where the Õ(·) notation hides factors poly-logarithmic in n. I will then show how the framework of Tiskin [SODA'10], built around efficient min-plus multiplication of unit-Monge matrices, can be applied to achieve a dynamic edit distance algorithm that takes Õ(n) time per update [Charalampopoulos, Kociumaka, and Mozes; CPM'20]. While this update time is conditionally optimal in terms of n, a very recent preprint [Gorbachev and Kociumaka; arXiv'24] achieves Õ(k) time per update using a novel divide-and-conquer approach combined with an application of weight-balanced straight-line programs [Charikar, Lehman, Liu, Panigrahy, Prabhakaran, Sahai, and Shelat; STOC'02]. After providing a high-level overview of this result, I will move on to approximating edit distance in the dynamic setting, where a black-box application of existing tools suffices to achieve O(n^{0.5+ε}) update time for maintaining a constant-factor approximation. Building upon the approach of Andoni, Krauthgamer, and Onak [FOCS'10], the current state-of-the-art algorithm [Kociumaka, Mukherjee, and Saha; FOCS'23] maintains an n^{o(1)}-factor approximation in n^{o(1)} time per update.

Videos: [Part 1]  [Part 2]

The edit distance (also known as the Levenshtein distance) of two strings is the minimum number of character insertions, deletions, and substitutions needed to transform one string into the other. The textbook algorithm determines the edit distance of two length-n strings in O(n²) time, and any polynomial-factor improvement upon this runtime would violate the Orthogonal Vectors Hypothesis (OVH). An established way of circumventing this lower bound is to consider the bounded edit distance problem, where the running time is expressed in terms of not only the length n of the input strings but also the value k of the edit distance: the classic algorithm of Landau and Vishkin [JCSS’88] achieves O(n + k²) time, which is optimal (up to sub-polynomial factors and conditioned on OVH) as a function of n and k. Another direction, with multiple ground-breaking results over the last decade, is approximating edit distance, where the runtime has been brought down to truly sub-quadratic, almost-linear, and even sub-linear at the cost of introducing approximation ranging from constant-factor to sub-polynomial in n.

In this tutorial, I will focus on the dynamic version of the edit distance problem, which asks to maintain the edit distance of two strings that change dynamically, with each update modeled as a single edit (character insertion, deletion, or substitution). First, I will introduce some basic concepts, such as the edit-distance alignment graph, and a folklore approach that combines the Landau–Vishkin algorithm with a classic dynamic strings implementation to achieve Õ(k²) time per update, where the Õ(·) notation hides factors poly-logarithmic in n. I will then show how the framework of Tiskin [SODA'10], built around efficient min-plus multiplication of unit-Monge matrices, can be applied to achieve a dynamic edit distance algorithm that takes Õ(n) time per update [Charalampopoulos, Kociumaka, and Mozes; CPM'20]. While this update time is conditionally optimal in terms of n, a very recent preprint [Gorbachev and Kociumaka; arXiv'24] achieves Õ(k) time per update using a novel divide-and-conquer approach combined with an application of weight-balanced straight-line programs [Charikar, Lehman, Liu, Panigrahy, Prabhakaran, Sahai, and Shelat; STOC'02]. After providing a high-level overview of this result, I will move on to approximating edit distance in the dynamic setting, where a black-box application of existing tools suffices to achieve O(n^{0.5+ε}) update time for maintaining a constant-factor approximation. Building upon the approach of Andoni, Krauthgamer, and Onak [FOCS'10], the current state-of-the-art algorithm [Kociumaka, Mukherjee, and Saha; FOCS'23] maintains an n^{o(1)}-factor approximation in n^{o(1)} time per update.

Videos: [Part 1]  [Part 2]

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings lying in the Boolean hypercube. The edit distance between a pair of strings is defined as the minimum number of character insertion, deletion, and bit flips needed for converting one string into another. In contrast, the Hamming distance between strings is simply the number of bit flips needed to convert them. In this talk I will present a randomized injective embedding of the edit distance into the Hamming distance with a small (quadratic) distortion. Moreover, the embedding output size is linear in the input size and the embedding can be computed using a single pass over the input. If time allows, I will also discuss a possible direction connecting this result and the challenge of proving the hardness of approximation for edit distance. This is based on a joint work with Diptarka Chakraborty and Michal Koucky.

[Video]

The Ulam distance of two permutations on $[n]$ is $n$ minus the length of their longest common subsequence. In this talk, we show that for every $varepsilon>0$, there exists some $alpha>0$, and an infinite set $Gammasubseteq mathbb{N}$, such that for all $ninGamma$, there is an explicit set $C_n$ of $(n!)^{alpha}$ many permutations on $[n]$, such that every pair of permutations in $C_n$ has pairwise Ulam distance at least $(1-varepsilon)cdot n$.

Moreover, we can compute the $i^{text{th}}$ permutation in $C_n$ in $poly(n)$ time and can also decode in $poly(n)$ time, a permutation $pi$ on $[n]$ to its closest permutation $pi^*$ in $C_n$, if the Ulam distance of $pi$ and $pi^*$ is less than $ frac{(1-varepsilon)cdot n}{4} $.

Previously, it was implicitly known by combining works of Goldreich and Wigderson [Israel Journal of Mathematics'23] and Farnoud, Skachek, and Milenkovic [IEEE Transactions on Information Theory'13] in a black-box manner, that it is possible to explicitly construct $(n!)^{Omega(1)}$ many permutations on $[n]$, such that every pair of them have pairwise Ulam distance at least $frac{n}{6}cdot (1-varepsilon)$, for any $varepsilon>0$, and the bound on the distance can be improved to $frac{n}{4}cdot (1-varepsilon)$ if the construction of Goldreich and Wigderson is directly analyzed in the Ulam metric.

[Video]

In this paper we provide a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness). If we take two strings x and y of edit distance at most k then their block decomposition uses the same number of grammars and the i-th grammar of x is the same as the i-th grammar of y except for at most k indexes i. The edit distance of x and y equals to the sum of edit distances of pairs of blocks where x and y differ. Our decomposition can be used to design a sketch of size O(k^2) for edit distance, and also a rolling sketch for edit distance of size O(k^2). The rolling sketch allows to update the sketched string by appending a symbol or removing a symbol from the beginning of the string.

[Video]

A line of work has looked at the problem of recovering an input from distance queries. In this setting, there is an unknown sequence s∈{0,1}≤n, and one chooses a set of queries y∈{0,1}O(n) and receives d(s,y) for a distance function d. The goal is to make as few queries as possible to recover s. Although this problem is well-studied for decomposable distances, i.e., distances of the form d(s,y)=∑ni=1f(si,yi) for some function f, which includes the important cases of Hamming distance, â„“p-norms, and M-estimators, to the best of our knowledge this problem has not been studied for non-decomposable distances, for which there are important special cases such as edit distance, dynamic time warping (DTW), Frechet distance, earth mover's distance, and so on. We initiate the study and develop a general framework for such distances. Interestingly, for some distances such as DTW or Frechet, exact recovery of the sequence s is provably impossible, and so we show by allowing the characters in y to be drawn from a slightly larger alphabet this then becomes possible. In a number of cases we obtain optimal or near-optimal query complexity. We also study the role of adaptivity for a number of different distance functions. One motivation for understanding non-adaptivity is that the query sequence can be fixed and the distances of the input to the queries provide a non-linear embedding of the input, which can be used in downstream applications involving, e.g., neural networks for natural language processing.

Joint work with Zhuangfei Hu, Xinda Li, Hongyang Zhang, and Shufan Zhang

[Video]

A partition $mathcal{P}$ of a metric space $(X,d_X)$ is $(sigma,tau,Delta)$-sparse if each cluster has a diameter at most $Delta$, and every ball with of radius $Delta/sigma$ intersects at most $tau$ clusters. In this talk, we will explore the construction and different applications of sparse partitions in their various forms over the years. As time allows, we will discuss: universal TSP, Steiner point removal, universal Steiner tree, and facility location.

[Video]

We present streaming algorithms for Uniform Facility Location in high-dimensional Euclidean spaces, which compute a constant approximation of the optimal cost in one or a few passes over the input stream while using memory only polynomial (and certainly not exponential) in the dimension. Our algorithms are based on importance sampling of points from the stream such that, informally, points contributing more to the objective are more likely to be sampled than points from "dense clusters", which can be served relatively cheaply. Our sampling procedure relies on consistent hashing (a.k.a. sparse partition) that maps points in R^d into buckets of bounded diameter, with the key property that every point set of small-enough diameter is hashed into a small number of distinct buckets. Still, our one-pass algorithm requires space n^epsilon for a given epsilon > 0 affecting the approximation ratio, and it is open how to compute a constant approximation in one pass using space polynomial in the dimension and polylogarithmic in the number of points n.

[Video]

We design new algorithms for k-clustering in high-dimensional Euclidean spaces. These algorithms run in the Massively Parallel Computation (MPC) model, and are fully scalable, meaning that the local memory in each machine is an arbitrarily small poly(n) for input size n, which importantly may be substantially smaller than k. Our algorithms are fast, i.e., take O(1) rounds, and achieve O(1)-bicriteria approximation for k-Median and for k-Means, while previous work achieves only polylog(n)-approximation or handles special cases.

Our results rely on a fast MPC algorithm for O(1)-approximation of facility location. A primary technical tool that we develop, and may be of independent interest, is a new MPC primitive for geometric aggregation, namely, computing certain statistics on an approximate neighborhood of every data point, which includes range counting and nearest-neighbor search.

Joint work with Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, and Pavel Vesely.

[Video]

This talk will discuss the construction of light weight spanners for points in high dimensional Euclidean spaces. Joint work with Arnold Filtser.

[Video]

We revisit the problem of approximating the edit distance of two strings. This important problem has been extensively studied in the last decades and has seen several breakthroughs in the literature, culminating in a constant-factor approximation in almost-linear time. However, why should we stop here---can we hope for similarly accurate approximation in *sublinear* time? In this talk I present an algorithm with subpolynomial (or even polylogarithmic) approximation factor in truly sublinear time O(n/k + poly(k)). This is *almost-optimal* in the regime where the edit distance k is comparably small (k < n^(1/3)). This result is based on joined work with Karl Bringmann, Alejandro Cassis, Tomasz Kociumaka, and Vasileios Nakos.

[Video]