Pith. sign in

REVIEW 3 major objections 5 minor 22 references

Sensitivity and Query Complexity under Uncertainty

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read 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)$.

desk verdict 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. read the letter →

arxiv 2507.00148 v1 pith:CIJT3HXO submitted 2025-06-30 cs.CC

Deepu Benson , Balagopal Komarath , Nikhil Mande , Sai Soumya Nalli , Jayalal Sarma , Karteek Sreenivasaiah This is my paper · ORCID
classification cs.CC
keywords querycomplexityhazard-freeextensionsensitivityblockcertificateKleenethree-valuedlogicdecisiontreesuncertainty
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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$.

Reading between the lines

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

  • 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.
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.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [§3.1, Lemma 3.5] 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.
  2. [§3.2, Theorem 3.7] 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.
  3. [§3.1, proof of Theorem 3.1] 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.
minor comments (5)
  1. [§1.1.3, Theorem 1.10] 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.
  2. [§3.2, MAJ example] 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.
  3. [§5.2, Definition 5.4] 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.
  4. [§1, natural extensions] 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.
  5. [General] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central sensitivity, certificate, and query-complexity bounds are derived directly from the new definitions and standard theorems, with no fitted parameter or load-bearing self-citation.

full rationale

The paper's main derivation chain is self-contained. Theorem 3.1 proves max{k1,k2} <= su(f) <= bsu(f) <= ccu(f) <= k1+k2-1 by direct arguments: the lower bound constructs an input y_P from a prime implicant/implicate and shows each literal position is u-sensitive; the upper bound certifies a u-output by revealing a prime implicant and a prime implicate that share a variable, and certifies 0/1 outputs by revealing an implicant or implicate. No parameter is calibrated to a target, and no quantity is defined in terms of the result it is used to prove. The relationship Du(f) = O(ccu(f) bsu(f)) is established by Algorithm 1 and Lemma 3.5 through a disjoint-sensitive-blocks argument, and the randomized and quantum lower bounds bsu(f) = O(Ru(f)) and bsu(f) = O(Qu(f)^2) use Yao's minimax principle and Ambainis's adversary method, both standard external theorems. The subsequent Du(f) = O(Ru(f)^2) and Du(f) = O(Qu(f)^4) are direct substitutions of these independent bounds into Theorem 3.6/3.1, not a renaming of fitted values. Self-citations to [IKL+19], [IKS23], and [Juk21] appear only as background for hazard-free circuits and Kleene logic, and the definitions and theorems of this paper do not rest on those works; [Weg85] is used only to name the mMUX function. The one notable weakness is Theorem 3.7's assertion, without proof, that a u-input with more than one u has a more certain extension y with exactly one u and ef(y)=u. This is a genuine but non-circular gap: it is a combinatorial claim about resolution subcubes and, as the paper's own structure shows, it feeds only the improved sensitivity estimates (Lemma 3.8, Theorem 3.9, Appendix B), not the central linear-equivalence or Du=O(Ru^2), Du=O(Qu^4) results. Absence of a proof of that claim is a correctness/rigor concern, not circularity. Accordingly, no circular step can be quoted or exhibited, and the honest finding is score 0.

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

The paper introduces new complexity measures for hazard-free extensions, but these are mathematical definitions, not unexplained entities. The proofs rely on standard combinatorics and cited theorems; no free parameters are fitted to data and no ad hoc postulates are introduced.

assumptions (4)
  • standard math Every prime implicant and prime implicate of a Boolean function share at least one variable.
    Used in the proof of Theorem 3.1 to bound u-certificate complexity by k1+k2-1 for inputs with ef(x)=u.
  • standard math A non-constant Boolean function on a subcube contains two adjacent vertices with different values (a sensitive edge).
    Implied but never stated in Theorem 3.7's claim that a u-input with multiple u's has a one-u extension that still evaluates to u.
  • standard math Yao's minimax principle and Ambainis's adversary method apply to the three-valued query model.
    Used in Lemma 4.3 to lower bound randomized and quantum u-query complexity in terms of u-block sensitivity.
  • domain assumption The K3 truth tables define the hazard-free extension semantics, and the query oracle returns 0, 1, or u truthfully.
    The model assumes queries to input bits can return the unknown value u and that the function computed is the hazard-free extension ef.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sensitivity and Query Complexity under Uncertainty." pith.science (2026). https://pith.science/paper/CIJT3HXO

@misc{pith2026250700148,
  author       = {Pith},
  title        = {Pith review of: Sensitivity and Query Complexity under Uncertainty},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CIJT3HXO}},
  note         = {Machine review of arXiv:2507.00148}
}
read the original abstract

In this paper, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where inputs are allowed to be unknown. We allow each query to produce three results: zero, one, or unknown. The output could also be: zero, one, or unknown, with the constraint that we should output ''unknown'' only when we cannot determine the answer from the revealed input bits. Such an extension of a Boolean function is called its hazard-free extension. - We prove an analogue of Huang's celebrated sensitivity theorem [Annals of Mathematics, 2019] in our model of query complexity with uncertainty. - We show that the deterministic query complexity of the hazard-free extension of a Boolean function is at most quadratic in its randomized query complexity and quartic in its quantum query complexity, improving upon the best-known bounds in the Boolean world. - We exhibit an exponential gap between the smallest depth (size) of decision trees computing a Boolean function, and those computing its hazard-free extension. - We present general methods to convert decision trees for Boolean functions to those for their hazard-free counterparts, and show optimality of this construction. We also parameterize this result by the maximum number of unknown values in the input. - We show lower bounds on size complexity of decision trees for hazard-free extensions of Boolean functions in terms of the number of prime implicants and prime implicates of the underlying Boolean function.

Figures

Figures reproduced from arXiv: 2507.00148 by the authors.

Figure 1
Figure 1. Hazard-free decision tree for fn s0 y() Tn−1 T ′ n−1 0 y() T ′′ n−1 u T ′ n−1 y() 1 T ′′ n−1 Tn−1 we query x. If x = 0, then xz = 0 and the answer can be determined by only querying y. If x = 1, then x + y = 1 and the answer can be determined by only querying z. If x = u, then we can immediately answer u since x + y can only be u or 1 and xz can only be u or 0. The proof for the inductive case is similar to the base… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 21 canonical work pages

  1. [1]

    Degree vs

    Scott Aaronson, Shalev Ben - David, Robin Kothari, Shravas Rao, and Avishay Tal. Degree vs. approximate degree and quantum implications of huang's sensitivity theorem. In Proceedings of 53rd Annual Symposium on Theory of Computing (STOC 2021) , pages 1330--1342, 2021

    work page 2021

  2. [2]

    Quantum Lower Bounds by Quantum Arguments

    Andris Ambainis. Quantum Lower Bounds by Quantum Arguments . J. Comput. Syst. Sci. , 64(4):750--767, 2002

    work page 2002

  3. [3]

    Quantum Lower Bounds by Polynomials

    Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum Lower Bounds by Polynomials . J. ACM , 48(4):778--797, 2001

    work page 2001

  4. [4]

    Complexity measures and decision tree complexity: a survey

    Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. , 288(1):21--43, 2002

    2002

  5. [5]

    Bounds on the time for parallel RAM 's to compute simple functions

    Stephen Cook and Cynthia Dwork. Bounds on the time for parallel RAM 's to compute simple functions . In Proceedings of the 14th Annual Symposium on Theory of Computing (STOC 1982) , page 231–233, 1982

    work page 1982

  6. [6]

    Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

    Stephen Cook, Cynthia Dwork, and R\" u diger Reischuk. Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes . SIAM Journal on Computing , 15(1):87--97, 1986

    work page 1986

  7. [7]

    Learning Decision Trees from Random Examples

    Andrzej Ehrenfeucht and David Haussler. Learning Decision Trees from Random Examples . Inf. Comput. , 82(3):231--246, 1989

    work page 1989

  8. [8]

    Parallelism in Random Access Machines

    Steven Fortune and James Wyllie. Parallelism in Random Access Machines . In Proceedings of the 10th Annual Symposium on Theory of Computing (STOC 1978) , page 114–118, 1978

    work page 1978

Show all 22 references
  1. [9]

    Servedio, Kunal Talwar, and Avi Wigderson

    Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, and Avi Wigderson. Smooth Boolean Functions Are Easy: Efficient Algorithms for Low-Sensitivity Functions . In Proceedings of the Conference on Innovations in Theoretical Computer Science (ITCS 2016) , page 59–70, 2016

    2016

  2. [10]

    A fast quantum mechanical algorithm for database search

    Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual Symposium on Theory of Computing (STOC 1996) , pages 212--219, 1996

    1996

  3. [11]

    Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

    Hao Huang. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture . Annals of Mathematics , 190(3):949 -- 955, 2019

    2019

  4. [12]

    On the Complexity of Hazard-free Circuits

    Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah. On the Complexity of Hazard-free Circuits . Journal of the ACM (JACM) , 66(4):1--20, 2019

    2019

  5. [13]

    Karchmer-Wigderson Games for Hazard-Free Computation

    Christian Ikenmeyer, Balagopal Komarath, and Nitin Saurabh. Karchmer-Wigderson Games for Hazard-Free Computation . In Proceedins of 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , volume 251, pages 74:1--74:25, 2023

    2023

  6. [14]

    Notes on Hazard-Free Circuits

    Stasys Jukna. Notes on Hazard-Free Circuits . SIAM J. Discret. Math. , 35(2):770--787, 2021

    2021

  7. [15]

    Introduction to Metamathematics

    Stephen Cole Kleene. Introduction to Metamathematics . P. Noordhoff N.V., Groningen, 1952

    1952

  8. [16]

    Logical Approaches to Incomplete Information: A Survey

    Ron van der Meyden. Logical Approaches to Incomplete Information: A Survey . In Logics for Databases and Information Systems , pages 307--356. Kluwer, 1998

    1998

  9. [17]

    CREW PRAMs and Decision Trees

    Noam Nisan. CREW PRAMs and Decision Trees . SIAM J. Comput. , 20(6):999--1007, 1991

    1991

  10. [18]

    On the Degree of Boolean Functions as Real Polynomials

    Noam Nisan and Mario Szegedy. On the Degree of Boolean Functions as Real Polynomials . Comput. Complex. , 4:301--313, 1994

    1994

  11. [19]

    Sensitivity vs

    David Rubinstein. Sensitivity vs. Block Sensitivity of Boolean functions . Combinatorica , 15(2):297--299, 1995

    1995

  12. [20]

    Understanding Machine Learning - From Theory to Algorithms

    Shai Shalev - Shwartz and Shai Ben - David. Understanding Machine Learning - From Theory to Algorithms . Cambridge University Press, 2014

    2014

  13. [21]

    The Critical Complexity of All (Monotone) Boolean Functions and Monotone Graph Properties

    Ingo Wegener. The Critical Complexity of All (Monotone) Boolean Functions and Monotone Graph Properties . Inf. Control. , 67(1-3):212--222, 1985

    1985

  14. [22]

    Probabilistic computations: Toward a unified measure of complexity

    Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity . In 18th Annual Symposium on Foundations of Computer Science ( SFCS 1977) , pages 222--227. IEEE Computer Society, 1977

    1977

Pith tools

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