Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Cell-Probe Model:
TR98-028 | 28th May 1998
Paul Beame, Faith Fich

On Searching Sorted Lists: A Near-Optimal Lower Bound

We obtain improved lower bounds for a class of static and dynamic
data structure problems that includes several problems of searching
sorted lists as special cases.

These lower bounds nearly match the upper bounds given by recent
striking improvements in searching algorithms given by Fredman and
Willard's ... more >>>

TR17-066 | 20th April 2017
Josh Alman, Joshua Wang, Huacheng Yu

Cell-Probe Lower Bounds from Online Communication Complexity

Revisions: 1

In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players Bob his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result it presents Bob with the next piece. ... more >>>

TR18-141 | 6th August 2018
Sandip Sinha, Omri Weinstein

Local Decodability of the Burrows-Wheeler Transform

Revisions: 1

The Burrows-Wheeler Transform (BWT) is among the most influential discoveries in text compression and DNA storage. It is a \emph{reversible} preprocessing step that rearranges an $n$-letter string into runs of identical characters (by exploiting context regularities), resulting in highly compressible strings, and is the basis for the ubiquitous \texttt{bzip} program. ... more >>>

TR19-055 | 9th April 2019
Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo

Lower Bounds for Oblivious Near-Neighbor Search

We prove an $\Omega(d \lg n/ (\lg\lg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $\mathit{oblivious}$ approximate-near-neighbor search (ANN) over the $d$-dimensional Hamming cube. For the natural setting of $d = \Theta(\log n)$, our result implies an $\tilde{\Omega}(\lg^2 n)$ lower bound, which is a quadratic improvement over the ... more >>>

ISSN 1433-8092 | Imprint