English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

In this work, we establish lower-bounds against memory bounded algorithms fordistinguishing between natural pairs of related distributions from samples thatarrive in a streaming setting.  In our first result, we show that any algorithm that distinguishes betweenuniform distribution on $\{0,1\}^n$ and uniform distribution on an$n/2$-dimensional linear subspace of $\{0,1\}^n$ with non-negligible advantageneeds $2^{\Omega(n)}$ samples or $\Omega(n^2)$ memory.  Our second result applies to distinguishing outputs of Goldreich's localpseudorandom generator from the uniform distribution on the output domain.Specifically, Goldreich's 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$, itoutputs $P(x_{S_1}), P(x_{S_2}), \ldots, P(x_{S_m})$ where $x_{S_i}$ is theprojection 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 theoutput of $G$ from the uniform distribution on $\{0,1\}^m$ with a large inversepolynomial advantage, for stretch $m \le\left(\frac{n}{t}\right)^{\frac{(1-\epsilon)}{36}\cdot t}$ (barring somerestrictions on $k$). The lower bound holds in the streaming model where ateach time step $i$, $S_i\subseteq [n]$ is a randomly chosen (ordered) subset ofsize $k$ and the distinguisher sees either $P(x_{S_i})$ or a uniformly randombit along with $S_i$.  Our proof builds on the recently developed machinery for proving time-spacetrade-offs (Raz 2016 and follow-ups) for search/learning problems.

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