We introduce and initiate the study of a new model of reductions called the random noise model. In this model, the truth table $T_f$ of the function $f$ is corrupted on a randomly chosen $\delta$-fraction of instances. A randomized algorithm $\mathcal{A}$ is a $\left(t, \delta, 1-\varepsilon\right)$-recovery reduction for $f$ if:

... more >>>

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