For a positive integer , a total Boolean function is a map . Its sensitivity is the largest number of individual bit flips that change its value at a common input. At an input , its block sensitivity is the largest number of pairwise disjoint nonempty coordinate sets whose separate flips change its value. The block sensitivity of is . The symbol denotes the all-zero input. The Sensitivity Conjecture asked whether has a polynomial upper bound in uniform in and .
Nisan and Szegedy suggested the quadratic inequality . Rubinstein showed that a polynomial upper bound must have degree at least two. Ambainis and Sun constructed examples with . Huang resolved the Sensitivity Conjecture in 2019. Wellens proved the universal bound .
The preprint proves that, for every integer , there is a nonconstant total Boolean function with . It also proves the existence of a real number and nonconstant total Boolean functions , indexed by positive integers , such that for every and as .
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.
Sensitivity is a Lean library: 16 items, in four groups. Each has a page written by OctoInform, listed below.
No item matches.