EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Sparse juntas on the biased hypercube

Irit Dinur, Yuval Filmus, Prahladh Harsha

TheoretiCS · 2024

DOI: 10.46298/theoretics.24.18 ↗

Kurz gefasst

Fachartikel in der Zeitschrift TheoretiCS, 2024. Verfasst von Irit Dinur und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We give a structure theorem for Boolean functions on the $p$-biased hypercube which are $\epsilon$-close to degree $d$ in $L_2$, showing that they are close to sparse juntas. Our structure theorem implies that such functions are $O(\epsilon^{C_d} + p)$-close to constant functions. We pinpoint the exact value of the constant $C_d$. We also give an analogous result for monotone Boolean functions on the biased hypercube which are $\epsilon$-close to degree $d$ in $L_2$, showing that they are close to sparse DNFs. Our structure theorems are optimal in the following sense: for every $d,\epsilon,p$, we identify a class $\mathcal{F}_{d,\epsilon,p}$ of degree $d$ sparse juntas which are $O(\epsilon)$-close to Boolean (in the monotone case, width $d$ sparse DNFs) such that a Boolean function on the $p$-biased hypercube is $O(\epsilon)$-close to degree $d$ in $L_2$ iff it is $O(\epsilon)$-close to a function in $\mathcal{F}_{d,\epsilon,p}$.

Zitieren

APA

Dinur, I., Filmus, Y., & Harsha, P. (2024). Sparse juntas on the biased hypercube. TheoretiCS. https://doi.org/10.46298/theoretics.24.18

Vancouver

Dinur I, Filmus Y, Harsha P. Sparse juntas on the biased hypercube. TheoretiCS. 2024. doi:10.46298/theoretics.24.18

BibTeX
@article{Dinur2024,
  author = {Dinur, Irit and Filmus, Yuval and Harsha, Prahladh},
  title = {Sparse juntas on the biased hypercube},
  journal = {TheoretiCS},
  year = {2024},
  doi = {10.46298/theoretics.24.18}
}
Kostenlos starten →