{"id":"c676dd9f-5729-4592-8066-a0c516db39b5","arxiv_id":"2412.16088","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"New constructions achieve asymptotically minimal spectral sensitivity λ(f) = Θ(√log n) and an optimal sensitivity tradeoff for total Boolean functions.","lead":"This paper constructs total Boolean functions whose spectral sensitivity is the minimum possible, matching the long-known lower bound up to a constant factor. It also shows an optimal tradeoff between 0-sensitivity and 1-sensitivity for low-sensitivity functions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the terse component analysis in Theorem 9 is correct, and the central claims are sound.","rationale":"The paper's central claim, that there exist total non-degenerate Boolean functions with spectral sensitivity asymptotically minimal up to the best constant, is supported by Theorem 4. The Hamming address function is non-degenerate, has s0=1 and s1=2^r, and the upper bound λ ≤ √(s0 s1) combined with the degree lower bound gives λ = √((1+o(1)) log n). I checked the details of non-degeneracy and the sensitivity counts; they are correct. The tradeoff construction in Theorem 9 is the only place where the prose is compressed. A full edge enumeration shows that the two claimed component types are exhaustive: the outer CHAF has s0=1, so an inner CHAF 0-input has at most one sensitive neighbor; certificates are pairwise at Hamming distance at least 3, so a codeword-flip leaf cannot be adjacent to two different 1-inputs; and variables in non-addressed inner blocks cannot change f'. The two-layer star with maximum center and first-layer degrees achieves spectral radius √(s0+s1−1), and Perron–Frobenius justifies using the orbit-symmetric eigenvector. Thus the reader's weakest assumption, while identifying the right location, is not a correctness risk. The desensitization section and Theorem 7 were also checked; the generalized Simon bound is derived correctly. I therefore recommend no change to the ACCEPT verdict.","tokens_in":8245,"tokens_out":36533,"duration_ms":292693,"concrete_test":"For a small instance of Theorem 9 (e.g., l=m=1, a1=b1=2 or 3), generate the full truth table of f' = CHAF ∘' ¬CHAF, build the sensitivity graph G_{f'}, and compute its largest eigenvalue numerically. Confirm that λ = √(s0+s1−1) and that every connected component is either a star of degree s1(f')−1 or a two-layer star with center degree at most s0(f'). If any extra edges appear, the component classification in Theorem 9 is incomplete.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The apparent soft spot in Theorem 9, the short enumeration of sensitivity-graph components, survives scrutiny. Since CHAF has s0=1, every inner CHAF 0-input has at most one sensitive neighbor, so the only possible components are stars of degree s1(f')−1 (when the inner CHAF 0-input is isolated) and two-layer stars with center degree at most s0(f') and first-layer degree s1(f'). Hamming distance at least 3 between certificates prevents sharing of codeword-flip leaves, and no other edges exist: flipping a codeword bit of a matched input breaks the match, flipping an inner variable in a non-addressed block does not change the outer certificate satisfaction, and 0–0 edges are impossible by definition. The largest component is the two-layer star with center degree s0(f') and first-layer degree s1(f'), whose Perron root is √(s0+s1−1). The proof is terse but not incorrect.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8404,"tokens_out":40055,"duration_ms":322365,"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.","major_comments":[],"minor_comments":[{"comment":"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":"Abstract and Section 1"},{"comment":"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":"Section 4, after Lemma 5"},{"comment":"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":"Section 4, Proposition 6"},{"comment":"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":"Section 5, Theorem 9"},{"comment":"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":"Section 4"},{"comment":"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.","section":"Section 5, Theorem 7"}],"recommendation":"minor_revision","confidential_remarks":"The paper is within scope and the central claims are correct. The only substantive request in revision is to expand the proof of the component classification in Theorem 9; the missing details are local and easily supplied. The remaining issues are typographical and notational. I do not see any correctness problem that would require a major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nMinor 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.\n\nOverall 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.","headline":"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.","tokens_in":8897,"tokens_out":8988,"would_cite":true,"duration_ms":70699,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["spectral sensitivity","Boolean functions","sensitivity","Hamming code","address function","certificate complexity","sensitivity tradeoff","total functions"],"falsifier":"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.","tokens_in":8083,"feed_emoji":"🧮","tokens_out":13718,"duration_ms":98837,"temperature":0.7,"pith_summary":"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.","feed_headline":"Spectral sensitivity can be as low as sqrt(log n)","feed_subtitle":"New total Boolean functions match the sqrt(log n) lower bound, settling the asymptotic minimum.","key_machinery":"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).","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides the Hamming code whose codewords have pairwise Hamming distance at least 3, the property that forces s0=1 in HAF_r.","marker":"[Ham50]"},{"why":"Supplies the original sensitivity lower bound whose proof is generalized to give s0+s1 ≥ log n − log log n + 2 (Theorem 7).","marker":"[Sim83]"},{"why":"Gives deg(f) ≥ log n − O(log log n), the degree lower bound used to establish λ(f) ≥ √((1+o(1)) log n).","marker":"[NS94]"},{"why":"Gives deg(f) ≤ λ(f)^2 and λ(f) ≤ √(s0 s1), the sandwich that equates λ with √s1 when s0=1.","marker":"[Aar+21]"},{"why":"Supplies the desensitization transformation used in the second construction family.","marker":"[BHT17]"},{"why":"Provides the monotone address function, the prior example of minimal sensitivity and a test case for the desensitization bound.","marker":"[Weg85]"}],"fun_headline_variants":["Spectral sensitivity hits √log n","Tight bound for spectral sensitivity","Minimal spectral sensitivity: √log n","New functions match √log n spectral sensitivity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Spectral sensitivity hits √log n","Tight bound for spectral sensitivity","Minimal spectral sensitivity: √log n","New functions match √log n spectral sensitivity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0002,"raw_usage":{"total_tokens":1439,"prompt_tokens":1071,"completion_tokens":368,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":687,"completion_tokens_details":{"reasoning_tokens":316}},"tokens_in":687,"tokens_out":368,"duration_ms":3638,"temperature":1.0,"reasoning_tokens":316,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T10:51:08.663920+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}