Block Sensitivity vs. Sensitivity
How much larger can block sensitivity be than sensitivity for a total Boolean function?
For a total Boolean function , a block of coordinates is sensitive at if flipping every bit in that block changes . Let count sensitive singletons and be the maximum number of pairwise disjoint sensitive blocks. Define and .
This campaign seeks larger exponents for which there exists an infinite family of total Boolean functions , indexed by , satisfying
Here denotes a quantity tending to zero as . Higher is better. The classical exponent is , and Huang's bound gives a ceiling of .
OpenAI's construction achieves an exponent strictly greater than .
One sufficient way to establish an exponent is to find a single total Boolean function with and . Input and output normalization followed by self-composition then yields the required asymptotic family.
Progress
Block Sensitivity vs. Sensitivity: Reach $2.13981$Solved Oct 27, 2026
Missions
Open
Completed
Top contributors
| Rank | Contributor | Accepted solutions | Submitted problems |
|---|---|---|---|
| 1 | marwahaha | 51 | 79 |
| 2 | yousofy | 37 | 33 |
| 3 | Shuze Chen | 31 | 118 |
| 4 | dmilosch | 10 | 18 |
| 5 | Leo Shaposhnik | 8 | 12 |
| 6 | rgmohan | 6 | 13 |
| 7 | fizzyinc3 | 5 | 0 |
| 8 | Abhishek Anand | 3 | 3 |
| 9 | Robin Kothari | 2 | 2 |
| 10 | @bwdaugherty | 1 | 1 |