<div dir="ltr"><div dir="ltr">Hi all — please join us this <b>Wednesday at 12pm</b> for the theory lunch! Details below:<div><br></div><div>***</div><div><b>Date: </b>February 19, 2025, 12pm</div><div><b>Location: </b>JCL 390</div><div><b><br></b></div><div><b>Title: </b>On Sums of INW Pseudorandom Generators</div><div><b><br></b></div><div><b>Speaker: </b>Zelin Lv (UChicago)</div><div><b><br></b></div><div><b>Abstract: </b>We study a new approach for constructing pseudorandom generators (PRGs) that fool constant-width standard-order read-once branching programs (ROBPs). We prove that the bitwise XOR of $t$ independent copies of $X$ fools width-$w$ programs with error $n^{\log(w + 1)} \cdot (\lambda \cdot \log n)^t$. Furthermore, we prove that this shortcoming is not an artifact of our analysis, but rather is an intrinsic limitation of our ``XOR of INW'' approach. That is, no matter how many copies of the INW generator we XOR together, and no matter how we set the expansion parameters, if the generator fools width-$3$ programs and the proof of correctness does not use any properties of the expander graphs except their spectral expansion, then we prove that the seed length of the generator is inevitably $\Omega(\log^2 n)$.<br><br>This is based on joint work with William Hoza.</div></div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"></div></div></div></div></div>