Alternation, sparsity and sensitivity: bounds and exponential gaps

DOI10.1016/J.TCS.2018.11.015MaRDI QIDQ2632012zbMATH OpenOpenAlexWikidataFDO

Authors Krishnamoorthy Dinesh, Jayalal Sarma M. N.

Publication date 17 May 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.05735

zbMATH Keywords

sensitivity conjectureBoolean function parametersXOR log-rank conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Abstract: $ewcommandspmathsfsparsityewcommandsmathsfsewcommandalmathsfalt$ The well-known Sensitivity Conjecture states that for any Boolean function $f$, block sensitivity of $f$ is at most polynomial in sensitivity of $f$ (denoted by $s(f)$). The XOR Log-Rank Conjecture states that for any $n$ bit Boolean function, $f$ the communication complexity of a related function $f^{oplus}$ on $2n$ bits, (defined as $f^{oplus}(x,y)=f(xoplusy)$) is at most polynomial in logarithm of the sparsity of $f$ (denoted by $sp(f)$). A recent result of Lin and Zhang (2017) implies that to confirm the above conjectures it suffices to 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 this context, we show the following : * There exists a family of Boolean functions for which $al(f)$ is at least exponential in $s(f)$ and $al(f)$ is at least exponential in $logsp(f)$. En route to the proof, we also show an exponential gap between $al(f)$ and the decision 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 $logsp(f)$, the XOR Log-Rank Conjecture is true for functions with the alternation upper bounded by $poly(logn)$. It is easy to observe that the Sensitivity Conjecture is also true for this class of functions. * The starting point for the above result is the observation (derived from Lin and Zhang (2017)) that for any Boolean function $f$ and $mge2$, $deg(f)leal(f)de{g}_2(f)de{g}_m(f)$ where $deg(f)$, $de{g}_2(f)$ and $de{g}_m(f)$ are the degrees of $f$ over $mathbbR$, $mathbb{F}_2$ and $mathbb{Z}_m$ respectively. We also show three further applications of this observation.

Recommendations

• Alternation, sparsity and sensitivity: combinatorial bounds and exponential gaps
• Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers
• On the sensitivity conjecture
• Tighter relations between sensitivity and other complexity measures

Cites work

• scientific article; zbMATH DE number 3829252 (Why is no real title available?)
• scientific article; zbMATH DE number 6789278 (Why is no real title available?)
• scientific article; zbMATH DE number 3319974 (Why is no real title available?)
• A New Approach to the Sensitivity Conjecture
• Analysis of Boolean Functions
• Boolean function complexity. Advances and frontiers.
• CREW PRAM<scp>s</scp> and Decision Trees
• Communication complexities of symmetric XOR functions
• Communication complexity and combinatorial lattice theory
• Complexity measures and decision tree complexity: a survey.
• Constant depth circuits, Fourier transform, and learnability
• Learning circuits with few negations
• Limiting Negations in Formulas
• Negation-limited formulas
• On the Inversion Complexity of a System of Functions
• On the parity complexity measures of Boolean functions
• On the sensitivity conjecture for disjunctive normal forms
• On the sensitivity conjecture for read-\(k\) formulas
• On the sensitivity of cyclically-invariant Boolean functions
• Properties and applications of Boolean function composition
• Quantum lower bounds by polynomials
• Query complexity of matroids
• Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers
• Sensitivity versus certificate complexity of Boolean functions
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Spectral analysis of Boolean functions as a graph eigenvalue problem
• The critical complexity of graph properties
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(2)

• Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers
• Alternation, sparsity and sensitivity: combinatorial bounds and exponential gaps

This page was built for publication: Alternation, sparsity and sensitivity: bounds and exponential gaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2632012)