REVIEW 3 major objections 4 minor 14 references
Block Sensitivity can exceed Spectral Sensitivity Squared
T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read The paper constructs a total Boolean function whose block sensitivity exceeds the square of its spectral sensitivity, refuting the conjecture that bs(f) = O(λ(f)^2).
desk verdict A novel LLL-based construction with a plausible core, but the formal-verification claim is undermined by a sorry, the 2.127 exponent is a rounding artifact, and the stress-test's multiplicativity counterexample is arithmetically wrong. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the certificate-union function $f = \mathbf{1}_{\bigcup_i C_i}$, where each certificate $C_i$ is a subcube of codimension $c$; a doubly regular tournament (a tournament in which every vertex has outdegree $(k-1)/2$ and every pair has $(k-3)/4$ common outneighbours) assigns, for each oriented pair $i \to j$, one variable in block $j$ that $C_i$ fixes to 0. The spectral lemma $\lambda(f)^2 \le c + 2\sqrt{(c-1)AB}$ reduces spectral sensitivity to two local counts, $A$ (other certificates at distance 1) and $B$ (other certificates within distance 2). A counting argument classifies the local patterns that would force $A>3$ or $B>7$, and the asymmetric Lovász local lemma shows gate variables can be chosen so these patterns never occur, leaving $k$ and $r$ free until the final choice $(k,r) = (14011,144)$.
What would settle it
Check the counting identities on a small doubly regular tournament: for example, enumerate all active radius-one and radius-two patterns on a $k=15$ or $k=19$ tournament and compare with $N=5(k-3)(k-7)^2/64$ and the constant $K$ in Equation (5). If either identity fails, the local-lemma inequalities at $(k,r)=(14011,144)$ no longer follow; equivalently, a direct check of the two inequalities with $x_1=(9/5)p_1$ and $x_2=(83/10)p_2$ would settle the existence step.
Extended reading notes
Core claim
The central claim is that the exponent $\log bs(f)/\log \lambda(f)$ can exceed 2 for a total Boolean function, so the bound $bs(f) = O(\lambda(f)^2)$ fails. The proof constructs, for $k = 14011$ blocks of $r = 144$ variables each, a function whose 1-set is a union of $k$ subcubes; a doubly regular tournament dictates one conflicting literal between every pair of subcubes, turning their near-neighbor structure into a low spectral radius. A spectral lemma bounds $\lambda(f)^2 \le c + 2\sqrt{(c-1)AB}$, where $c$ is the certificate codimension and $A,B$ are local counts of nearby certificates, and the Lovász local lemma shows gate variables can be chosen with $A \le 3$ and $B \le 7$. The resulting concrete numbers give $\lambda(f) \le 89.0162$ and $bs(f) \ge 14011$, hence $bs(f) \ge \lambda(f)^{2.127}$.
Load-bearing premise
The existence proof depends on exact counts of local patterns in a doubly regular tournament (Lemma 5.4, Equation (5), and Equations (6)-(7)); if any of these counts is wrong, the Lovász local lemma may not deliver a gate assignment satisfying the locality conditions, and the stated spectral bound would not follow.
Editorial extensions
If this is right
- No quadratic bound $bs(f)=O(\lambda(f)^2)$ holds for total Boolean functions; the constructed family gives $bs(f)=\Omega(\lambda(f)^{2.127})$ with $\lambda(f)\to\infty$.
- Composition amplifies any exponent above 2, so the counterexample persists at all scales rather than being a finite-size accident.
- The 30-variable member of the family gives a concrete, exactly computed case with exponent above 2, usable as a test object for further exploration.
- Because spectral sensitivity lower-bounds every standard query-complexity measure, block sensitivity can outrun this lower bound by more than a square.
- Numerical evidence reported in the paper suggests the specific construction cannot exceed exponent 2.21, marking the limit of this particular template.
Reading between the lines
- A natural next step is to run the same local-lemma scheme on other doubly regular tournaments or other gate assignments; the paper's empirical search found a cyclotomic assignment best for $(k,r)=(251,5)$, so similar rules might push the proved exponent closer to the observed 2.20 barrier.
- The spectral lemma's bound is probably not tight: empirically $\lambda^2$ sits near $c+2\sqrt{(c-1)A}$ rather than $c+2\sqrt{(c-1)AB}$. If that missing factor could be proved away, the same construction would automatically reach a higher exponent.
- The certificate-union template may transfer to other spectral or algebraic complexity measures: any measure expressible as a spectral radius plus local counting is a candidate for a similar block-sensitivity separation.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper constructs a total Boolean function as the indicator of a union of k subcubes on kr variables, where each subcube is indexed by a block of r variables and the conflicting literals between blocks are assigned using a doubly regular tournament and randomized gate variables fixed by the Lovász local lemma. The authors prove a spectral lemma bounding the spectral sensitivity λ(f) in terms of local counts A and B, verify the local-lemma hypotheses for (k,r)=(14011,144), and claim bs(f) ≥ 14011 with λ(f) ≤ 89.0162, hence bs(f) ≥ λ(f)^{2.127}. They further claim that by iterated composition this yields a family with bs(f_n)=Ω(λ(f_n)^{2.127}), refuting the conjecture bs(f)=O(λ(f)^2). The paper also reports numerical evidence for a better exponent on 1255 variables and a 30-variable witness, and it states that the main theorem has been formally verified in Lean.
Significance. If the main theorem and its composition corollary were correct, the paper would resolve the open question of Aaronson, Ben-David, Kothari, Rao and Tal in the negative, which would be a substantial contribution to Boolean function complexity. The spectral lemma in Section 4 is clean and appears sound, and the Lovász local lemma parameter computation for (k,r)=(14011,144) is a concrete, checkable calculation. The paper also provides a concrete 30-variable function whose exponent can be verified exactly, which is a nice computational artifact. However, the two central claims needed for the asymptotic refutation are not supported: the asserted exact multiplicativity of λ under composition is false, and the advertised Lean formalization is not present in the appendix because the displayed theorem contains `sorry`. In addition, the numerical exponent 2.127 in Theorem 6.1 is not implied by the stated bounds. As a result, the paper does not establish that bs(f)=O(λ(f)^2) is false.
major comments (3)
- [Section 4, paragraph after Lemma 4.1 and Eq. (2)] The assertion that "Both bs(f) and λ(f) are both exactly multiplicative under composition" is false for λ. For standard Boolean composition, take f=g=AND_2; then λ(f)=λ(g)=1, but the composed function AND_4 on four variables has λ=2, since its sensitivity graph is the disjoint union of two stars K_{1,4}. Therefore the equality λ(f^{∘t})=λ(f)^t used in the paragraph before Eq. (2) is not valid. Consequently Corollary 6.2, which relies on iterated composition to turn the finite example into an infinite family with λ→∞, does not follow. A single finite function with bs(f)>λ(f)^2 does not refute the asymptotic statement bs(f)=O(λ(f)^2), because any constant can absorb a fixed finite ratio. To repair the argument, the paper would need to prove a suitable upper bound such as λ(f∘g) ≤ λ(f)λ(g) for the constructed family, but no such statement is proved or even stated.
- [Section 7 and Appendix B] The formal verification claim is not supported by the included artifact. The abstract and Section 7 state that the main result has been formally verified in Lean, and Appendix B is described as reproducing the Comparator certificate. However, the theorem `exists_bs_gt_lam_rpow` in Appendix B ends with `sorry`; a theorem containing `sorry` is not a proof. Thus the paper's assertion of machine-checked verification is inaccurate. A complete Lean proof or an actual Comparator certificate must be provided, or the formal-verification claim must be withdrawn.
- [Theorem 6.1 and Section 6] The claimed implication "implying that bs(f) ≥ λ(f)^{2.127}" is not justified by the displayed numerical bounds. The paper itself reports an exponent of 2.126973 immediately before the theorem, and with bs(f)≥14011 and λ(f)≤89.0162 the best exponent guaranteed by these quantities is approximately 2.12695, since 89.0162^{2.127}≈14020>14011. Thus rounding the exponent up to 2.127 gives a statement that is numerically false as an implication from the stated bounds. The theorem should either state a valid exponent such as 2.1269 or prove a tighter bound on λ(f).
minor comments (4)
- [Abstract and Section 2] The abstract says "total Boolean function on 2017584 inputs", but 2017584 is the number of variables; the wording should say "variables" for consistency with the rest of the paper.
- [Corollary 6.2] The displayed conclusion contains a typo: "bs(fn) = Ω( λ(fn))2.127" should presumably read "bs(f_n)=Ω(λ(f_n)^{2.127})".
- [Throughout] There are several typographical errors, including "senstivity", "block sensitivity of b", "tourament", "whiel", "efficient", and "satifisability"; these should be corrected in a revision.
- [Appendix A] The tournament table uses dots without an explicit explanation of what a dot represents; a sentence clarifying that dots denote the opposite orientation (or a non-edge of the gate selection) would improve readability.
Circularity Check
No circularity found: the spectral bound is derived from local counts and a Lovász local lemma argument, not from the target separation.
full rationale
The paper's central derivation is self-contained in the relevant sense. The function f is defined as a union of certificate subcubes indexed by a doubly regular tournament, and the block sensitivity lower bound bs(f) ≥ k follows directly from the construction (Lemma 3.1). The spectral sensitivity upper bound is obtained from Lemma 4.1, which bounds λ(f)^2 in terms of the codimension c and the local counts A and B; those counts are then controlled by a probabilistic argument (Section 5) culminating in the Lovász local lemma. The parameters (k, r) are chosen by explicit optimization, and the claimed numerical bound λ(f) ≤ 89.0162 is computed from the inequality, not fitted to any spectral data. The only self-citation is to the author's prior work on Aristotle for the Lean formalization, and that is used for proof verification, not as a load-bearing mathematical premise. The skeptical concerns raised about the paper — that spectral sensitivity is not exactly multiplicative under composition, and that the displayed exponent 2.127 slightly exceeds the value 2.126973 implied by the stated bounds — are genuine correctness criticisms, but they are not circularity: they do not show that any stated conclusion is assumed as an input, only that some inference steps may be invalid or imprecise. Under the hard rule that circularity requires a exhibited reduction of a claim to its own input, no such step exists here. Score 0.
Assumptions & free parameters
free parameters (6)
- k (number of blocks/certificates) =
14011
- r (block size) =
144
- A (max other certificates at distance 1) =
3
- B (max other certificates at distance at most 2) =
7
- x1 (LLL witness, radius one) =
1.8 * r^{-6}
- x2 (LLL witness, radius two) =
8.3 * K * r^{-20}
assumptions (6)
- standard math Lovász local lemma (asymmetric version)
- standard math Existence of a doubly regular tournament on k vertices for k ≡ 3 mod 4 (e.g., Paley tournament)
- standard math Geometric mean norm inequality ||R||₂ ≤ sqrt(||R||₁ ||R||∞)
- ad hoc to paper Correctness of the event counting in Lemma 5.4 and Equation 5
- domain assumption Multiplicativity of bs(f) and λ(f) under composition
- domain assumption Gate functions satisfy g_i(0)=1
Cite this review
Pith. "Pith review of Block Sensitivity can exceed Spectral Sensitivity Squared." pith.science (2026). https://pith.science/paper/OB7PAM7R
@misc{pith2026260800851,
author = {Pith},
title = {Pith review of: Block Sensitivity can exceed Spectral Sensitivity Squared},
year = {2026},
howpublished = {\url{https://pith.science/paper/OB7PAM7R}},
note = {Machine review of arXiv:2608.00851}
}
abstract
The spectral sensitivity $\lambda(f)$ of a Boolean function is the largest eigenvalue of the adjacency matrix of its sensitivity graph. It lower-bounds every standard measure of query complexity, and Aaronson, Ben-David, Kothari, Rao and Tal, who introduced it, asked whether block sensitivity is at most quadratic in it: is $bs(f)=O(\lambda(f)^{2})$? We show that it is not. We construct a total Boolean function on $2017584$ variables with $bs(f)\ge 14011$ and $\lambda(f)\le 89.0162$, so that $bs(f)\ge\lambda(f)^{2.127}$, and hence by composition a family with $\lambda(f_n)\to\infty$ and $bs(f_n)=\Omega(\lambda(f_n)^{2.127})$. The function is the indicator of a union of $k$ subcubes indexed by the vertices of a doubly regular tournament, and the freedom left in the construction is fixed by the Lov\'asz local lemma. The main result has been formally verified in Lean. We also give numerical evidence that a member of the same family on $1255$ variables reaches an exponent near $2.20$, and exhibit a member on $30$ variables whose exponent already exceeds $2$ and whose spectral sensitivity can be computed exactly.
Reference graph
Works this paper leans on
-
[1]
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
S. Aaronson, S. Ben-David, R. Kothari, S. Rao, and A. Tal, “Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem,” in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021) , ACM, 2021, pp. 1330–1342. arXiv:2010.12629
work page Pith review arXiv 2021
-
[2]
Aristotle: IMO-level automated theorem proving,
T. Achim, A. Best, A. Bietti, K. Der, M. Fédérico, S. Gukov, D. Halpern-Leistner, K. Henningsgard, Y. Kudryashov, A. Meiburg, M. Michelsen, R. Patterson, E. Ro- driguez, L. Scharff, V. Shanker, V. Sicca, H. Sowrirajan, A. Swope, M. Tamas, V. Tenev, J. Thomm, H. Williams, and L. Wu, “Aristotle: IMO-level automated theorem proving,”
-
[3]
N. Alon and J. H. Spencer, The Probabilistic Method , 4th ed. Wiley, Hoboken, NJ, 2016
work page 2016
-
[4]
New separation between $s(f)$ and $bs(f)$
A. Ambainis and X. Sun, “New separation between s(f ) and bs(f ),” Electronic Collo- quium on Computational Complexity, Report TR11-116, 2011. arXiv:1108.3494
work page Pith review arXiv 2011
-
[5]
Complexity measures and decision tree complexity: a survey,
H. Buhrman and R. de Wolf, “Complexity measures and decision tree complexity: a survey,” Theoretical Computer Science , vol. 288, no. 1, pp. 21–43, 2002
work page 2002
-
[6]
Upper and lower time bounds for parallel random access machines without simultaneous writes,
S. A. Cook, C. Dwork, and R. Reischuk, “Upper and lower time bounds for parallel random access machines without simultaneous writes,” SIAM Journal on Computing , vol. 15, no. 1, pp. 87–97, 1986
work page 1986
-
[7]
Problems and results on 3-chromatic hypergraphs and some related questions,
P. Erdős and L. Lovász, “Problems and results on 3-chromatic hypergraphs and some related questions,” in Infinite and Finite Sets (Colloq., Keszthely, 1973) , vol. II, Col- loquia Mathematica Societatis János Bolyai, vol. 10, North-Holland, Amsterdam, 1975, pp. 609–627
work page 1973
-
[8]
Induced subgraphs of hypercubes and a proof of the sensitivity conjecture,
H. Huang, “Induced subgraphs of hypercubes and a proof of the sensitivity conjecture,” Annals of Mathematics , vol. 190, no. 3, pp. 949–955, 2019. arXiv:1907.00847
arXiv 2019
Show all 14 references
-
[9]
https://github
Lean FRO, Comparator: a trustworthy judge for Lean proofs . https://github. com/leanprover/comparator
-
[10]
The Lean 4 theorem prover and programming language,
L. de Moura and S. Ullrich, “The Lean 4 theorem prover and programming language,” in Automated Deduction – CADE 28 , Lecture Notes in Computer Science, vol. 12699, Springer, Cham, 2021, pp. 625–635
2021
-
[11]
The Lean mathematical library,
The mathlib Community, “The Lean mathematical library,” in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), ACM, 2020, pp. 367–381
2020
-
[12]
CREW PRAMs and decision trees,
N. Nisan, “CREW PRAMs and decision trees,” SIAM Journal on Computing , vol. 20, no. 6, pp. 999–1007, 1991. 13
1991
-
[13]
On the degree of Boolean functions as real polynomials,
N. Nisan and M. Szegedy, “On the degree of Boolean functions as real polynomials,” Computational Complexity , vol. 4, no. 4, pp. 301–313, 1994
1994
-
[14]
Sensitivity vs. block sensitivity of Boolean functions,
D. Rubinstein, “Sensitivity vs. block sensitivity of Boolean functions,” Combinatorica, vol. 15, no. 2, pp. 297–299, 1995. Note on AI Usage Several key ideas of the proof, in particular that ”gated tournaments” would be a good candidate for large bs relative to λ, were suggest...
1995
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.