Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > CHIN HO LEE:
All reports by Author Chin Ho Lee:

TR22-034 | 3rd March 2022
Chin Ho Lee, Edward Pyne, Salil Vadhan

Fourier Growth of Regular Branching Programs

We 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\{ ... more >>>




ISSN 1433-8092 | Imprint