Sensitivity and Query Complexity under Uncertainty

Deepu Benson, Balagopal Komarath, Nikhil Mande, Sai Soumya Nalli, Jayalal Sarma, Karteek Sreenivasaiah · 2025

Read Sensitivity and Query Complexity under Uncertainty by Deepu Benson, Balagopal Komarath, Nikhil Mande, Sai Soumya Nalli, Jayalal Sarma, Karteek Sreenivasaiah (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-00148.txt.

Introduction

Deepu Benson and five co-authors study how hard Boolean functions get when inputs may be unknown. Each query can answer zero, one, or unknown, and the output may be unknown only when the revealed bits cannot settle it. That hazard-free extension mirrors parallel hardware that must not guess. The team proves an analogue of Huang's sensitivity theorem inside this model.

Deterministic query cost of the extension is at most quadratic in its randomized cost and quartic in its quantum cost, beating the best bounds for plain Boolean functions. An exponential gap in decision tree size also appears. General conversion methods from plain trees to hazard-free ones are shown optimal.

Catalog record

CREATORDeepu Benson, Balagopal Komarath, Nikhil Mande, Sai Soumya Nalli, Jayalal Sarma, Karteek Sreenivasaiah
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-00148

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sensitivity and Query Complexity under Uncertainty Deepu Benson, Balagopal Komarath, Nikhil Mande, Sai Soumya Nalli, Jayalal Sarma, Karteek Sreenivasaiah 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. 1 Introduction A single-tape Turing Machine needs at least n steps in the worst case to compute any n -bit function that depends on all of its inputs. One way to achieve faster computation is to use multiple processors in parallel. Parallel computation is modeled using Parallel Random Access Machines (PRAM), originally defined by Fortune and Wyllie [ FW78 ] , in which there are multiple processors and multiple memory cells shared among all processors. In a single time step, each processor can read a fixed number of memory cells, execute one instruction, and write to a fixed number of memory cells. In the real world, access to shared memory has to be mediated using some mechanism to avoid read-write conflicts. A popular mechanism to achieve this is called Concurrent-Read Exclusive-Write (CREW) in which concurrent reads of the same memory cell are allowed, but each cell can only be written to by at most one processor in a single time step. An algorithm that violates this restriction is invalid. A fundamental problem in such a model of computation is to determine the number of processors and the amount of time required for computing Boolean functions. A Boolean function f:\{0,1\}^{n}\mapsto\{0,1\} is predetermined 1 1 1 The number of input bits is fixed, making this model non-uniform. and the input bits are presented in shared memory locations. The processors have to write the output bit f(x) to a designated shared memory location. For example, consider the Boolean disjunction (logical OR) of all input bits which outputs 1 if and only if there is at least one 1 among the inputs. There is a simple divide-and-conquer algorithm to compute the OR of n input bits in O(\log n) time using n processors that exploits the fact that OR is associative and distributive. This is essentially a CREW-PRAM algorithm to compute the OR of n bits in O(\log(n)) -time. Note that each of the processors in the above algorithm computes a trivial function at each step namely the OR of two bits. Can we do better if we are allowed to use more complex computations at each step? Cook and Dwork [ CD82 ] , and Cook, Dwork, and Reischuk [ CDR86 ] answer this question by showing that any CREW-PRAM algorithm that computes the logical OR of n bits needs \Omega(\log(n)) -time, irrespective of the functions computed by the processors at each step. The reason their lower bound is independent of the functions allowed at each processor is because their lower bound really applies to the number accesses made to the shared memory. If we only care about analyzing the number of memory accesses by an algorithm running on an all-powerful processor, a neat way to think of the computation at each processor is to model it as a two-player interactive game: a querier who is all-powerful and an oracle . They want to compute a Boolean function f:\{0,1\}^{n}\to\{0,1\} known beforehand, on an input x\in\{0,1\}^{n} . However, the input x is only known to the oracle. The only interaction allowed is where the querier asks a query i\in[n] , and the oracle can reply with x_{i} . The query complexity of f is defined as the the maximum number of queries required to find the answer, where the maximum is taken over all x . The querier’s aim is to minimize the number of queries required to determine the value of the function in the worst-case. This is exactly the computation model studied in an exciting area of computer science simply called ‘query complexity’. The technique used in [ CD82 ] and [ CDR86 ] involves defining a measure that is equivalent to what is now commonly known as sensitivity of a Boolean function, denoted \mathsf{s}(f) . More precisely, they show that the time needed by CREW-PRAM algorithms, irrespective of the instruction set, to compute a Boolean function is asymptotically lower bounded by the logarithm of the sensitivity of the function. The question whether a function can be computed in time at most the logarithm of the function’s sensitivity, thereby characterizing the CREW-PRAM time complexity in terms of sensitivity, remained open. Nisan [ Nis91 ] introduced a generalization of sensitivity called block-sensitivity , denoted \mathsf{bs}(f) , which is lower bounded by sensitivity, and proved that CREW-PRAM time complexity is asymptotically the same as the logarithm of the block sensitivity of a function. Nisan further related decision tree depth complexity , denoted 0pt(f) to block-sensitivity providing another characterization for CREW-PRAM time complexity as the logarithm of decision tree depth. However, the block-sensitivity of a function can be potentially much higher than its sensitivity, as shown by Rubinstein [ Rub95 ] with an explicit function that witnesses a quadratic gap between these two measures. After research spanning almost three decades which saw extensive study of relationships between the above parameters and various other parameters (see, for example, [ ABK+21 ] and the references therein), such as certificate complexity (denoted \mathsf{cc}(f) ) and degree (denoted \mathsf{deg}(f) ), Huang [ Hua19 ] , in a breakthrough result, proved that sensitivity and block-sensitivity are polynomially related. This is the celebrated sensitivity theorem: Theorem 1.1 (Sensitivity theorem for Boolean functions [ Hua19 ] ) . For all Boolean functions f:\{0,1\}^{n}\to\{0,1\} , \mathsf{bs}(f)=O(\mathsf{s}(f)^{4}) . By earlier results [ Nis91 , NS94 , BBC+01 ] , Huang’s result implies that the combinatorial and analytic measures of sensitivity, block sensitivity, certificate complexity, degree, approximate degree, deterministic/randomized/quantum query complexity are all polynomially equivalent for Boolean functions. This strong connection makes the study of query complexity essentially equivalent to studying the time complexity of CREW-PRAMs. Thus henceforth, we shall

Read the complete text