We analyze the Fourier growth, i.e. the $L_1$ Fourier weight at level $k$ (denoted $L_{1,k}$), of various well-studied classes of "structured" $\mathbb{F}_2$-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [CHHL19,CHLT19,CGLSS20] which show that upper bounds on Fourier growth (even at ... more >>>

Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021] ) is a refutational proof system for quantified Boolean formulas (QBF). Each line of MRes consists of clauses with only existential literals, together with information of countermodels stored as merge maps. As a result, MRes has strategy extraction by design. The ... more >>>

The classic Impagliazzo--Nisan--Wigderson (INW) psesudorandom generator (PRG) (STOC `94) for space-bounded computation uses a seed of length $O(\log n \cdot \log(nwd/\varepsilon))$ to fool ordered branching programs of length $n$, width $w$, and alphabet size $d$ to within error $\varepsilon$. A series of works have shown that the analysis of the ... more >>>