We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwise distances. The novelty is studying average-distortion: for any fixed (yet, arbitrary) distribution $\mu$ over the metric, the sketch should not over-estimate distances, and it should (approximately) preserve the average distance with respect to draws from $\mu$. The notion generalizes average-distortion embeddings into $\ell_{1}$ [1], [2] as well as data-dependent locality-sensitive hashing [3], [4], which have been recently studied in the context of nearest neighbor search.•For all $p \in(2, \infty)$ and any c larger than a fixed constant, we give an average-distortion sketch for ($[\Delta]^{d}, \ell_{p}$) with approximation c and bit-complexity poly $\left(2^{p / c} \cdot \log (d \Delta)\right)$, which is provably impossible in (worst-case) sketching.•As an application, we improve on the approximation of sublinear-time data structures for nearest neighbor search over $\ell_{p}$ (for large $p\gt2$). The prior best approximation was $O(p)$ [2], [4], and we show it can be any c larger than a fixed constant (irrespective of p) by using $n^{O(p / c)}$ space.We give some evidence that $2^{\Omega(p / c)}$ space may be necessary by giving a lower bound on average-distortion sketches which produce a certain probabilistic certificate of farness (which our sketches crucially rely on).

We present the first semi-streaming polynomial-time approximation scheme (PTAS) for the minimum feedback arc set problem on directed tournaments in a small number of passes. Namely, we obtain a (1 + ε)-approximation in time O (poly(n) 2^{poly(1/ε)}), with p passes, in n^{1+1/p} ⋅ poly((log n)/ε) space. The only previous algorithm with this pass/space trade-off gave a 3-approximation (SODA, 2020), and other polynomial-time algorithms which achieved a (1+ε)-approximation did so with quadratic memory or with a linear number of passes. We also present a new time/space trade-off for 1-pass algorithms that solve the tournament feedback arc set problem. This problem has several applications in machine learning such as creating linear classifiers and doing Bayesian inference. We also provide several additional algorithms and lower bounds for related streaming problems on directed graphs, which is a largely unexplored territory.

Self-adjusting computation is an approach for automatically producing dynamic algorithms from static ones. It works by tracking control and data dependencies, and propagating changes through the dependencies when making an update. Extensively studied in the sequential setting, some results on parallel self-adjusting computation exist, but are only applicable to limited classes of computations, or are ad-hoc systems with no theoretical analysis of their performance.