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

We prove that SVP$_p$ is NP-hard to approximate within a factor of $2^{\log^{1 - \varepsilon} n}$, for all constants $\varepsilon > 0$ and $p > 2$, under standard deterministic Karp reductions. This result is also the first proof that \emph{exact} SVP$_p$ is NP-hard in a finite $\ell_p$ norm. Hardness for ... more >>>