[Theory] [Theory Lunch] Zelin Lv, Wednesday 2/19, 12-1pm, JCL 390

[Gabe Schoenbach via Theory]

Hi all — please join us this *Wednesday at 12pm* for the theory
lunch! Details below:

***
*Date: *February 19, 2025, 12pm
*Location: *JCL 390

*Title: *On Sums of INW Pseudorandom Generators

*Speaker: *Zelin Lv (UChicago)

*Abstract: *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)$.

This is based on joint work with William Hoza.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250217/c8edf008/attachment.html>