The main motivation for studying linear data structures and circuits is the intuition that non-linear advice cannot help in computing a linear operator. Jukna and Schnitger formalized this as a conjecture which states that all circuits computing a linear operator can be ``linearized," with only a constant size blow-up. We ... 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 >>>

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