English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given $f:\{-1, 1\}^n \rightarrow \{-1, 1\}$, define the \emph{spectraldistribution} of $f$ to be the distribution on subsets of $[n]$ in which theset $S$ is sampled with probability $\widehat{f}(S)^2$. Then the FourierEntropy-Influence (FEI) conjecture of Friedgut and Kalai (1996) states thatthere is some absolute constant $C$ such that $\operatorname{H}[\widehat{f}^2]\leq C\cdot\operatorname{Inf}[f]$. Here, $\operatorname{H}[\widehat{f}^2]$denotes the Shannon entropy of $f$'s spectral distribution, and$\operatorname{Inf}[f]$ is the total influence of $f$. This conjecture is oneof the major open problems in the analysis of Boolean functions, and settlingit would have several interesting consequences.  Previous results on the FEI conjecture have been largely through directcalculation. In this paper we study a natural interpretation of the conjecture,which states that there exists a communication protocol which, given subset $S$of $[n]$ distributed as $\widehat{f}^2$, can communicate the value of $S$ usingat most $C\cdot\operatorname{Inf}[f]$ bits in expectation.  Using this interpretation, we are able show the following results:  1. First, if $f$ is computable by a read-$k$ decision tree, then$\operatorname{H}[\widehat{f}^2] \leq 9k\cdot \operatorname{Inf}[f]$.  2. Next, if $f$ has $\operatorname{Inf}[f] \geq 1$ and is computable by adecision tree with expected depth $d$, then $\operatorname{H}[\widehat{f}^2]\leq 12d\cdot \operatorname{Inf}[f]$.  3. Finally, we give a new proof of the main theorem of O'Donnell and Tan(ICALP 2013), i.e. that their FEI$^+$ conjecture composes.  In addition, we show that natural improvements to our decision tree resultswould be sufficient to prove the FEI conjecture in its entirety. We believethat our methods give more illuminating proofs than previous results about theFEI conjecture.

Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture