Alternation, sparsity and sensitivity: bounds and exponential gaps

DOI10.1016/J.TCS.2018.11.015zbMATH Open1422.68109arXiv1712.05735OpenAlexW2772048929WikidataQ115566732 ScholiaQ115566732MaRDI QIDQ2632012FDOQ2632012

Krishnamoorthy Dinesh, Jayalal Sarma M. N.

Publication date: 17 May 2019

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Analysis of Boolean Functions
• Boolean function complexity. Advances and frontiers.
• Constant depth circuits, Fourier transform, and learnability
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• CREW PRAM<scp>s</scp> and Decision Trees
• Complexity measures and decision tree complexity: a survey.
• Quantum lower bounds by polynomials
• Communication complexity and combinatorial lattice theory
• On the Inversion Complexity of a System of Functions
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• The critical complexity of graph properties
• Spectral analysis of Boolean functions as a graph eigenvalue problem
• Sensitivity Versus Certificate Complexity of Boolean Functions
• Limiting Negations in Formulas
• Learning circuits with few negations
• Negation-limited formulas
• On the parity complexity measures of Boolean functions
• A New Approach to the Sensitivity Conjecture
• Communication is Bounded by Root of Rank
• Properties and applications of boolean function composition
• On the Sensitivity Conjecture for Disjunctive Normal Forms
• Query Complexity of Matroids
• Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers

Cited In (1)

• Sensitivity, affine transforms and quantum communication complexity

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)