The ell^1-grid junta-size conjecture independent of the codomain size

Let f:ZknZlf:\mathbb{Z}_k^n\to\mathbb{Z}_l satisfy

j=1nEx[f(x)f(xej)]B.\sum_{j=1}^n\mathbb{E}_x\left[|f(x)-f(x\mathbin{\oplus}e_j)|'\right]\leq B.

Here |\cdot|' is the source's normalized difference notation. Junta-size conjecture. The function ff is ϵ\epsilon-close to an MM-junta g:ZknZlg:\mathbb{Z}_k^n\to\mathbb{Z}_l, where

Mexp(C4Bk/ϵ),M\leq\exp(C_4Bk/\epsilon),

for an absolute constant C4C_4. This would remove the dependence on ll from the corresponding junta bound; the source gives no resolution.

Sources & referencesView supporting material

Primary source

Itai Benjamini, David Ellis, Ehud Friedgut, Nathan Keller and Arnab Sen, “Juntas in the ^1-grid and Lipschitz maps between discrete tori”, arXiv:1311.6958 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.