[Theory] [Theory Lunch] William Hoza, Wednesday 1/29, 12-1pm, JCL 298

[Gabe Schoenbach via Theory]

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

***
*Date: *January 29, 2025, 12pm
*Location: *JCL 298

*Title: *Fooling Near-Maximal Decision Trees

*Speaker: *William Hoza (UChicago)

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

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)$.

Paper link: https://eccc.weizmann.ac.il/report/2025/003/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250127/1b337bfb/attachment.html>