{"id":"e7f5e454-f8ac-4a59-a7ca-3a150287feb9","arxiv_id":"2608.00851","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"partial","parameter_count":6,"one_line_summary":"A total Boolean function on 2,017,584 variables has block sensitivity at least λ^{2.127}, with λ the spectral sensitivity, so bs is not O(λ²).","lead":"A new construction shows block sensitivity can outpace the square of spectral sensitivity, refuting a 2021 conjecture in query complexity. The gap is exponent 2.127, and a 30-variable counterexample is also given.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claimed exact multiplicativity of λ under composition is false, so the infinite-family construction and asymptotic refutation are unsupported as written.","rationale":"I examined the probabilistic counting in Section 5 and the LLL inequalities for (k,r)=(14011,144). Lemma 5.4's active-pattern counts check out, the radius-two union bound gives the stated K, and the asymmetric LLL inequalities hold with the certified (x1,x2), albeit with a very small margin. I therefore do not think the reader's weakest assumption, the Section 5 counting, is the most load-bearing point. The formal verification gap in Appendix B is real and supports a conditional verdict, but it is a matter of claimed verification rather than a flaw in the mathematical argument. The more serious problem is the composition step: the paper asserts that λ is exactly multiplicative, a statement that a small explicit counterexample refutes. This step is essential because the abstract and Corollary 6.2 use iterated composition to turn the finite example into an infinite family, and without an infinite family the single function cannot refute the asymptotic big-O conjecture. The theorem as stated also overclaims the exponent 2.127, since the bounds λ ≤ 89.0162 and bs ≥ 14011 imply only an exponent of about 2.12697. Both issues are repairable: submultiplicativity may well be provable, and the exponent can be rounded down. But as written, the paper's central asymptotic claim is not established by the arguments given, so a conditional verdict requiring these corrections is appropriate.","tokens_in":11,"tokens_out":53414,"duration_ms":1030793,"concrete_test":"Construct the 16-vertex sensitivity graph of h = (x1∧x2) XOR (x3∧x4) and diagonalize its adjacency matrix; the largest eigenvalue is 2√2, while λ(PARITY_2)λ(AND_2) = 2√3. Their inequality disproves exact multiplicativity. To determine whether the corollary can be repaired, also test at least three other small pairs, e.g., OR_2∘AND_2, AND_2∘PARITY_2, and PARITY_2∘OR_2, checking whether λ(f∘g) ≤ λ(f)λ(g) in every case; if submultiplicativity holds, the paper should replace the false exact-multiplicativity assertion with a proof of this weaker inequality and then justify that the resulting family still refutes the asymptotic conjecture.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing unsupported step is the composition argument stated just before Eq. (2): \"Both bs(f) and λ(f) are both exactly multiplicative under composition.\" Block sensitivity is multiplicative, but spectral sensitivity is not. For f = PARITY_2 and g = AND_2, λ(f) = 2 and λ(g) = √3, yet the composed function h = (x1∧x2) XOR (x3∧x4) has λ(h) = 2√2 ≈ 2.828, which is strictly less than the product 2√3 ≈ 3.464. Thus the exact multiplicativity claim is false for standard Boolean composition. This matters because Theorem 6.1 alone gives a single finite function; a single finite example does not refute the asymptotic conjecture bs(f) = O(λ(f)^2), since a big-O constant can absorb any fixed finite ratio. The paper's claimed refutation depends on iterated composition to produce an infinite family with λ→∞ and exponent 2.127; that inference is invalid as written. The proof could potentially be repaired if λ is submultiplicative (λ(f∘g) ≤ λ(f)λ(g)), which the example satisfies, but the paper neither states nor proves this weaker property and instead asserts a false equality. Separately, the displayed exponent 2.127 is not implied by the proven bounds: with λ ≤ 89.0162 and bs ≥ 14011, the best guaranteed exponent is about 2.12697, so the theorem's phrase \"implying bs(f) ≥ λ(f)^{2.127}\" is numerically unsupported.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13110,"tokens_out":12291,"duration_ms":106537,"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":[{"comment":"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":"Section 4, paragraph after Lemma 4.1 and Eq. (2)"},{"comment":"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.","section":"Section 7 and Appendix B"},{"comment":"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).","section":"Theorem 6.1 and Section 6"}],"minor_comments":[{"comment":"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.","section":"Abstract and Section 2"},{"comment":"The displayed conclusion contains a typo: \"bs(fn) = Ω( λ(fn))2.127\" should presumably read \"bs(f_n)=Ω(λ(f_n)^{2.127})\".","section":"Corollary 6.2"},{"comment":"There are several typographical errors, including \"senstivity\", \"block sensitivity of b\", \"tourament\", \"whiel\", \"efficient\", and \"satifisability\"; these should be corrected in a revision.","section":"Throughout"},{"comment":"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.","section":"Appendix A"}],"recommendation":"reject","confidential_remarks":"The false statement about multiplicativity of λ is a load-bearing error, and the claimed Lean verification is contradicted by the `sorry` in the appendix. Even if the finite construction is sound, the paper as written does not refute the asymptotic conjecture bs(f)=O(λ(f)^2). I would encourage the authors to pursue a repair if they can prove a submultiplicativity-type bound for their construction and supply a genuine formal proof, but the current manuscript is not publishable in its present form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The construction is the real news here: a union of subcubes indexed by a doubly regular tournament, with gate variables fixed by the Lovász local lemma. The spectral lemma (Lemma 4.1) is clean, and the LLL parameter check for (k,r)=(14011,144) looks numerically sound. The explicit 30-variable witness is a nice concrete artifact.\n\nThe stress-test's composition counterexample does not survive contact. It claims λ(AND_2)=√3; the actual value is √2. The composed function (x1∧x2) XOR (x3∧x4) has λ=2√2, exactly λ(PARITY_2)·λ(AND_2). So the provided example supports exact multiplicativity; it does not refute it. That said, the paper asserts multiplicativity without proof or citation, and that should be fixed in revision.\n\nThe real soft spots are elsewhere. The abstract and Section 7 say the main result has been formally verified in Lean, but Appendix B's central theorem ends in `sorry`. If the repository has a complete proof, ship the certificate; if not, retract the claim. The Lean definition of `lam` also looks like a sum of eigenvalues rather than the largest eigenvalue, which would mean the formal statement is proving the wrong thing. Second, the exponent 2.127 is not actually implied by Theorem 6.1: the bounds λ≤89.0162 and bs≥14011 give a best guaranteed exponent near 2.12697, so the abstract's 2.127 is a small but real overstatement. Third, the 'exact certification' of the LLL inequalities is asserted without shipping a certificate; that is minor if the pen-and-paper check is truly easy.\n\nThis paper is not ready to publish as written, but it deserves a serious referee. The underlying construction is original, the spectral analysis is credible, and the errors are correctable. I would send it to peer review with the expectation of substantial revision, not desk-reject it.","headline":"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.","tokens_in":13696,"tokens_out":18995,"would_cite":false,"duration_ms":161227,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","05C20","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"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).","keywords":["boolean functions","block sensitivity","spectral sensitivity","sensitivity graph","query complexity","doubly regular tournaments","Lovász local lemma","certificate complexity"],"falsifier":"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.","tokens_in":12532,"feed_emoji":"🧩","tokens_out":9883,"duration_ms":85248,"temperature":0.7,"pith_summary":"Block sensitivity counts how many pairwise-disjoint blocks of coordinates can be flipped to change a Boolean function's value; spectral sensitivity is the largest eigenvalue of the function's sensitivity graph and lower-bounds every standard query-complexity measure. The paper answers a question posed when spectral sensitivity was introduced: block sensitivity is not bounded by a quadratic function of spectral sensitivity. It establishes this by constructing a total Boolean function on 2,017,584 variables with block sensitivity at least 14,011 and spectral sensitivity at most 89.0162, so $bs(f) \\ge \\lambda(f)^{2.127}$. The function is the indicator of a union of subcubes indexed by the vertices of a doubly regular tournament, and the Lovász local lemma fixes the freedom in the construction. A 30-variable member of the same family already exceeds exponent 2, and the main theorem is verified in a formal proof assistant.","feed_headline":"Block sensitivity beats spectral sensitivity squared","feed_subtitle":"A 2,017,584-variable function achieves bs ≥ λ^{2.127}, disproving the quadratic conjecture.","key_machinery":"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)$.","core_discovery":"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}$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"introduced spectral sensitivity and posed the quadratic conjecture that this paper refutes","marker":"[1]"},{"why":"defined sensitivity and the critical-complexity notion underlying the sensitivity graph","marker":"[6]"},{"why":"proved the degree bound $deg(f)\\le \\lambda(f)^2$ that made the quadratic conjecture natural","marker":"[8]"},{"why":"supplied $bs(f)\\le 2deg(f)^2$, completing the upper-bound chain the paper breaks","marker":"[13]"},{"why":"supplied the Lovász local lemma used to choose the gate variables","marker":"[7]"},{"why":"provided the asymmetric two-type local lemma form used to combine radius-one and radius-two bad events","marker":"[3]"},{"why":"defined block sensitivity, the measure being compared","marker":"[12]"}],"fun_headline_variants":["Block sensitivity exceeds spectral sensitivity squared","Spectral sensitivity squared fails to bound block sensitivity","Exponent 2.127: block over spectral sensitivity","Disproof: quadratic bound on block sensitivity false"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Block sensitivity exceeds spectral sensitivity squared","Spectral sensitivity squared fails to bound block sensitivity","Exponent 2.127: block over spectral sensitivity","Disproof: quadratic bound on block sensitivity false"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000869,"raw_usage":{"total_tokens":3792,"prompt_tokens":1003,"completion_tokens":2789,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":619,"completion_tokens_details":{"reasoning_tokens":2731}},"tokens_in":619,"tokens_out":2789,"duration_ms":18019,"temperature":1.0,"reasoning_tokens":2731,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:18:41.991594+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem","cited_arxiv_id":"2010.12629","evidence_quote":"introduced spectral sensitivity and posed the quadratic conjecture that this paper refutes"},{"cited_title":"Upper and lower time bounds for parallel random access machines without simultaneous writes,","cited_arxiv_id":null,"evidence_quote":"defined sensitivity and the critical-complexity notion underlying the sensitivity graph"},{"cited_title":"On the degree of Boolean functions as real polynomials,","cited_arxiv_id":null,"evidence_quote":"supplied $bs(f)\\le 2deg(f)^2$, completing the upper-bound chain the paper breaks"},{"cited_title":"Problems and results on 3-chromatic hypergraphs and some related questions,","cited_arxiv_id":null,"evidence_quote":"supplied the Lovász local lemma used to choose the gate variables"},{"cited_title":"Alon and J","cited_arxiv_id":null,"evidence_quote":"provided the asymmetric two-type local lemma form used to combine radius-one and radius-two bad events"},{"cited_title":"CREW PRAMs and decision trees,","cited_arxiv_id":null,"evidence_quote":"defined block sensitivity, the measure being compared"}],"review_version":2}