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

At least 12 years old · documented by

Let f:Zkn→Zlf:\mathbb{Z}_k^n\to\mathbb{Z}_l satisfy

∑j=1nEx[∣f(x)−f(x⊕ej)∣′]≤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:Zkn→Zlg:\mathbb{Z}_k^n\to\mathbb{Z}_l, where

M≤exp⁡(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.

References

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.