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,1}^n$ and uniform distribution on an $n/2$-dimensional linear subspace of ${0,1}^n$ with non-negligible advantage needs $2^{Omega(n)}$ samples or $Omega(n^2)$ memory. Our second result applies to distinguishing outputs of Goldreichs local pseudorandom generator from the uniform distribution on the output domain. Specifically, Goldreichs pseudorandom generator $G$ fixes a predicate $P:{0,1}^k rightarrow {0,1}$ and a collection of subsets $S_1, S_2, ldots, S_m subseteq [n]$ of size $k$. For any seed $x in {0,1}^n$, it outputs $P(x_{S_1}), P(x_{S_2}), ldots, P(x_{S_m})$ where $x_{S_i}$ is the projection of $x$ to the coordinates in $S_i$. 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^epsilon$ memory, can distinguish the output of $G$ from the uniform distribution on ${0,1}^m$ with a large inverse polynomial advantage, for stretch $m le left(frac{n}{t}right)^{frac{(1-epsilon)}{36}cdot t}$ (barring some restrictions on $k$). The lower bound holds in the streaming model where at each time step $i$, $S_isubseteq [n]$ is a randomly chosen (ordered) subset of size $k$ and the distinguisher sees either $P(x_{S_i})$ or a uniformly random bit along with $S_i$. Our proof builds on the recently developed machinery for proving time-space trade-offs (Raz 2016 and follow-ups) for search/learning problems.
تحميل البحث