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

We prove that the Fourier dimension of any Boolean function with Fouriersparsity $s$ is at most $O\left(s^{2/3}\right)$. Our proof method yields animproved bound of $\widetilde{O}(\sqrt{s})$ assuming a conjecture ofTsang~\etal~\cite{tsang}, that for every Boolean function of sparsity $s$ thereis an affine subspace of $\mathbb{F}_2^n$ of co-dimension $O(\poly\log s)$restricted to which the function is constant. This conjectured bound is tightupto poly-logarithmic factors as the Fourier dimension and sparsity of theaddress function are quadratically separated. We obtain these bounds byobserving that the Fourier dimension of a Boolean function is equivalent to itsnon-adaptive parity decision tree complexity, and then bounding the latter.

Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity