Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > THOMAS ROTHVOSS:
All reports by Author Thomas Rothvoss:

TR21-102 | 13th July 2021
Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff

Tight bounds on the Fourier growth of bounded functions on the hypercube

Revisions: 1

We give tight bounds on the degree \ell homogenous parts f_\ell of a bounded function f on the cube. We show that if f: \{\pm 1\}^n \rightarrow [-1,1] has degree d, then \| f_\ell \|_\infty is bounded by d^\ell/\ell!, and \| \hat{f}_\ell \|_1 is bounded by $d^\ell e^{{\ell+1 \choose 2}} ... more >>>




ISSN 1433-8092 | Imprint