ECCC-Report TR22-109https://eccc.weizmann.ac.il/report/2022/109Comments and Revisions published for TR22-109en-usWed, 27 Jul 2022 15:58:49 +0300
Paper TR22-109
| Searching for Regularity in Bounded Functions |
Siddharth Iyer,
Michael Whitmeyer
https://eccc.weizmann.ac.il/report/2022/109Given a function $f:\mathbb F_2^n \to [-1,1]$, this work seeks to find a large affine subspace $\mathcal U$ such that $f$, when restricted to $\mathcal U$, has small nontrivial Fourier coefficients.
We show that for any function $f:\mathbb F_2^n \to [-1,1]$ with Fourier degree $d$, there exists an affine subspace of dimension at least $ \tilde\Omega(n^{1/d!}k^{-2})$, wherein all of $f$'s nontrivial Fourier coefficients become smaller than $ 2^{-k}$.
To complement this result, we show the existence of degree $d$ functions with coefficients larger than $2^{-d\log n}$ when restricted to any affine subspace of dimension larger than $\Omega(dn^{1/(d-1)})$. In addition, we give explicit examples of functions with analogous but weaker properties.
Along the way, we provide multiple characterizations of the Fourier coefficients of functions restricted to subspaces of $\mathbb F_2^n$ that may be useful in other contexts. Finally, we highlight applications and connections of our results to parity kill number and affine dispersers/extractors.Wed, 27 Jul 2022 15:58:49 +0300https://eccc.weizmann.ac.il/report/2022/109