{"id":"62fc90cf-7d4b-4470-9328-751566a4bfe0","arxiv_id":"2507.13963","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For every total Boolean function, the logs of exact and approximate De Morgan sparsity (and of exact and approximate l1 norm) are polynomially related up to a log n factor, resolving a 2021 conjecture.","lead":"Researchers prove a conjecture about Boolean formulas: allowing small errors in a polynomial representation of a Boolean function does not let you make the formula much shorter, when the terms are built from AND operations (the De Morgan basis). The proof introduces an adaptive random restriction method, a new technique that may be useful for other open problems in computational complexity.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the adaptive restriction proof of the main sparsity and ℓ1-norm theorems is coherent; remaining gaps are minor and do not threaten the central claim.","rationale":"The paper's central theorems are mathematically plausible and the proofs are internally consistent after close reading. The random restriction Algorithm 1 is genuinely adaptive; the lower bound on active calls (Claim 3.5) and the full-degree/exponential-tail properties (Claim 3.6) check out. The use of degree vs approximate degree is legitimate with a fixed universal constant. I therefore do not see a concern that would overturn Theorem 1.1 or Theorem 1.5. The items that gave the reader pause are real but minor: Claim 4.21 is an omission rather than an error, the Theorem 1.4 exponent is an easily corrected typo, and the error-amplification citation in Claim 3.9 is a mis-citation for a standard fact. The false equality Cover=M(f) in Remark 4.8 is the most substantive issue; however, the proof only needs Cover≤M(f), which follows because each minterm (resp. maxterm) gives a monochromatic 1-subcube (resp. 0-subcube), so the minterm/maxterm subcubes cover the cube with at most M(f) subcubes. Thus Theorem 4.7 survives. Since all problems are fixable without changing the main results, the verdict should remain unchanged from the reader's conditional acceptance.","tokens_in":32772,"tokens_out":38363,"duration_ms":443089,"concrete_test":"Write out the missing proof of Claim 4.21 by adapting Claim 3.9 to max-sensitivity distributions: apply Markov to the degree-k tail of a low-weight generalized approximator, trim the tail, amplify the residual 0.44-approximator to 1/3 with a constant-degree polynomial, and derive the Ω(√ℓ) contradiction with Theorem 4.19. If this adaptation fails, Theorem 1.8(b) is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing flaw in the central argument. Theorem 1.1 and Theorem 1.5 rest on the max-degree distribution of §3; Claims 3.5 and 3.6 give the three distribution properties, and Claims 3.8/3.9 correctly convert them into sparsity/weight lower bounds via deg ≤ c·Ądeg^2. The concern that the universal constant c in Theorem 2.7 must match the constant in k=√(ℓ/c) is addressed by choosing c to be exactly that constant. The remaining issues are presentational: Claim 4.21 is stated without proof although it is needed for Theorem 1.8(b); the adaptation of Claim 3.9 is straightforward but should be written out. Theorem 1.4's statement drops a log n factor relative to its proof (Claim 3.17 + Claim 3.18 + Theorem 1.1 gives log^6 Ąspar · log^2 n). Claim 3.9 cites Theorem 2.6 for 0.44-error to 1/3-error amplification; Theorem 2.6 as stated handles 1/3 to smaller ε, but a constant-degree composition fills the gap. Remark 4.8's assertion Cover(f)=M(f) is false in general (OR has M=n+1 and Cover=2), but the required direction Cover(f)≤M(f) holds via minterm/maxterm subcubes, so Theorem 4.7 still follows.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the gap between exact and approximate polynomial representations of total Boolean functions in the De Morgan basis. The main result, Theorem 1.1, states that for every total Boolean function f, log(spar(f)) = O(log^2(~spar(f)) · log n), confirming a conjecture of Knop et al. The proof introduces an adaptive random restriction process, Algorithm 1 (MaxDegreeRestriction), which produces a max-degree distribution for any function with large exact l1-norm: with high probability many variables remain free, the restricted function has full degree, and every monomial's degree under the restriction has an exponential tail bound. The same machinery yields Theorem 1.5, the analogous statement for exact and approximate l1-norm, and Section 4 extends the approach to generalized monomials, proving Theorem 1.8 for monotone functions via separating sets and max-sensitivity distributions. Applications to AND-decision-tree complexity and decision-tree size are derived in Theorem 1.4 and Corollary 1.9.","tokens_in":33044,"tokens_out":19107,"duration_ms":210651,"significance":"If the results are correct, the paper settles an open conjecture and shows that, on a logarithmic scale, approximation does not significantly reduce sparsity or coefficient mass in the De Morgan basis, in sharp contrast to the Fourier basis. The adaptive restriction method is a genuine technical novelty: it applies to arbitrary functions with large algebraic weight rather than to functions with explicit combinatorial structure, and it is developed carefully enough that the main probabilistic claims are verifiable. The derived consequences for AND-query complexity and for decision-tree size of monotone functions are concrete and nontrivial. The paper also gives matching or near-matching examples, including the Or function and the threshold function Thrn_{n-1}, which usefully calibrate the bounds. Overall, this is a strong contribution if the two issues identified below are fixed.","major_comments":[{"comment":"Claim 4.21 is stated without proof and is load-bearing for Theorem 1.8(b) and Corollary 1.9(b), since those results require a lower bound on the approximate generalized weight. The text says only that the proof is omitted because it involves no new ideas. For a journal submission, this is not sufficient: please provide the full argument, adapting the reasoning of Claim 3.9 to max-sensitivity distributions, including the tail-weight Markov step and the constant-error to 1/3-error reduction, or explicitly state and prove a lemma that fills this gap.","section":"§4.3, Claim 4.21"},{"comment":"The stated upper bound in Theorem 1.4 is not justified by the cited ingredients. Combining Claim 3.17, Claim 3.18, and Theorem 1.1 gives D_AND(f) = O((log MBS(f))^2 · log spar(f) · log n) = O((log^2 ~spar(f))^2 · (log^2 ~spar(f) · log n) · log n) = O(log^6 ~spar(f) · log^2 n), not O(log^6 ~spar(f) · log n) as stated. Either restate Theorem 1.4 with log^2 n, or prove an improved version of Claim 3.17 or Claim 3.18 that removes one log n factor; the displayed equality in the proof is currently incorrect.","section":"§3.4, Theorem 1.4 and its proof"}],"minor_comments":[{"comment":"The proof invokes Theorem 2.6 to amplify an approximation with error 0.44 to error 1/3, but Theorem 2.6 as stated converts 1/3-error into smaller error. The intended step is a standard constant-degree composition; please add a sentence explaining the direction and the constant-degree error reduction.","section":"§3.2, Claim 3.9"},{"comment":"The remark asserts Cover(f) = M(f) for monotone functions without proof. The derivation of Theorem 4.7 only needs the direction Cover(f) ≤ M(f), which follows from covering each input by a minterm or maxterm subcube. Please either prove the asserted equality or state and use only the needed inequality.","section":"§4.1, Remark 4.8"},{"comment":"The proof says the algorithm halts when |V| = 1, 'which corresponds to |F| ≤ 2', but the base case in Algorithm 2 is |F| ≤ 2 and can occur while |V| is still large. The bound t ≤ n still holds because every recursive call removes one variable from V, but the parenthetical is confusing and should be reworded.","section":"§4.3, Claim 4.16 proof"},{"comment":"There are minor typographical errors: 'max-sesitivity' appears instead of 'max-sensitivity' in the paragraph after Algorithm 2, and 'sensitvity' appears in Claim 4.20. Please proofread these terms.","section":"§4.3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is well within the scope of cs.CC and the main theorem is likely to be of broad interest. The two major issues—the missing proof of Claim 4.21 and the log-factor error in Theorem 1.4—are fixable in revision, but they affect stated results and should be resolved before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a real result and the main proofs are sound. The paper proves that for every total Boolean f, log spar(f) = O(log^2 Āspar(f) · log n), resolving the KLMY conjecture, and it also gets the ℓ1-norm analog plus a monotone generalized-monomial statement. The adaptive random restriction in Algorithm 1 is the genuine novelty—it samples restrictions based on how the ℓ1 norm of the polynomial evolves, and the three distribution properties (many free variables, full degree, exponential tail for monomial degree) are exactly what makes the reduction to deg ≤ c·Ādeg^2 go through. I read Claims 3.5 and 3.6 carefully; they hold. The approach is worth more than the theorem itself, since it gives a generic way to convert exact-size hardness into approximate-size lower bounds.\n\nThe soft spots are minor, not load-bearing. Theorem 1.4's statement appears to drop a log n: combining Claim 3.17 with Claim 3.18 and Theorem 1.1 gives O(log^6 Āspar · log^2 n), not O(log^6 Āspar · log n). The proof sketch in the text actually points to the former—Claim 3.17 already carries a log n factor, and substituting log spar = O(log^2 Āspar · log n) adds another. That needs a correction in the statement. Claim 4.21, the approximate generalized weight lower bound from a max-sensitivity distribution, is asserted without proof. It looks like a straightforward adaptation of Claim 3.9, but it should be written out. Remark 4.8's Cover(f) = M(f) is false in general (OR has M = n+1 and Cover = 2), though the direction actually used, Cover(f) ≤ M(f), holds via minterm/maxterm subcubes, so the argument survives. Claim 3.9 also cites Theorem 2.6 for 0.44-error to 1/3-error amplification; the theorem as stated goes from 1/3 to smaller ε, but a constant-degree composition fills the gap, so this is a citation-application detail.\n\nThe stress-test worry about the constant c in deg ≤ c·Ādeg^2 matching the k = sqrt(ℓ/c) choice is resolvable: you take the same universal constant, and Theorem 2.7 supplies it. I see no circularity and no fitted parameters. The dependence on Ehrenfeucht–Haussler in Section 4 is reasonable.\n\nWho is this for: anyone working on polynomial representations, query complexity, or And-decision trees. It will be cited. With a short fix list, it deserves a serious referee round. I recommend sending it out.","headline":"Confirms the Knop–Lovett–McGuire–Yuan conjecture with a genuinely new adaptive restriction scheme; the central proof holds up, and the remaining issues are small and fixable.","tokens_in":33603,"tokens_out":1748,"would_cite":true,"duration_ms":18487,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","06E30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that exact and approximate sparsity of total Boolean functions are polynomially related on the logarithmic scale in the De Morgan basis, up to a log n factor.","keywords":["De Morgan basis","Boolean functions","polynomial sparsity","approximate sparsity","random restrictions","ℓ1 norm","generalized monomials","monotone functions"],"falsifier":"Build or search an explicit family of total Boolean functions and compute $\\mathrm{spar}(f)$ and $\\widetilde{\\mathrm{spar}}_{1/3}(f)$; a single family with $\\log \\mathrm{spar}(f) / ((\\log \\widetilde{\\mathrm{spar}}_{1/3}(f))^2 \\log n) \\to \\infty$ would falsify Theorem 1.1, and the analogous ratio against $(\\log n)^3$ would falsify Theorem 1.8.","tokens_in":32559,"feed_emoji":"⚖️","tokens_out":14355,"duration_ms":155634,"temperature":0.7,"pith_summary":"Boolean functions have two natural real-polynomial descriptions: an exact one and a pointwise-approximating one. A classic result [44] shows the degrees of the two descriptions are never far apart; this paper proves the same phenomenon for sparsity in the De Morgan basis. For every total Boolean function $f$, it establishes $\\log(\\mathrm{spar}(f)) = O(\\log^2(\\widetilde{\\mathrm{spar}}(f)) \\cdot \\log n)$, and the same restriction argument yields $\\log(\\mathrm{wt}(f)) = O((\\log \\widetilde{\\mathrm{wt}}(f))^2 \\log n)$. This confirms the conjecture of [39] that approximation cannot exponentially reduce De Morgan sparsity, in sharp contrast with the Fourier basis, where And is exponentially sparse only approximately. For monotone functions, the paper extends the phenomenon to generalized monomials, with the consequence that deterministic and randomized decision-tree size are polynomially related on the log scale.","feed_headline":"Approximate sparsity stays close to exact sparsity on the log scale","feed_subtitle":"The theorem confirms the conjecture that approximation cannot exponentially shrink De Morgan representations.","key_machinery":"The key object is an adaptive random restriction process, Algorithm 1 (`MaxDegreeRestriction`). It reads the current multilinear polynomial; if some variable can be fixed while retaining almost all $\\ell_1$ weight, it fixes it in a passive step, otherwise it takes a random active step: with probability $1/2$ it fixes the chosen variable to 0, and with probability $1/2$ it leaves it free while replacing the polynomial by its discrete derivative. The output distribution leaves $\\Omega(\\log \\mathrm{wt}(f)/\\log n)$ free variables, keeps the restricted polynomial at full degree on free variables, and gives monomial degrees an exponential tail $\\Pr[\\deg(M|_\\rho) \\ge t] \\le 2^{-t}$. The generalized-monomial version replaces full degree by full sensitivity and is driven by Algorithm 2 (`MaxSensitivityRestriction`), which uses a separating set of inputs; both processes are the engine that converts a large exact measure into a large approximate lower bound.","core_discovery":"The central claim is that De Morgan sparsity is polynomially related under approximation: for every total $f$, $\\log \\mathrm{spar}(f) = O(\\log^2 \\widetilde{\\mathrm{spar}}(f) \\cdot \\log n)$, and the same proof yields $\\log \\mathrm{wt}(f) = O((\\log \\widetilde{\\mathrm{wt}}(f))^2 \\log n)$. The argument starts from a large exact $\\ell_1$ norm and forces any $1/3$-approximating polynomial to have sparsity at least $2^{\\Omega(\\sqrt{\\log \\mathrm{wt}(f)/\\log n})}$. For monotone functions generalized to monomials built from $x_i$ and $1-x_i$, the paper proves $\\log g\\mathrm{spar}(f) = O((\\log \\widetilde{g\\mathrm{spar}}(f))^4 (\\log n)^3)$ and the analogous weight bound, using separating sets of minterms or maxterms. These results confirm the conjecture of [39] and place deterministic and randomized query complexity, sparsity, and $\\ell_1$ norm in one polynomial equivalence class on the log scale in the De Morgan world.","pith_inferences":["The same adaptive restriction template could apply to other representation families in Question 1.6, not just De Morgan and generalized monomials; the paper leaves open which families admit the separating structure that makes the argument go through.","The threshold function example shows the $\\log n$ factor cannot be avoided; a natural search is for families of functions interpolating between Or and thresholds to test whether the quadratic exponent in Theorem 1.1 is also unavoidable.","If a matching approximate-rank bound for $f \\circ \\mathrm{And}_2$ were found, the main theorem would immediately give a polynomial upper bound on zero-error deterministic communication in terms of quantum bounded-error communication; the paper's Question 1.11 is precisely the missing piece.","Since the generalized-monomial proof passes through minterms and maxterms, non-monotone functions with few separating sets are the natural candidates for a counterexample to the monotone-style statement; this could be checked by exhaustive search on small cubes."],"forward_implications":["Randomized And-decision-tree complexity is characterized by $\\log \\widetilde{\\mathrm{spar}}(f)$ on the log scale: $R^{\\wedge}_{\\mathrm{dt}}(f) \\le D^{\\wedge}_{\\mathrm{dt}}(f) \\le O((\\log \\widetilde{\\mathrm{spar}}(f))^6 \\log n)$.","Exact and approximate $\\ell_1$ norms are quadratically related on the log scale, so a small-weight approximating polynomial forces the exact representation to have weight at most $2^{O((\\log \\widetilde{\\mathrm{wt}}(f))^2 \\log n)}$.","For monotone functions, generalized sparsity and weight control ordinary decision-tree size, yielding $\\log D_{\\mathrm{dt}}(f) = O((\\log \\widetilde{g\\mathrm{spar}}(f))^4 (\\log n)^3)$, and similarly for weight.","Every shifted De Morgan basis inherits the main relation, so approximation cannot exponentially reduce sparsity or weight in any of the $2^n$ shifted bases.","Combined with the And-function log-rank result [40], a positive answer to the paper's approximate-rank question would bound deterministic zero-error communication by a polynomial of quantum bounded-error communication for every $f \\circ \\mathrm{And}_2$."],"supporting_citations":[{"why":"Establishes the degree-versus-approximate-degree framework and gives the sensitivity-to-approximate-degree lower bound used in the generalized-monomial argument.","marker":"[44]"},{"why":"Supplies the tight theorem deg(g)=O(\\widetilde{deg}(g)^2) that the restriction argument contradicts in Claims 3.8 and 3.9.","marker":"[1]"},{"why":"Conjectures that approximation cannot significantly reduce De Morgan sparsity; Theorem 1.1 resolves this conjecture and supplies the lower-bound link to randomized And-query complexity.","marker":"[39]"},{"why":"Gives the deterministic And-decision-tree bounds in terms of log sparsity and monotone block sensitivity that combine with the main theorem to yield Theorem 1.4.","marker":"[40]"},{"why":"Provides the decision-tree-size and cube-cover bound that converts large exact generalized sparsity or weight into many minterms or maxterms for monotone functions, the bridge for Theorem 1.8.","marker":"[26]"},{"why":"Supplies the error-reduction theorem used to boost a 0.44-error approximant to 1/3 without increasing degree beyond a constant factor.","marker":"[25]"},{"why":"Underlies the weight-to-sparsity conversion theorem used to relate approximate $\\ell_1$ norm and approximate sparsity.","marker":"[29]"}],"fun_headline_variants":["Approximation keeps De Morgan sparsity log-scale polynomial close","No exponential shrink: approximate De Morgan sparsity tied to exact","De Morgan: exact and approximate sparsity polynomially related on log scale","Log-scale polynomial gap: exact vs approximate De Morgan sparsity","Adaptive restriction ties exact and approximate De Morgan sparsity on log scale"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof hangs on the theorem that every total Boolean function's exact degree is at most a constant times the square of its approximate degree, with one universal constant serving both in the fixed-constant choice and in the contradiction; the generalized-monomial half additionally assumes the cube-cover bound that turns large exact generalized sparsity into many minterms or maxterms.","fun_headline_variants_meta":{"raw":{"variants":["Approximation keeps De Morgan sparsity log-scale polynomial close","No exponential shrink: approximate De Morgan sparsity tied to exact","De Morgan: exact and approximate sparsity polynomially related on log scale","Log-scale polynomial gap: exact vs approximate De Morgan sparsity","Adaptive restriction ties exact and approximate De Morgan sparsity on log scale"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001133,"raw_usage":{"total_tokens":4723,"prompt_tokens":976,"completion_tokens":3747,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":592,"completion_tokens_details":{"reasoning_tokens":3657}},"tokens_in":592,"tokens_out":3747,"duration_ms":36809,"temperature":1.0,"reasoning_tokens":3657,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:16:59.855448+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build or search an explicit family of total Boolean functions and compute $\\mathrm{spar}(f)$ and $\\widetilde{\\mathrm{spar}}_{1/3}(f)$; a single family with $\\log \\mathrm{spar}(f) / ((\\log \\widetilde{\\mathrm{spar}}_{1/3}(f))^2 \\log n) \\to \\infty$ would falsify Theorem 1.1, and the analogous ratio against $(\\log n)^3$ would falsify Theorem 1.8.","supporting_citations":[{"cited_title":"On the degree of boolean functions as real polynomials","cited_arxiv_id":null,"evidence_quote":"Establishes the degree-versus-approximate-degree framework and gives the sensitivity-to-approximate-degree lower bound used in the generalized-monomial argument."},{"cited_title":"Degree vs","cited_arxiv_id":null,"evidence_quote":"Supplies the tight theorem deg(g)=O(\\widetilde{deg}(g)^2) that the restriction argument contradicts in Claims 3.8 and 3.9."},{"cited_title":"Guest column: Models of computation between decision trees and communication","cited_arxiv_id":null,"evidence_quote":"Conjectures that approximation cannot significantly reduce De Morgan sparsity; Theorem 1.1 resolves this conjecture and supplies the lower-bound link to randomized And-query complexity."},{"cited_title":"Log-rank and lifting for and- functions","cited_arxiv_id":null,"evidence_quote":"Gives the deterministic And-decision-tree bounds in terms of log sparsity and monotone block sensitivity that combine with the main theorem to yield Theorem 1.4."},{"cited_title":"Learning decision trees from random examples","cited_arxiv_id":null,"evidence_quote":"Provides the decision-tree-size and cube-cover bound that converts large exact generalized sparsity or weight into many minterms or maxterms for monotone functions, the bridge for Theorem 1.8."},{"cited_title":"Bounded independence fools halfspaces","cited_arxiv_id":null,"evidence_quote":"Supplies the error-reduction theorem used to boost a 0.44-error approximant to 1/3 without increasing degree beyond a constant factor."},{"cited_title":"On the power of circuits with gates of low l1 norms","cited_arxiv_id":null,"evidence_quote":"Underlies the weight-to-sparsity conversion theorem used to relate approximate $\\ell_1$ norm and approximate sparsity."}],"review_version":1}