@manuascript {633905,
	title = {Pseudorandomness for read-once, constant-depth circuits},
	journal = {CoRR},
	number = {1504.04675},
	year = {2015},
	abstract = {
	For Boolean functions computed by read-once, depth-D\&nbsp;circuits with unbounded fan-in over the de Morgan basis, we present an explicit pseudorandom generator with seed length \(\tilde{O}(\log^{D+1} n)\). The previous best seed length known for this model was\&nbsp;\(\tilde{O}(\log^{D+4} n)\), obtained by Trevisan and Xue (CCC {\textquoteleft}13) for all of\&nbsp;AC0\&nbsp;(not just read-once). Our work makes use of Fourier analytic techniques for pseudorandomness introduced by Reingold, Steinke, and Vadhan (RANDOM {\textquoteleft}13) to show that the generator of Gopalan et al. (FOCS {\textquoteleft}12) fools read-once\&nbsp;AC0. To this end, we prove a new Fourier growth bound for read-once circuits, namely that for every\&nbsp;\(F : \{0,1\}^n\rightarrow \{0,1\}\) computed by a read-once, depth-\(D\)\&nbsp;circuit,



	\(\left|\hat{F}[s]\right| \leq O\left(\log^{D-1} n\right)^k,\)



	where\&nbsp;\(\hat{F}\)\&nbsp;denotes the Fourier transform of\&nbsp;\(F\)\&nbsp;over\&nbsp;\(\mathbb{Z}_2^n\).

},
	url = {https://arxiv.org/abs/1504.04675},
	author = {Sitan Chen and Thomas Steinke and Salil P. Vadhan}
}
