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/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

$\newcommand{\sp}{\mathsf{sparsity}}\newcommand{\s}{\mathsf{s}}\newcommand{\al}{\mathsf{alt}}$The well-known Sensitivity Conjecture states that for any Boolean function $f$,block sensitivity of $f$ is at most polynomial in sensitivity of $f$ (denotedby $\s(f)$). The XOR Log-Rank Conjecture states that for any $n$ bit Booleanfunction, $f$ the communication complexity of a related function $f^{\oplus}$on $2n$ bits, (defined as $f^{\oplus}(x,y)=f(x\oplus y)$) is at most polynomialin logarithm of the sparsity of $f$ (denoted by $\sp(f)$). A recent result ofLin and Zhang (2017) implies that to confirm the above conjectures it sufficesto upper bound alternation of $f$ (denoted $\al(f)$) for all Boolean functions$f$ by polynomial in $\s(f)$ and logarithm of $\sp(f)$, respectively. In thiscontext, we show the following :  * There exists a family of Boolean functions for which $\al(f)$ is at leastexponential in $\s(f)$ and $\al(f)$ is at least exponential in $\log \sp(f)$.En route to the proof, we also show an exponential gap between $\al(f)$ and thedecision tree complexity of $f$, which might be of independent interest.  * As our main result, we show that, despite the above gap between $\al(f)$and $\log \sp(f)$, the XOR Log-Rank Conjecture is true for functions with thealternation upper bounded by $poly(\log n)$. It is easy to observe that theSensitivity Conjecture is also true for this class of functions.  * The starting point for the above result is the observation (derived fromLin and Zhang (2017)) that for any Boolean function $f$ and $m \ge 2$,$deg(f)\le \al(f)deg_2(f)deg_m(f)$ where $deg(f)$, $deg_2(f)$ and $deg_m(f)$are the degrees of $f$ over $\mathbb{R}$, $\mathbb{F}_2$ and $\mathbb{Z}_m$respectively. We also show three further applications of this observation.

Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps