Boolean Functions with Minimal Spectral Sensitivity

Jevg\=enijs Vihrovs; Kri\v{s}j\=anis Pr\=usis

Boolean Functions with Minimal Spectral Sensitivity

T0 review · 0 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that the minimum spectral sensitivity of a total Boolean function is Θ(√log n), and constructs functions achieving this bound up to a 1+o(1) factor, together with an optimal tradeoff between zero- and one-sensitivity.

desk verdict Clean construction settles minimal spectral sensitivity for total Boolean functions; the tradeoff theorem is sharp and the proofs survive scrutiny despite a terse component analysis. read the letter →

arxiv 2412.16088 v2 pith:IBL6B2GL submitted 2024-12-20 cs.CC

Krišjānis Prūsis , Jevgēnijs Vihrovs This is my paper · ORCID

classification cs.CC MSC 68Q1505C50

keywords spectralsensitivityBooleanfunctionsHammingcodeaddressfunctioncertificatecomplexitytradeofftotal

topics P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper determines the asymptotic minimum of a Boolean-function measure called spectral sensitivity, which measures the largest eigenvalue of the graph that connects inputs at which the function flips value. The authors construct total Boolean functions on n variables whose spectral sensitivity is Θ(√log n), matching the known lower bound √((1+o(1)) log n) up to a factor of 1+o(1). The main construction, the Hamming address function, combines Hamming error-correcting codes with the classical address function; its 1-certificates are separated by the code's minimum distance, forcing zero-sensitivity 1 and one-sensitivity O(log n). The paper also proves an optimal tradeoff: for every c∈[0,1], there is a function with zero-sensitivity (c+o(1)) log n and one-sensitivity (1−c+o(1)) log n while maintaining minimal spectral sensitivity. As a consequence, it yields a new example of a function whose ordinary sensitivity is (1/2+o(1)) log n, the smallest possible up to a constant factor.

What carries the argument

The central object is the Hamming address function HAF_r, built from the binary Hamming code H_r with codeword length k=2^r−1 and message length 2^r−r−1. For each message m, the function has a 1-certificate p_m that fixes the first k bits to the codeword w_m and sets the m-th of the remaining $2^{{2^r−r−1}}$ data bits to 1. Because any two codewords differ in at least three positions, the certificates are pairwise far apart, so each 0-input is adjacent to at most one certificate, forcing s0=1; meanwhile the certificate complexity bound gives s1 ≤ 2^r. The spectral sensitivity then follows from the sandwich inequality √(s1) ≤ λ ≤ √(s0 s1). For the tradeoff family, the construction uses a conjunction of several such functions and a modified composition with a negated copy; the sensitivity graph of the composition is analyzed via its connected components, which the paper shows are only stars centered at 1-inputs and two-layer stars centered at a 0-input, the latter giving the eigenvalue √(s0+s1−1).

What would settle it

For a small concrete instance (for example r1=r2=2 or r1=r2=3), enumerate all edges of the sensitivity graph of f'=CHAF ∘' ¬CHAF, write down its adjacency matrix, and compute its largest eigenvalue; if it exceeds √(s0+s1−1), Theorem 9 is false. Alternatively, search for a pair of two-layer stars connected by an edge, which would invalidate the component analysis.

Watch

Extended reading notes

Core claim

The paper's central claim is that the lower bound λ(f) ≥ √((1+o(1)) log n) for the spectral sensitivity of any non-degenerate total Boolean function is tight up to a factor of 1+o(1). This is shown by the Hamming address function HAF_r, which encodes each message of a Hamming code into a 1-certificate consisting of the codeword followed by a single 1 in a dedicated data position; because codewords differ in at least three positions, no 0-input can be adjacent to two certificates, so s0(HAF_r)=1 and s1(HAF_r) ≤ 2^r, giving λ(HAF_r)=√s1=√((1+o(1)) log n). The paper further proves that the generalized Simon inequality s0(f)+s1(f) ≥ log n − log log n + 2 is the optimal tradeoff for low-sensitivity functions, and constructs, for every c∈[0,1], a total non-degenerate function f with s0(f)=(c+o(1)) log n, s1(f)=(1−c+o(1)) log n, and λ(f)=√((1+o(1)) log n). The tradeoff construction composes a conjunction of Hamming address functions with a negated copy and analyzes the sensitivity graph's connected components, which are claimed to be stars and two-layer stars with spectral norm √(s0+s1−1).

Load-bearing premise

The proof of the tradeoff construction assumes that the sensitivity graph of the composed function CHAF ∘' ¬CHAF has exactly two types of connected components, stars and two-layer stars; if any additional edges existed, the spectral norm could exceed √(s0+s1−1) and the claimed λ(f)=√((1+o(1)) log n) could fail.

Editorial extensions

If this is right

For every total non-degenerate Boolean function, λ(f) ≥ √((1+o(1)) log n), and the Hamming address function attains this bound up to a 1+o(1) factor, so the asymptotic minimum of spectral sensitivity is now known exactly.
The tradeoff construction matches the generalized Simon inequality s0(f)+s1(f) ≥ log n − log log n + 2 for every c∈[0,1], showing that the entire low-sensitivity tradeoff curve is achievable at minimal spectral sensitivity.
Taking c=1/2 gives a total Boolean function with s0(f)=s1(f)=(1/2+o(1)) log n, a new example of minimal possible sensitivity up to a constant factor, previously known only for the monotone address function.
Because s(f) ≤ λ(f)^2 and deg(f) ≤ λ(f)^2 (with query complexity polynomial in degree), these functions simultaneously have near-minimal sensitivity, degree, and deterministic query complexity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The certificate-separation mechanism behind HAF_r—using a code's minimum distance to isolate 1-certificates—may generalize to other complexity measures, such as constructing functions with prescribed unambiguous certificate complexity or near-minimal approximate degree.
The component analysis of the composed sensitivity graph in the proof of Theorem 9 is asserted in a short paragraph; a computer-assisted enumeration of the sensitivity graph for small parameters (e.g., r1=r2=2) could confirm that only the two claimed component types occur.
The generalized Simon inequality may be improvable in the additive constant; equality up to o(1) is shown, but exact minimizers for finite n remain open.
The conjunction trick for approximating arbitrary c suggests that a single Hamming-address construction with a more flexible code might yield the entire sensitivity tradeoff without composing multiple copies.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper closes the question of minimal spectral sensitivity for total Boolean functions. The main construction, the Hamming address function, achieves lambda(f) = sqrt((1+o(1)) log n), matching the lower bound that follows from Nisan-Szegedy plus deg <= lambda^2. That is a genuinely clean result. The tradeoff theorem (Theorem 9) that lets you dial s0 and s1 to any split of the optimal log n budget is also new, and the generalization of Simon's lower bound to s0+s1 is a useful observation. The desensitization comparison in Section 4 is honest and gives a worse constant, which is good context.

The proofs are mostly sound. I checked the one spot that looked terse: Theorem 9's classification of connected components of the sensitivity graph. The text says there are only two component types and leaves it at that. That is short for the amount of case analysis involved, but the claim is correct. Since CHAF has s0=1, any 0-input of the inner CHAF has at most one sensitive neighbor; flipping it gives the two-layer star, and if there is no such neighbor you get an ordinary star. Hamming distance between certificates prevents any extra edges between components. So the spectral norm calculation sqrt(s0+s1-1) holds. I'd like the published version to expand this paragraph, but it is not a correctness issue.

Minor issues: the abstract has a typo; the tradeoff statement writes s0 twice where the second should be s1. Also, the parameter selection for arbitrary c in Theorem 9 is informal, though the idea is clear: by taking enough Hamming codes and shifting all exponents, you can approximate any ratio.

Overall this is a solid paper for the Boolean function complexity audience. It settles a natural open question with a simple construction, and the proof checks out. It deserves a serious referee. I'd recommend accept, with a request to fix the typo and say a bit more about the component analysis.

Referee Report

0 major / 6 minor

Summary. The paper studies the minimum possible spectral sensitivity λ(f) of total non-degenerate Boolean functions. Its main construction is the Hamming address function HAF_r, which satisfies s0(HAF_r)=1, s1(HAF_r)=2^r, n=2^{Θ(2^r)}, and λ(HAF_r)=√((1+o(1)) log n), matching the lower bound λ(f)≥√((1-o(1)) log n) that follows from the Nisan–Szegedy degree bound and the inequality deg(f)≤λ(f)^2. The paper also analyzes a desensitization method of Ben-David–Hatami–Tal and derives λ=√((3+o(1)) log n) for several known low-sensitivity functions. The second main contribution is a generalized Simon lower bound s0(f)+s1(f)≥log n−log log n+2 together with a composition construction CHAF_a ∘' ¬CHAF_b that achieves s0=(c+o(1)) log n and s1=(1−c+o(1)) log n for any c∈[0,1], while keeping λ(f)=√((1+o(1)) log n). The proof of the latter theorem analyzes the sensitivity graph and shows that its nontrivial connected components are stars and two-layer stars.

Significance. The paper resolves, up to a 1+o(1) factor, the question of the minimal spectral sensitivity of total Boolean functions, complementing the previously known lower bound with an explicit matching construction. The tradeoff theorem is optimal against the generalized Simon bound and yields a new example of a function with minimal total sensitivity up to a constant factor. The constructions are explicit and elementary, and the central claims are correct on inspection; the proof of the component analysis in Theorem 9 is terse but the missing edge enumeration is straightforward to supply. This is a solid contribution to Boolean function complexity.

minor comments (6)

[Abstract and Section 1] In the abstract (and in the corresponding sentence in Section 1), the second displayed quantity in the tradeoff statement is written as s0(f)=(1−c+o(1)) log n; it should be s1(f)=(1−c+o(1)) log n.
[Section 4, after Lemma 5] The sentence 'By the fact that s0(f′)=1 and by Lemma 2, we have λ(f′)=√s1(f′)' should refer to Lemma 3 together with the elementary inequality √s(f)≤λ(f), not Lemma 2. In the same paragraph, 's1(f′)=UC1(f)=3UC1(f)' should read 's1(f′)=3UC1(f)', and '√3 UC1(f)' should be written as √(3 UC1(f)) to avoid ambiguity.
[Section 4, Proposition 6] The proof establishes only the lower bound UC1(MAF_k)≥deg(MAF_k)≥k=(1+o(1)) log n. To conclude λ(MAF′_k)=√((3+o(1)) log n), one also needs the matching upper bound UC1(MAF_k)≤(1+o(1)) log n. This follows, for example, from the unambiguous collection of certificates that fix all k address bits and, for addresses of weight ⌊k/2⌋, fix the selected data bit to 1; the step should be stated explicitly.
[Section 5, Theorem 9] The classification of the connected components of the sensitivity graph is asserted in a short paragraph rather than proved. Please add a formal enumeration of all possible sensitive edges: outer codeword flips, the unique inner flip in the addressed block, inner flips in non-addressed blocks, and the edges incident to the central 0-input; also explicitly rule out edges among first-layer vertices and between codeword-flip leaves. In the eigenvector argument, the averaging over child permutations should be restricted to the largest eigenvalue (or justified by Perron–Frobenius), since averaging can annihilate eigenvectors for other eigenvalues.
[Section 4] The quantity D(f) is used in the sentence 's1(f′) ≤ 3 D(f)' but is never defined. It should be defined (deterministic decision tree depth) or replaced by the unambiguous certificate complexity bounds that are actually used.
[Section 5, Theorem 7] In the proof, the case split 'If s(f)>log n, then ... we are done' is only valid when log log n ≥ 2; for finitely many small n the target lower bound is not implied by the argument as written. Either state the theorem for sufficiently large n or handle the small cases separately. The symmetric derivation of the degree bound for G1 is also omitted and should be included for completeness.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the constructions are benchmarked against external lower bounds and no prediction reduces to an input.

full rationale

The paper's derivation chain is self-contained. HAF_r is constructed explicitly from Hamming codes and the Boolean address function, and its s0=1 and s1≤2^r are proved from the code's minimum distance, not assumed. The bound λ(f)=√(s1(f)) follows from two external, cited inequalities (s(f)≤λ(f) as max degree ≤ spectral radius, and λ(f)≤√(s0(f)s1(f)) from Aaronson et al.), neither of which is supplied by the present authors. The lower bound λ(f)≥√((1+o(1))log n) is imported from Nisan–Szegedy and Aaronson et al. and is external to the construction. The tradeoff Theorem 9 is a composition of the same function; its spectral-norm computation is an explicit eigenvalue calculation for the claimed two component types of the sensitivity graph. A reader might wish for a more formal enumeration of the components in Theorem 9, but that is a potential proof gap or correctness concern, not a circularity: no quantity is fitted to data, no result is renamed, and no load-bearing step is justified solely by the authors' own prior work. No self-citations occur in the argument. Hence circularity score 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claims rest on standard complexity-theoretic lemmas (degree lower bounds, spectral sensitivity relations, certificate complexity inequalities) and on the standard existence of Hamming codes. No free parameters are fitted to data. No new entities are postulated.

assumptions (6)

standard math There exist Hamming codes H_r of length 2^r-1 with minimum distance 3 and message length 2^r-r-1.
Used in Theorem 4 to guarantee that any two 1-certificates differ in at least 3 positions, giving s0=1.
standard math deg(f) ≤ λ(f)^2 for every Boolean function f.
Aaronson et al. 2021, Theorem 1. Used with Nisan-Szegedy to lower bound spectral sensitivity.
standard math λ(f) ≤ √(s0(f) s1(f)) for every Boolean function f.
Aaronson et al. 2021, Lemma 31. Used to upper bound spectral sensitivity of HAF_r.
standard math For any non-empty subgraph G of the Boolean hypercube, |V(G)| ≥ 2^{δ(G)} where δ(G) is the minimum degree.
Simon 1983, Lemma 1. Used in the proof of Theorem 7.
standard math The indicator of any Boolean function f can be represented exactly as the sum of indicators of subcubes in an unambiguous certificate collection, hence UC_b(f) ≥ deg(f).
Implicit in BHT17 Section 2.7.2 as cited; used in Proposition 6.
standard math A threshold function on k variables has degree exactly k.
Buhrman and de Wolf 2002, Proposition 5. Used to lower bound deg(MAF_k) ≥ k.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Boolean Functions with Minimal Spectral Sensitivity." pith.science (2026). https://pith.science/paper/IBL6B2GL

@misc{pith2026241216088,
  author       = {Pith},
  title        = {Pith review of: Boolean Functions with Minimal Spectral Sensitivity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IBL6B2GL}},
  note         = {Machine review of arXiv:2412.16088}
}

abstract

We show examples of total Boolean functions that depend on $n$ variables and have spectral sensitivity $\Theta(\sqrt{\log n})$, which is asymptotically minimal. Our main new function combines the Hamming code with the Boolean address function and has $\lambda(f) = \sqrt{(1+o(1)) \log_2 n}$, which is optimal even up to a constant factor. By combining this function with itself in a specific way, we also obtain a family of functions with $\text{s}_0(f) = (c+o(1)) \log_2 n$ and $\text{s}_0(f) = (1-c+o(1)) \log_2 n$ for any $c \in [0,1]$. This is an optimal tradeoff for Boolean functions with low sensitivity, as the lower bound on sensitivity by Simon generalizes to \[\text{s}_0(f)+\text{s}_1(f)\geq\log_2 n - \log_2 \log_2 n + 2.\] As a corollary, this gives a new example of a function with minimal possible sensitivity (up to a constant factor), $\text{s}(f) = (\frac{1}{2}+o(1)) \log_2 n$.

Figures

Figures reproduced from arXiv: 2412.16088 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

2 extracted references · 1 canonical work pages

[67]

Low-Sensitivity Functions from Unambiguous Certificates

Leibniz International Pro- ceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zen trum f¨ ur In- formatik, 2017, 28:1–28:23. isbn: 978-3-95977-029-3. doi: 10.4230/LIPIcs.I TCS.2017.28. arXiv: 1605.07084 [quant-ph] . [CHS20] John Chiarelli, Pooya Hatami, and Michael Saks. “An Asympto tically Tight Bound on the Number of Relevant Variables in a Bo...

work page Pith review arXiv 2020
[2021]

How Low can Approximate D egree and Quantum Query Complexity be for Total Boolean Functions?

New York, NY, USA: Associ- ation for Computing Machinery, 2021, pp. 1330–1342. isbn: 9781450380539. doi: 10.1145/3406325.3451047. arXiv: 2010.12629 [quant-ph] . [A W14] Andris Ambainis and Ronald de Wolf. “How Low can Approximate D egree and Quantum Query Complexity be for Total Boolean Functions?” In : Com- putational Complexity 23 (2 2014), pp. 305–322....

arXiv 2002

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [67]

Low-Sensitivity Functions from Unambiguous Certificates

Leibniz International Pro- ceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zen trum f¨ ur In- formatik, 2017, 28:1–28:23. isbn: 978-3-95977-029-3. doi: 10.4230/LIPIcs.I TCS.2017.28. arXiv: 1605.07084 [quant-ph] . [CHS20] John Chiarelli, Pooya Hatami, and Michael Saks. “An Asympto tically Tight Bound on the Number of Relevant Variables in a Bo...

work page Pith review arXiv 2020

[2] [2021]

How Low can Approximate D egree and Quantum Query Complexity be for Total Boolean Functions?

New York, NY, USA: Associ- ation for Computing Machinery, 2021, pp. 1330–1342. isbn: 9781450380539. doi: 10.1145/3406325.3451047. arXiv: 2010.12629 [quant-ph] . [A W14] Andris Ambainis and Ronald de Wolf. “How Low can Approximate D egree and Quantum Query Complexity be for Total Boolean Functions?” In : Com- putational Complexity 23 (2 2014), pp. 305–322....

arXiv 2002