Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Improved Bounds on Fourier Entropy and Min-entropy

Arunachalam, S., Chakraborty, S., Koucký, M., Saurabh, N., & de Wolf, R. (2018). Improved Bounds on Fourier Entropy and Min-entropy. Retrieved from http://arxiv.org/abs/1809.09819.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Forschungspapier
Latex : {Improved Bounds on Fourier Entropy and Min-entropy}

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:1809.09819.pdf (Preprint), 484KB
Name:
arXiv:1809.09819.pdf
Beschreibung:
File downloaded from arXiv at 2018-12-13 08:50
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Arunachalam, Srinivasan1, Autor
Chakraborty, Sourav1, Autor           
Koucký, Michal1, Autor
Saurabh, Nitin2, Autor           
de Wolf, Ronald1, Autor
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Computational Complexity, cs.CC
 Zusammenfassung: Given a Boolean function $f:\{-1,1\}^n\to \{-1,1\}$, the Fourier distribution
assigns probability $\widehat{f}(S)^2$ to $S\subseteq [n]$. The Fourier
Entropy-Influence (FEI) conjecture of Friedgut and Kalai asks if there exist a
universal constant C>0 such that $H(\hat{f}^2)\leq C Inf(f)$, where
$H(\hat{f}^2)$ is the Shannon entropy of the Fourier distribution of $f$ and
$Inf(f)$ is the total influence of $f$.
1) We consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture.
This asks if $H_{\infty}(\hat{f}^2)\leq C Inf(f)$, where
$H_{\infty}(\hat{f}^2)$ is the min-entropy of the Fourier distribution. We show
$H_{\infty}(\hat{f}^2)\leq 2C_{\min}^\oplus(f)$, where $C_{\min}^\oplus(f)$ is
the minimum parity certificate complexity of $f$. We also show that for every
$\epsilon\geq 0$, we have $H_{\infty}(\hat{f}^2)\leq 2\log
(\|\hat{f}\|_{1,\epsilon}/(1-\epsilon))$, where $\|\hat{f}\|_{1,\epsilon}$ is
the approximate spectral norm of $f$. As a corollary, we verify the FMEI
conjecture for the class of read-$k$ $DNF$s (for constant $k$).
2) We show that $H(\hat{f}^2)\leq 2 aUC^\oplus(f)$, where $aUC^\oplus(f)$ is
the average unambiguous parity certificate complexity of $f$. This improves
upon Chakraborty et al. An important consequence of the FEI conjecture is the
long-standing Mansour's conjecture. We show that a weaker version of FEI
already implies Mansour's conjecture: is $H(\hat{f}^2)\leq C
\min\{C^0(f),C^1(f)\}$?, where $C^0(f), C^1(f)$ are the 0- and 1-certificate
complexities of $f$, respectively.
3) We study what FEI implies about the structure of polynomials that
1/3-approximate a Boolean function. We pose a conjecture (which is implied by
FEI): no "flat" degree-$d$ polynomial of sparsity $2^{\omega(d)}$ can
1/3-approximate a Boolean function. We prove this conjecture unconditionally
for a particular class of polynomials.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2018-09-262018
 Publikationsstatus: Online veröffentlicht
 Seiten: 38 p.
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 1809.09819
URI: http://arxiv.org/abs/1809.09819
BibTex Citekey: Arunachalam_arXiv1809.09819
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: