Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai

In the last decade, the notion of metric embeddings with

small distortion received wide attention in the literature, with

applications in combinatorial optimization, discrete mathematics, functional

analysis and bio-informatics. The notion of embedding is, given two metric

spaces on the same number of points, to find a bijection that minimizes

more >>>

Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, Erik Waingarten

We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed $k \in \mathbb{N}$ and $\varepsilon > 0$, we show that the non-adaptive query complexity of finding a length-$k$ monotone subsequence of $f \colon [n] \to \mathbb{R}$, assuming that $f$ is $\varepsilon$-far ... more >>>