Johnson and Lindenstrauss (Contemporary Mathematics, 1984) showed that for n > m, a scaled random projection A from ℝn to ℝm is an approximate isometry on any set S of size at most exponential in m. If S is larger, however, its points can contract arbitrarily under A. In particular, the hypergrid ([−B, B] ∩ ℤ)n is expected to contain a point that is contracted by a factor of κstat = Θ(B)−1/α, where α = m/n.

We study the complexity of memory checkers with computational security and prove the first general tight lower bound. Memory checkers, first introduced over 30 years ago by Blum, Evans, Gemmel, Kannan, and Naor (FOCS ’91, Algorithmica ’94), allow a user to store and maintain a large memory on a remote and unreliable server by using small trusted local storage. The user can issue instructions to the server and after every instruction, obtain either the correct value or a failure (but not an incorrect answer) with high probability. The main complexity measure of interest is the size of the local storage and the number of queries the memory checker makes upon every logical instruction. The most efficient known construction has query complexity \(O(\log n/\log \log n)\) and local space proportional to a computational security parameter, assuming one-way functions, where n is the logical memory size. Dwork, Naor, Rothblum, and Vaikuntanathan (TCC ’09) showed that for a restricted class of “deterministic and non-adaptive” memory checkers, this construction is optimal, up to constant factors. However, going beyond the small class of deterministic and non-adaptive constructions has remained a major open problem. In this work, we fully resolve the complexity of memory checkers by showing that any construction with local space p and query complexity q must satisfy \(\begin{equation*} p \ge \frac{n}{(\log n)^{O(q)}} \;. \end{equation*}\) This implies, as a special case, that \(q\ge \Omega (\log n/\log \log n)\) in any scheme, assuming that \(p\le n^{1-\varepsilon }\) for \(\varepsilon \gt 0\) . The bound applies to any scheme with computational security, completeness \(2/3\) , and inverse polynomial in n soundness (all of which make our lower bound only stronger). We further extend the lower bound to schemes where the read complexity \(q_r\) and write complexity \(q_w\) differ. For instance, we show the tight bound that if \(q_r=O(1)\) and \(p\le n^{1-\varepsilon }\) for \(\varepsilon \gt 0\) , then \(q_w\ge n^{\Omega (1)}\) . This is the first lower bound, for any non-trivial class of constructions, showing a read-write query complexity trade-off. Our proof is via a delicate compression argument showing that a “too good to be true” memory checker can be used to compress random bits of information. We draw inspiration from tools recently developed for lower bounds for relaxed locally decodable codes. However, our proof itself significantly departs from these works, necessitated by the differences between settings.

We study the complexity of memory checkers with computational security and prove the first general tight lower bound.

We show direct and conceptually simple reductions between the classical learning with errors (LWE) problem and its continuous analog, CLWE (Bruna, Regev, Song and Tang, STOC 2021). This allows us to bring to bear the powerful machinery of LWE-based cryptography to the applications of CLWE. For example, we obtain the hardness of CLWE under the classical worst-case hardness of the gap shortest vector problem. Previously, this was known only under quantum worst-case hardness of lattice problems. More broadly, with our reductions between the two problems, any future developments to LWE will also apply to CLWE and its downstream applications. As a concrete application, we show an improved hardness result for density estimation for mixtures of Gaussians. In this computational problem, given sample access to a mixture of Gaussians, the goal is to output a function that estimates the density function of the mixture. Under the (plausible and widely believed) exponential hardness of the classical LWE problem, we show that Gaussian mixture density estimation in $\mathbb{R}^{n}$ with roughly $\log n$ Gaussian components given poly $(n)$ samples requires time quasi-polynomial in n. Under the (conservative) polynomial hardness of LWE, we show hardness of density estimation for $n^{\epsilon}$ Gaussians for any constant $\epsilon>0$, which improves on Bruna, Regev, Song and Tang (STOC 2021), who show hardness for at least $\sqrt{n}$ Gaussians under polynomial (quantum) hardness assumptions. Our key technical tool is a reduction from classical LWE to LWE with k-sparse secrets where the multiplicative increase in the noise is only $O(\sqrt{k})$, independent of the ambient dimension n.