<div dir="ltr"><div>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>January 29, 2025, 12pm</div><div><b>Location: </b>JCL 298</div><div><b><br></b></div><div><b>Title: </b>Fooling Near-Maximal Decision Trees</div><div><b><br></b></div><div><b>Speaker: </b>William Hoza (UChicago)</div><div><b><br></b></div><div><b>Abstract: </b>For any constant $\alpha > 0$, we construct an explicit pseudorandom generator (PRG) that fools $n$-variate decision trees of size $m$ with error $\epsilon$ and seed length $(1 + \alpha) \cdot \log_2 m + O(\log(1/\epsilon) + \log \log n)$. For context, one can achieve seed length $(2 + o(1)) \cdot \log_2 m + O(\log(1/\epsilon) + \log \log n)$ using well-known constructions and analyses of small-bias distributions, but such a seed length is trivial when $m \geq 2^{n/2}$. By combining our new PRG with work by Chen and Kabanets (TCS 2016), we get an explicit PRG that fools circuits of size $2.99\cdot n$ over the $U_2$ basis with error $2^{-\Omega(n)}$ and seed length $(1 - \Omega(1)) \cdot n$.</div><br>Our approach for fooling decision trees is to develop a new variant of the classic concept of almost $k$-wise independence, which might be of independent interest. We say that a distribution $X$ over $\{0, 1\}^n$ is $k$-wise $\epsilon$-probably uniform if every Boolean function $f$ that depends on only $k$ variables satisfies $\mathbb{E}[f(X)] \geq (1 - \epsilon) \cdot \mathbb{E}[f]$. We show how to sample a $k$-wise $\epsilon$-probably uniform distribution using a seed of length $(1 + \alpha) \cdot k + O(\log(1/\epsilon) + \log \log n)$.<br><br>Paper link: <a href="https://eccc.weizmann.ac.il/report/2025/003/">https://eccc.weizmann.ac.il/report/2025/003/</a></div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"></div></div></div></div></div>