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/

Global: Zendy Plus annual

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

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

For Boolean functions computed by read-once, depth-$D$ circuits withunbounded fan-in over the de Morgan basis, we present an explicit pseudorandomgenerator with seed length $\tilde{O}(\log^{D+1} n)$. The previous best seedlength known for this model was $\tilde{O}(\log^{D+4} n)$, obtained by Trevisanand Xue (CCC `13) for all of $AC^0$ (not just read-once). Our work makes use ofFourier analytic techniques for pseudorandomness introduced by Reingold,Steinke, and Vadhan (RANDOM `13) to show that the generator of Gopalan et al.(FOCS `12) fools read-once $AC^0$. To this end, we prove a new Fourier growthbound for read-once circuits, namely that for every $F: \{0,1\}^n\to\{0,1\}$computed by a read-once, depth-$D$ circuit,\begin{equation*}\sum_{s\subseteq[n], |s|=k}|\hat{F}[s]|\leO(\log^{D-1}n)^k,\end{equation*} where $\hat{F}$ denotes the Fourier transformof $F$ over $\mathbb{Z}^n_2$.

Pseudorandomness for Read-Once, Constant-Depth Circuits