# Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG

arXiv: https://arxiv.org/abs/2002.07235 · HTML: https://mlsanity.com/paper/2002.07235/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2020.

## Built on by (most cited first, 3 of 3)

- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Estimation of Entropy in Constant Space with Improved Sample Complexity](https://mlsanity.com/paper/2205.09804/) (2022)
- [Tight Time-Space Lower Bounds for Constant-Pass Learning](https://mlsanity.com/paper/2310.08070/) (2023)

## Abstract (arXiv)

In this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming setting. In our first result, we show that any algorithm that distinguishes between uniform distribution on 0,1n and uniform distribution on an n/2-dimensional linear subspace of 0,1n with non-negligible advantage needs 2Omega(n) samples or Omega(n2) memory. Our second result applies to distinguishing outputs of Goldreich's local pseudorandom generator from the uniform distribution on the output domain. Specifically, Goldreich's pseudorandom generator G fixes a predicate P:0,1k rightarrow 0,1 and a collection of subsets S1, S2, ldots, Sm subseteq [n] of size k. For any seed x ∈ 0,1n, it outputs P(xS1), P(xS2), ldots, P(xSm) where xSi is the projection of x to the coordinates in Si. We prove that whenever P is t-resilient (all non-zero Fourier coefficients of (-1)P are of degree t or higher), then no algorithm, with <nε memory, can distinguish the output of G from the uniform distribution on 0,1m with a large inverse polynomial advantage, for stretch m ≤ left(fracntright)^frac(1-ε)36· t (barring some restrictions on k). The lower bound holds in the streaming model where at each time step i, Sisubseteq [n] is a randomly chosen (ordered) subset of size k and the distinguisher sees either P(xSi) or a uniformly random bit along with Si. Our proof builds on the recently developed machinery for proving time-space trade-offs (Raz 2016 and follow-ups) for search/learning problems.