Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > FORBIDDEN PATTERNS:
Reports tagged with Forbidden Patterns:
TR06-110 | 15th August 2006
Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai

#### Improved Algorithms for Optimal Embeddings

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 >>>

TR19-134 | 4th October 2019
Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, Erik Waingarten

#### Finding monotone patterns in sublinear time

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 >>>

ISSN 1433-8092 | Imprint