{"id":"e128af9b-0a88-410c-9f5b-cf39a5319589","arxiv_id":"2507.00148","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For hazard-free extensions of Boolean functions, u-sensitivity, u-block sensitivity, u-certificate complexity and u-query complexity are linearly equivalent, yielding Du = O(Ru^2) and Du = O(Qu^4).","lead":"This paper introduces a model of Boolean query complexity where answers can be 0, 1, or \"unknown\", and where the algorithm must output \"unknown\" only when the value is genuinely undetermined from the revealed bits. It proves that in this uncertainty model, the main complexity measures are linearly equivalent, and that deterministic query complexity is at most quadratic in randomized and quartic in quantum query complexity.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the Theorem 3.7 gap is genuine but non-central and patchable; the central linear-equivalence and query-complexity results hold.","rationale":"I read the paper in good faith and stress-tested the strongest claim. The reader's conditional verdict is appropriate. The only substantive gap is the unproved one-u extension in Theorem 3.7, exactly as the reader identified. That gap is real but not load-bearing for the central theorem: Theorem 3.1 and the polynomial query-complexity relationships do not use it. Moreover, the gap is easily filled by a standard path argument, so it does not undermine correctness. I also checked the surrounding proofs: the u-certificate upper bound in Theorem 3.1 is sound once one notes that the chosen implicant/implicate can only involve u-positions of x; the Algorithm 1 correctness proof is valid; and the randomized and quantum lower bounds in Lemma 4.3 are standard adversary arguments with no hidden assumption. Several typos exist (e.g., the MAJ example and a repeated s_u^(0) in Theorem 3.9), but they are presentation issues. Since no load-bearing concern lands, I do not change the reader's verdict.","tokens_in":32211,"tokens_out":32260,"duration_ms":393206,"concrete_test":"Patch Theorem 3.7 explicitly: for ef(x)=u, pick x0,x1 in Res(x) with f(x0)!=f(x1), walk a path between them in the Boolean subcube, and take the first coordinate where f flips; the ternary string y that agrees with both endpoints off that coordinate and is u at it satisfies ef(y)=u. Then re-derive Lemma 3.8 and the Appendix B equivalences from this y. Also verify in Theorem 3.1 that the prime implicant selected at a 1-resolution and the prime implicate selected at a 0-resolution use only u-positions of x; if this check fails on any example, the ccu upper bound needs repair.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim, Theorem 3.1, is well supported. The chain max{k1,k2} <= su(f) <= bsu(f) <= ccu(f) <= k1+k2-1 goes through: the u-sensitivity lower bound follows from prime implicants/implicates, and the certificate upper bound can be justified by observing that any implicant true on a 1-resolution and any implicate false on a 0-resolution can only use positions where x is u, so revealing the union of the two terms (which share a variable) certifies ef(x)=u. Lemma 3.5 and Algorithm 1 give Du(f)=O(ccu(f)bsu(f)), and the randomized/quantum lower bounds in Lemma 4.3 are standard adversary arguments that check out. The reader's weakest assumption is the only real gap: Theorem 3.7 asserts, without proof, that every u-input with more than one u has a more certain extension y with exactly one u and ef(y)=u. This is true: choose two Boolean resolutions of x with different f-values, take any path between them in the resolution subcube, and use the first flipping edge to define y. However, this assertion feeds only Lemma 3.8, Theorem 3.9, and Appendix B; it is not needed for Theorem 3.1 or for the Du=O(Ru^2), Du=O(Qu^4) relationships. The manuscript also contains minor typos and some compressed proof passages, but I found no load-bearing flaw in the central argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the query complexity of hazard-free extensions ef:{0,u,1}^n -> {0,u,1} of Boolean functions f, i.e., the unique most-certain extension under Kleene's strong logic of indeterminacy. It defines u-analogues of sensitivity, block sensitivity, certificate complexity, and deterministic/randomized/quantum query complexity. The central result, Theorem 3.1, shows that max{k1,k2} <= su(f) <= bsu(f) <= ccu(f) <= k1+k2-1, where k1 and k2 are the largest prime implicant and prime implicate sizes; this yields a linear equivalence among these four measures. Using Algorithm 1, the paper proves Du(f)=O(ccu(f)bsu(f)), and via Lemma 4.3 it derives Du(f)=O(Ru(f)^2) and Du(f)=O(Qu(f)^4), an analogue of Huang's sensitivity theorem in the uncertainty model. The paper also gives exact u-query complexity bounds for MUX_n, shows that monotone functions have Du/Ru/Qu within a constant of their Boolean counterparts, proves exponential decision-tree size blow-ups for AND and near-optimal lower bounds, constructs decision trees for limited uncertainty, and proves a learning radius theorem for hazard-free extensions of low u-sensitivity.","tokens_in":32469,"tokens_out":22442,"duration_ms":251750,"significance":"If the missing justifications discussed below are supplied, this is a solid and interesting contribution. The main linear equivalence is surprising because it contrasts with the Boolean world, where sensitivity and block sensitivity can be quadratically separated; here the proof is elementary and avoids Huang's spectral method. The resulting Du=O(Ru^2) and Du=O(Qu^4) bounds improve on the best-known Boolean-world relationships, and the exact MUX analysis provides sharp separations. The decision-tree size results and the learning-radius theorem are concrete and falsifiable. The paper is self-contained in its main line, with explicit constants and constructive algorithms; the MUX adversary is detailed and the monotone-function reduction is clean. The principal weaknesses are two local proof gaps: an unproved one-u extension assertion in Theorem 3.7 and an incorrect alphabet in a step of Lemma 3.5; both are repairable without changing the paper's main conclusions.","major_comments":[{"comment":"In the proof that the sets B1,...,Bk form disjoint sensitive blocks, the text asserts that for each i there is a string alpha_i in {0,1}^{|B_i|} such that x' with B_i set to alpha_i is a u-input. This is not correct when the u-certificate c_i contains a u at a position of B_i: the queried value may be 0 or 1, and replacing that position by a Boolean value need not give a u-output, whereas replacing it by u does. The proof should allow alpha_i in {0,u,1}^{|B_i|}; Definition 2.3 permits the witness string to contain u's, so the block-sensitivity conclusion remains valid after this change.","section":"§3.1, Lemma 3.5"},{"comment":"The last item of the proof relies on the assertion, made in parentheses, that every input x with more than one u and ef(x)=u has a more certain extension y with exactly one u and ef(y)=u, described as 'y is an edge in the hypercube'. No proof is given. This assertion is true: choose two Boolean resolutions of x with different f-values and take a path between them in the Boolean subcube on the u-positions; the first edge whose endpoints have different f-values defines the required y. The argument should be included, because Lemma 3.8, Theorem 3.9, and the alternative-sensitivity results in Appendix B depend on this one-u reduction.","section":"§3.2, Theorem 3.7"},{"comment":"The proof of the last inequality uses the fact that every prime implicant and every prime implicate of a Boolean function share at least one variable, but this fact is neither stated nor proved. It is true: if a prime implicant P and a prime implicate Q were variable-disjoint, an assignment satisfying all literals of P and falsifying all literals of Q would be consistent and would force f to be both 1 and 0. Please add this one-line lemma explicitly, since the k1+k2-1 bound is exactly where the shared variable is used.","section":"§3.1, proof of Theorem 3.1"}],"minor_comments":[{"comment":"The displayed inequality '2size(f)-1 <= sizeu(f) <= 2size(f)-1' appears to contain a typesetting error; the proof in §5.3 establishes the lower bound 2*size(f)-1 and the upper bound 2^{size(f)}-1. The theorem statement should be corrected.","section":"§1.1.3, Theorem 1.10"},{"comment":"The sentence 'flipping any of the 1's to a 0 makes the function 1' is incorrect; on the described input (n zeros, one u, n ones), flipping a 1 to 0 produces a u-output, not a 1-output. The stated sensitivity value 2n+1 is still correct, but the explanatory sentence should be fixed.","section":"§3.2, MAJ example"},{"comment":"The expression binom(n,n/3)binom(2n/3,n/3) and the range [n/3,2n/3] assume that n is divisible by 3; for arbitrary n the statement should use floors and ceilings or explicitly restrict n to multiples of 3.","section":"§5.2, Definition 5.4"},{"comment":"The statement that ef is 'the unique function such that f' <= ef for all natural f'' should specify that ef is the most certain (maximal) natural extension; as written it could be misread as defining an arbitrary upper bound rather than the best possible deterministic output.","section":"§1, natural extensions"},{"comment":"There are several compressed proof phrases and typographical errors, for example 'the values ... is known' in Section 7 and 'Proceedins' in the bibliography entry for [IKS23]; a careful proofreading pass is needed.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The central contribution is sound and well within the scope of the journal. The two technical gaps flagged in the major comments are genuine but local and easily repairable; I do not see any fundamental flaw in the main theorem or in the Du/Ru/Qu relationships. The appendix on CREW-PRAM time is somewhat tangential to the main line, and its recurrence should be checked for consistency with the ternary alphabet, but it is not needed for the paper's central claims. No concerns about novelty or attribution: the relation to hazard-free circuits [IKL+19] is clearly acknowledged."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper is in good shape. It defines a natural three-valued query model (u-query complexity) for hazard-free extensions of Boolean functions and proves a genuine analogue of Huang's sensitivity theorem: max prime implicant/implicate size, u-sensitivity, u-block sensitivity, and u-certificate complexity are all linearly equivalent. That's a clean result, and the proof via prime implicants/implicates is simpler than Huang's spectral argument because the u-domain lets you read the certificate structure directly. The downstream bounds Du=O(Ru^2) and Du=O(Qu^4) improve on or match the best Boolean-world relationships, and the exact MUX bounds (Du=2^n+n, Ru=Theta(2^n), Qu=Theta(2^{n/2})) plus the decision-tree size separations (AND exponential, MUX polynomial) give the model teeth. The monotone equivalence and the limited-uncertainty parameterization are useful additions.\n\nI read the central chain carefully. Theorem 3.1 goes through; the certificate upper bound is the one place where the prose is terse, but the union of a prime implicant and prime implicate does certify u, and the k1+k2-1 bound is correct. Lemma 4.3's randomized and quantum lower bounds via Yao and Ambainis are standard and check out. The MUX adversary is complicated but consistent; the decision-tree size arguments for AND and MUX also hold.\n\nThe main soft spot is Theorem 3.7. It asserts without proof that any u-input with more than one u has a more certain single-u extension y with ef(y)=u. That statement is true — take two Boolean resolutions with different f-values and walk a path between them; the first edge where f flips gives you such a y — but the paper should include that argument because Lemma 3.8, Theorem 3.9, and Appendix B depend on it. This is patchable and not load-bearing for Theorem 3.1 or the Du/Ru/Qu relationships. There are also assorted typos and compressed passages, e.g., in Theorem 3.9's statement and proof. None of these change my read of the main results.\n\nWho this is for: query-complexity people who want a new model with clean separation results, and anyone working on hazard-free circuits or sensitivity-based learning. It deserves a serious referee, not a desk reject. I would accept it for review and ask for the Theorem 3.7 patch plus a proofreading pass.","headline":"A solid, mostly correct new model for query complexity under uncertainty; the central linear sensitivity theorem and the MUX bounds hold, with one patchable gap in Theorem 3.7.","tokens_in":33040,"tokens_out":3807,"would_cite":true,"duration_ms":41725,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For Boolean functions with inputs that may be unknown, the measures $s_u$, $bs_u$, $cc_u$, and $\\max\\{k_1,k_2\\}$ are linearly equivalent, giving a hazard-free analogue of Huang's sensitivity theorem and the bounds $D_u=O(R_u^2)=O(Q_u^4)$.","keywords":["query complexity","hazard-free extension","sensitivity","block sensitivity","certificate complexity","Kleene three-valued logic","decision trees","uncertainty"],"falsifier":"Run an exhaustive check over all Boolean functions on four variables: for every input with two or more u's, test whether some setting of all but one u to 0 or 1 yields an $\\tilde f$-output of u; this directly tests the unproved step in Theorem 3.7, and a single counterexample would falsify the sharper sensitivity claims.","tokens_in":32023,"feed_emoji":"❓","tokens_out":15332,"duration_ms":140892,"temperature":0.7,"pith_summary":"Querying a Boolean function when input bits may be unknown changes the model: answers are 0, 1, or u, and the hazard-free extension outputs 0 or 1 only when every resolution of the unknowns gives that value, otherwise u. This paper shows that in that model u-sensitivity, u-block sensitivity, u-certificate complexity, and the size of the largest prime implicant or prime implicate of the Boolean function are linearly equivalent. From that equivalence it derives $D_u(f)=O(bs_u(f)^2)=O(R_u(f)^2)=O(Q_u(f)^4)$, improving the best-known deterministic-versus-randomized bound from the ordinary Boolean model. It also proves an exponential depth blow-up for MUX, an exponential size blow-up for AND, general conversions from Boolean decision trees to hazard-free trees, and parameterized conversions when at most $k$ inputs are unknown. A reader should care because the hard core of computing with uncertainty turns out to be governed by simple syntactic width measures of the function.","feed_headline":"Sensitivity theorem survives unknown input bits","feed_subtitle":"Hazard-free query complexity: deterministic cost is at most quadratic in randomized and quartic in quantum cost.","key_machinery":"The machinery is the hazard-free extension: for $x\\in\\{0,u,1\\}^n$, $\\tilde f(x)=b\\in\\{0,1\\}$ iff $f$ is constant on the Boolean resolutions of $x$, and $\\tilde f(x)=u$ otherwise; queries are made to a ternary oracle, and deterministic u-query complexity is the depth of a ternary decision tree computing $\\tilde f$. The argument is carried by prime implicants and prime implicates of $f$, the minimal sets of literals that force output 1 or 0 respectively. Their maximum sizes $k_1$ and $k_2$ lower-bound u-sensitivity (each literal of a largest prime implicant is sensitive at the all-u-elsewhere input) and upper-bound u-certificate complexity (a certificate for a u-output can reveal one prime implicant and one prime implicate, which share a variable). This syntactic handle replaces the spectral approach used in the Boolean sensitivity theorem.","core_discovery":"The paper's central claim is that for the hazard-free extension $\\tilde f$ of any Boolean function $f$, the parameters $\\max\\{k_1,k_2\\}$, $s_u(f)$, $bs_u(f)$, and $cc_u(f)$ are linearly equivalent, with $\\max\\{k_1,k_2\\} \\le s_u(f) \\le bs_u(f) \\le cc_u(f) \\le k_1+k_2-1$, where $k_1$ and $k_2$ are the sizes of the largest prime implicant and prime implicate of $f$. The proof is elementary: a largest prime implicant defines an input with u's everywhere else, and every literal of that implicant is u-sensitive; a certificate for a u-output is obtained by revealing one prime implicant and one prime implicate, which necessarily share a variable. This gives $D_u(f)=O(cc_u(f)\\cdot bs_u(f))=O(bs_u(f)^2)$, and standard minimax and adversary arguments give $bs_u(f)=\\Omega(R_u(f))$ and $bs_u(f)=\\Omega(Q_u(f)^2)$, so $D_u(f)=O(R_u(f)^2)=O(Q_u(f)^4)$. The same three-valued framework yields an exponential depth blow-up for the multiplexer function, an exponential size blow-up for AND, a general conversion from Boolean decision trees to u-trees, and a parameterized conversion when at most $k$ inputs are unknown.","pith_inferences":["The authors leave open whether the Boolean sensitivity theorem and the all-unknown theorem can be unified; the parameterized tree construction suggests a concrete route: prove a sensitivity theorem for inputs with at most $k$ unknowns, interpolating between Huang's exponent and linearity.","Because $\\mathrm{size}_u(f)$ is at least the number of prime implicants plus the number of prime implicates, the uncertainty model magnifies syntactic redundancy; one can search for functions with small Boolean decision trees but exponentially many primes to obtain strong size blow-ups beyond the balanced-counting example of Section 5.2.","The $4s$ Hamming-ball specification for hazard-free extensions, versus the $2s$ radius in the Boolean setting, is a natural tightness test: checking whether MAJ requires the larger radius would indicate whether the extra uncertainty genuinely doubles the learning burden."],"forward_implications":["For every Boolean $f$, $D_u(f)=O(R_u(f)^2)$, improving the best-known cubic deterministic-randomized bound in the ordinary query model, and $D_u(f)=O(Q_u(f)^4)$, matching the best Boolean bound.","U-sensitivity and u-block sensitivity are linearly related, so Rubinstein-type quadratic gaps between sensitivity and block sensitivity disappear once uncertainty is allowed.","CREW-PRAM time for hazard-free extensions is, up to constant factors, $\\log(\\max\\{k_1,k_2\\})$, giving a syntactic characterization of parallel time under uncertainty.","MUX$_n$, one of the easiest Boolean functions, becomes evasive under uncertainty: $D_u(\\mathrm{MUX}_n)=2^n+n$, with $R_u(\\mathrm{MUX}_n)=\\Theta(2^n)$ and $Q_u(\\mathrm{MUX}_n)=\\Theta(2^{n/2})$.","For inputs with at most $k$ unknowns, a Boolean decision tree of size $s$ and depth $d$ converts to a hazard-free tree of depth $O(2^k d)$ and size polynomial in $s$ for constant $k$, so limited uncertainty contains the blow-up to the parameter $k$."],"supporting_citations":[{"why":"The classical sensitivity theorem whose hazard-free analogue is proved; its fourth-power bound is the benchmark replaced by linearity.","marker":"[Hua19]"},{"why":"Supplies the survey-level inequalities $s(f)\\le bs(f)\\le cc(f)$ that seed Theorem 3.1 and the decision-tree definitions used throughout.","marker":"[BdW02]"},{"why":"Its CREW-PRAM time lower bound in terms of sensitivity is adapted in Appendix A to bound time for hazard-free extensions.","marker":"[CDR86]"},{"why":"Introduces block sensitivity and the pointer-doubling upper bound on CREW-PRAM time that the uncertainty model adapts.","marker":"[Nis91]"},{"why":"Yao's minimax principle is used to prove the randomized lower bound $R_u(f)=\\Omega(bs_u(f))$.","marker":"[Yao77]"},{"why":"The adversary method is used to prove the quantum lower bound $Q_u(f)=\\Omega(\\sqrt{bs_u(f)})$.","marker":"[Amb02]"},{"why":"Documents the best-known Boolean-world polynomial relationships that the paper's quadratic and quartic bounds improve or match.","marker":"[ABK+21]"},{"why":"Grover search underlies the quantum u-query algorithm for MUX and the quadratic deterministic-quantum separation.","marker":"[Gro96]"},{"why":"Defines the monotone multiplexer mMUX used to demonstrate that hazard-free extensions of easy functions can remain easy.","marker":"[Weg85]"}],"fun_headline_variants":["Sensitivity theorem survives uncertain inputs","Hazard-free query complexity: quadratic and quartic","Uncertainty boosts decision tree depth exponentially","New bounds for Boolean functions with unknown bits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the sharper characterization in Theorem 3.7 rests on an unproved assertion—that every input with more than one unknown value has a one-unknown refinement still evaluating to ‘unknown’—and if that assertion failed, the improved sensitivity bounds and the alternative-sensitivity equivalences in Appendix B would need repair, while the linear-equivalence theorem itself would survive.","fun_headline_variants_meta":{"raw":{"variants":["Sensitivity theorem survives uncertain inputs","Hazard-free query complexity: quadratic and quartic","Uncertainty boosts decision tree depth exponentially","New bounds for Boolean functions with unknown bits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000216,"raw_usage":{"total_tokens":1512,"prompt_tokens":1104,"completion_tokens":408,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":720,"completion_tokens_details":{"reasoning_tokens":353}},"tokens_in":720,"tokens_out":408,"duration_ms":4668,"temperature":1.0,"reasoning_tokens":353,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:28:39.139304+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive check over all Boolean functions on four variables: for every input with two or more u's, test whether some setting of all but one u to 0 or 1 yields an $\\tilde f$-output of u; this directly tests the unproved step in Theorem 3.7, and a single counterexample would falsify the sharper sensitivity claims.","supporting_citations":[],"review_version":1}