Paul Beame, Faith Fich

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

Josh Alman, Joshua Wang, Huacheng Yu

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

Sandip Sinha, Omri Weinstein

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

Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo

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