We prove a general translation theorem for converting one-way communication lower bounds over a product distribution to dynamic cell-probe lower bounds.

Specifically, we consider a class of problems considered in [Pat10] where:
1. $S_1, \ldots, S_m \in \{0, 1\}^n$ are given and publicly known.
2. $T ... more >>>

We consider a static data structure problem of computing a linear operator under cell-probe model. Given a linear operator $M \in \mathbb{F}_2^{m \times n}$, the goal is to pre-process a vector $X \in \mathbb{F}_2^n$ into a data structure of size $s$ to answer any query $ {\left\langle M_i , X ... more >>>

Quantum computing promises exponential speedups for certain problems, yet fully universal quantum computers remain out of reach and near-term devices are inherently noisy. Motivated by this, we study noisy quantum algorithms and the landscape between BQP and BPP. We build on a powerful technique to differentiate quantum and classical algorithms ... more >>>