Under the auspices of the Computational Complexity Foundation (CCF)

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

TR20-003 | 15th January 2020
Giuseppe Persiano, Kevin Yeo

#### Tight Static Lower Bounds for Non-Adaptive Data Structures

Revisions: 1

In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+\Omega(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend ... more >>>

ISSN 1433-8092 | Imprint