On the sensitivity conjecture for disjunctive normal forms

DOI10.4230/LIPICS.FSTTCS.2016.15MaRDI QIDQ4636562zbMATH OpenOpenAlexFDO

Authors C. S. Karthik, Sébastien Tavenas

Publication date 19 April 2018

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

zbMATH Keywords

block sensitivityBoolean functionDNFsensitivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Abstract: The sensitivity conjecture of Nisan and Szegedy [CC '94] asks whether for any Boolean function $f$, the maximum sensitivity $s(f)$, is polynomially related to its block sensitivity $bs(f)$, and hence to other major complexity measures. Despite major advances in the analysis of Boolean functions over the last decade, the problem remains widely open. In this paper, we consider a restriction on the class of Boolean functions through a model of computation (DNF), and refer to the functions adhering to this restriction as admitting the Normalized Block property. We prove that for any function $f$ admitting the Normalized Block property, $bs(f)leq4s(f{)}^2$. We note that (almost) all the functions mentioned in literature that achieve a quadratic separation between sensitivity and block sensitivity admit the Normalized Block property. Recently, Gopalan et al. [ITCS '16] showed that every Boolean function $f$ is uniquely specified by its values on a Hamming ball of radius at most $2s(f)$. We extend this result and also construct examples of Boolean functions which provide the matching lower bounds.

Recommendations

• On the sensitivity conjecture
• Sensitivity vs. block sensitivity of Boolean functions
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Tighter relations between sensitivity and other complexity measures
• On the resolution of the sensitivity conjecture

Cited in

(6)

• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Size of sets with small sensitivity: a generalization of Simon's lemma
• Determining the <I>SHOIN(D)</I>-Satisfiability with a Complete Disjunctive Normal Form Group
• On the sensitivity conjecture
• On the sensitivity conjecture for read-k formulas
• A tighter relation between sensitivity complexity and certificate complexity

This page was built for publication: On the sensitivity conjecture for disjunctive normal forms

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