ECCC-Report TR22-034https://eccc.weizmann.ac.il/report/2022/034Comments and Revisions published for TR22-034en-usSun, 06 Mar 2022 05:07:32 +0200
Paper TR22-034
| Fourier Growth of Regular Branching Programs |
Chin Ho Lee,
Edward Pyne,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2022/034We analyze the Fourier growth, i.e. the $L_1$ Fourier weight at level $k$ (denoted $L_{1,k}$), of read-once regular branching programs.
We prove that every read-once regular branching program $B$ of width $w \in [1,\infty]$ with $s$ accepting states on $n$-bit inputs must have its $L_{1,k}$ bounded by
$$
\min\left\{ \Pr[B(U_n)=1] (w-1)^k , s \cdot O\left((n \log n)/k\right)^{\frac{k-1}{2}} \right\}.
$$
For any constant $k$, our result is tight up to constant factors for the AND function on $w-1$ bits, and is tight up to polylogarithmic factors for unbounded width programs. In particular, for $k=1$ we have $L_{1,1}(B)\leq s$, with no dependence on the width $w$ of the program.
Our result gives new bounds on the coin problem and new pseudorandom generators (PRGs). Furthermore, we obtain an explicit generator for unordered permutation branching programs of unbounded width with a constant factor stretch, where no PRG was previously known.
Applying a composition theorem of B{\l}asiok, Ivanov, Jin, Lee, Servedio and Viola (RANDOM 2021), we extend our results to ``generalized group products,'' a generalization of modular sums and product tests.Sun, 06 Mar 2022 05:07:32 +0200https://eccc.weizmann.ac.il/report/2022/034