55 citations · 62 across the 8 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018
Static Data Structure Lower Bounds Imply Rigidity
Zeev Dvir, Alexander Golovnev, Omri Weinstein
We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower boun…
cs.DS2018
Local Decodability of the Burrows-Wheeler Transform
Sandip Sinha, Omri Weinstein
The Burrows-Wheeler Transform (BWT) is among the most influential discoveries in text compression and DNA storage. It is a reversible preprocessing step that rearranges an -lett…
cs.DS2018
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
Sepehr Assadi, Xiaorui Sun, Omri Weinstein
A fundamental question that shrouds the emergence of massively parallel computing (MPC) platforms is how can the additional power of the MPC paradigm be leveraged to achieve faster…