OctoInformBeta

A superquadratic separation of sensitivity and block sensitivity

For a positive integer nn, a total Boolean function is a map f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}. Its sensitivity s(f)s(f) is the largest number of individual bit flips that change its value at a common input. At an input xx, its block sensitivity bs⁡(f,x)\operatorname{bs}(f,x) is the largest number of pairwise disjoint nonempty coordinate sets whose separate flips change its value. The block sensitivity of ff is bs⁡(f)=max⁡xbs⁡(f,x)\operatorname{bs}(f)=\max_x\operatorname{bs}(f,x). The symbol 00 denotes the all-zero input. The Sensitivity Conjecture asked whether bs⁡(f)\operatorname{bs}(f) has a polynomial upper bound in s(f)s(f) uniform in nn and ff.

Nisan and Szegedy suggested the quadratic inequality bs⁡(f)≤s(f)2\operatorname{bs}(f)\le s(f)^2. Rubinstein showed that a polynomial upper bound must have degree at least two. Ambainis and Sun constructed examples with bs⁡(f)=23s(f)2−13s(f)\operatorname{bs}(f)=\frac23s(f)^2-\frac13s(f). Huang resolved the Sensitivity Conjecture in 2019. Wellens proved the universal bound bs⁡(f)≤2/3s(f)4+1\operatorname{bs}(f)\le\sqrt{2/3}\,s(f)^4+1.

The preprint proves that, for every integer d≥1d\ge1, there is a nonconstant total Boolean function ff with bs⁡(f)/s(f)2≥2d/(4(d+2)2)\operatorname{bs}(f)/s(f)^2\ge 2^d/(4(d+2)^2). It also proves the existence of a real number α>2\alpha>2 and nonconstant total Boolean functions FmF_m, indexed by positive integers mm, such that bs⁡(Fm,0)≥s(Fm)α\operatorname{bs}(F_m,0)\ge s(F_m)^\alpha for every mm and bs⁡(Fm,0)→∞\operatorname{bs}(F_m,0)\to\infty as m→∞m\to\infty.

Lean has checked every result of the Lean library, so the Lean library is the reference for the statements on these pages. Each result is stated as the Lean library states it and linked to the corresponding Lean declaration. Where the preprint gives a different statement, it is given beside the Lean library’s statement. The preprint serves only as a guide to the order and names of the results.

The Lean library: Sensitivity

Sensitivity is a Lean library: 16 items, in four groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. §1 (setting): literal flips, sensitivity, and block sensitivity Sensitivity from coordinate and block flips.
  2. Theorem 1.1 [Superquadratic separation] Block sensitivity outgrows squared sensitivity.
§2. The labelled tournament and nested predicates 8 items
  1. §2 (setting): parameters, regular tournament, and admissible labels Cyclic tournaments supply regular row orientations.
  2. Lemma 2.1 [Existence of the edge labeling] Labellings exclude a sixteen-vertex configuration.
  3. §2 (proof of Lemma 2.1): uniform labels and the union bound A probability bound for forbidden labellings.
  4. §2.1 (setting): the initial Hamming-ball family Hamming balls form a nested initial family.
  5. §2.2 (setting): recursive clauses and nested predicates Recursive clauses preserve nested predicate families.
  6. §2.3 (setting): ordinary and joint profiles Sensitivity profiles track single-coordinate flips.
  7. Lemma 2.2 [Initial sensitivity profiles] The initial family has bounded side sensitivities.
  8. Lemma 2.3 [Common disjoint blocks at zero] Predicate towers preserve common accepting blocks.
§3. Sensitivity recurrences 1 item
  1. Proposition 3.1 [Four coupled sensitivity recurrences] Four recurrences bound recursive sensitivity.
§4. Quantitative bounds and separation 5 items
  1. Lemma 4.1 [Quantitative sensitivity profiles] Sensitivity bounds through a fixed tower.
  2. §4 (proof of Theorem 1.1): the final OR, dimension, and quantitative bounds Final disjunction (OR) witnesses give a superquadratic separation.
  3. §4.1 (setting): disjoint composition Boolean composition on separate input blocks.
  4. Lemma 4.2 [Sensitivity and zero-input blocks under composition] Sensitivity is submultiplicative under block composition.
  5. Corollary 4.3 [A fixed exponent greater than two] A fixed exponent above two.

No item matches.