Sensitivity and Query Complexity Under Uncertainty

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 [10], 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 pre-determined¹¹1The 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 [7], and Cook, Dwork, and Reischuk [8] answer this question by showing that any CREW-PRAM algorithm that computes the logical OR of $n$-bits needs $\mathrm{\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 [7] and [8] involves defining a measure that is equivalent to what is now commonly known as sensitivity of a Boolean function, denoted $𝗌(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 [20] introduced a generalization of sensitivity called block-sensitivity, denoted $\mathrm{𝖻𝗌}(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 [22] 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, [1] and the references therein), such as certificate complexity (denoted $\mathrm{𝖼𝖼}(f)$) and degree (denoted $\mathrm{𝖽𝖾𝗀}(f)$), Huang [13], in a breakthrough result, proved that sensitivity and block-sensitivity are polynomially related. This is the celebrated sensitivity theorem:

By earlier results [20, 21, 3], Huang’s result implies that the 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 predominantly use terminology from query complexity, and also express our results in the context of query complexity.

In this work, we initiate a systematic study to understand the effect of allowing uncertainty among the inputs in the setting of CREW-PRAM. Allowing uncertainty in this setting is easier to understand in the equivalent query model: When an input bit is queried by the querier, the oracle can reply with “uncertain”. If it is possible for the function value to be determined in the presence of such uncertainties, then we would like the querier to output such a value. In what follows, we make the setting more formal.

To model uncertainty we use a classic three-valued logic, namely Kleene’s strong logic of indeterminacy [17], usually denoted K3. The logic K3 has three truth values $0$, $1$, and $𝗎$. The behaviour of the third value $𝗎$ with respect to the basic Boolean primitives – conjunction ($\wedge$), disjunction ($\vee$), and negation ($\neg$) – are given in Table 1.

The logic K3 has been used in several other contexts where there is a need to represent and work with unknowns and hence has found several important wide-ranging applications in computer science. For instance, in relational database theory, SQL implements K3 and uses $𝗎$ to represent a NULL value [19]. Perhaps the oldest use of K3 is in modeling hazards that occur in real-world combinational circuits. Recently there have been a series of results studying constructions and complexity of hazard-free circuits [14, 15, 16]. Here $𝗎$ was used to represent metastability, or an unstable voltage, that can resolve to $0$ or $1$ at a later time.

One way to interpret the basic binary operations $\vee$, $\wedge$, and $\neg$ in K3 is as follows: for a bit $b\in \{0,1\}$, if the value of the function is guaranteed to be $b$ regardless of all $\{0,1\}$-settings to the $𝗎$-variables, then the output is $b$. Otherwise, the output is $𝗎$. This interpretation generalizes in a nice way to $n$-variate Boolean functions. In literature, this extension is typically called the hazard-free extension of $f$ (see, for instance, [14]), and is an important concept studied in circuits and switching network theory since the 1950s. The interested reader can refer to [14], and the references therein, for history and applications of this particular way of extending $f$ to K3. We define this extension formally below.

For a string $x\in {\{0,𝗎,1\}}^n$, define the resolutions of $x$ as follows:

That is, $\mathrm{𝖱𝖾𝗌}(x)$ denotes the set of all strings in ${\{0,1\}}^n$ that are consistent with the $\{0,1\}$-valued bits of $x$. The hazard-free extension of a Boolean function is defined as follows:

To understand the motivation behind this definition, consider the instability partial order defined on $\{0,𝗎,1\}$ by the relations $𝗎\le 0$ and $𝗎\le 1$. The elements $0$ and $1$ are incomparable. This partial order captures the intuition that $𝗎$ is less certain than $0$ and $1$. This partial order can be extended naturally to elements of ${\{0,𝗎,1\}}^n$ as $x\le y$ iff $x_i\le y_i$ for all $1\le i\le n$. A function $f^{\prime }:{\{0,𝗎,1\}}^n\to \{0,𝗎,1\}$ is natural if for all $x,y\in {\{0,𝗎,1\}}^n$ such that $x\le y$, we have $f^{\prime }(x)\le f^{\prime }(y)$ and $f^{\prime }(z)\in \{0,1\}$ when $z\in {\{0,1\}}^n$. Intuitively, this property says that the function cannot produce a less certain output on a more certain input and if there is no uncertainty in the input, there should be no uncertainty in the output. A natural function $f^{\prime }$ extends a Boolean function $f$ if $f^{\prime }(x)=f(x)$ for all $x\in {\{0,1\}}^n$. There could be many natural functions that extend a Boolean function. Consider two natural functions $f^{\prime }$ and $f^{\prime \prime }$ that extend $f$. We say $f^{\prime }\le f^{\prime \prime }$ if $f^{\prime }(x)\le f^{\prime \prime }(x)$ for all $x\in {\{0,𝗎,1\}}^n$. This says that the output of $f^{\prime \prime }$ is at least as certain as the output of $f^{\prime }$. An alternative definition for the hazard-free extension of a function $f$ is as follows: it is the unique function $\tilde{f}$ such that $f^{\prime }\le \tilde{f}$ for all natural functions $f^{\prime }$ that extends $f$. That is, the hazard-free extension of a Boolean function is the best we could hope to compute in the presence of uncertainties in the inputs to $f$.

We note here that even though we use the term “hazard-free”, there is a fundamental difference between our model of computation and the ones studied in results such as [14, 15, 16]. For hazard-free circuits, the value $𝗎$ represents an unstable voltage, and the gates in a circuit are fundamentally unable to detect it. That is, there is no circuit that can output $1$ when input is $𝗎$ and $0$ otherwise. However, in our setting, the value $𝗎$ is simply another symbol just like $0$ or $1$. So we can indeed detect/read a $𝗎$ value. The restriction that we have to compute the hazard-free extension is a semantic one in this paper, whereas Boolean circuits can only compute natural functions. In other words, we are interested in query complexity of hazard-free extensions of Boolean functions per se, and we have no notion of metastability in our computation model.

There is a rich body of work on the query complexity of Boolean functions that has established best-possible polynomial relationships among various models such as deterministic, randomized, and quantum models of query complexity, and their interplay with analytical measures such as block sensitivity and certificate complexity (see, for example, [1] and the references therein). We study these relationships in the presence of uncertainty, in particular for hazard-free extensions of Boolean functions. A main goal is to characterize query complexity (equivalently CREW-PRAM time complexity) of hazard-free extensions of Boolean functions using these parameters.

For $b\in \{0,1\}$, we use ${\mathrm{𝖻𝗌}}_{𝗎,b}(f)$ to denote the maximum $𝗎$-block sensitivity of $f$ at $x$, over all $x\in f^{-1}(b)$. For a string $x\in {\{0,𝗎,1\}}^n$ and a set $B\subseteq [n]$ that is a sensitive block of $\tilde{f}$ at $x$, we abuse notation and use $x^B$ to denote an arbitrary but fixed string $y\in {\{0,𝗎,1\}}^n$ that satisfies $y_{[n]\setminus B}=x_{[n]\setminus B}$ and $\tilde{f}(y)\ne \tilde{f}(x)$.

We now formally define certificate complexity for hazard-free extensions of Boolean functions. We first define a partial assignment as follows: By a partial assignment on $n$ bits, we mean a string $p\in {\{0,1,𝗎,\ast \}}^n$, representing partial knowledge of a string in ${\{0,𝗎,1\}}^n$, where the $\ast$-entries are yet to be determined. We say a string $y\in {\{0,𝗎,1\}}^n$ is consistent with a partial assignment $p\in {\{0,1,𝗎,\ast \}}^n$ if $y_i=p_i$ for all $i\in [n]$ with $p_i\ne \ast$.

In other words, a certificate for $\tilde{f}$ at $x$ is a set of variables of $x$ that if revealed, guarantees the output of all consistent strings with the revealed variables to be equal to $\tilde{f}(x)$.

We refer the reader to [6] for basics of quantum query complexity.

We first show that sensitivity, block sensitivity, certificate complexity, and size of the largest prime implicant/prime implicate are all asymptotically the same. This is a more formal and more precise restatement of Theorem 3.

We start by proving that for monotone functions, the presence of uncertainty does not make computation significantly harder. Similar relationships are known for monotone combinational circuits w.r.t. containing metastability [14].

We show that despite requiring exponentially more depth in the presence of uncertainty, we can compute the function ${\mathrm{𝖬𝖴𝖷}}_n$ using a decision tree that is only quadratically larger in size than the Boolean one (Theorem 8).

However, there are functions that require exponentially larger decision tree size in the presence of uncertainty such as the $\mathrm{𝖠𝖭𝖣}$ function (Theorem 9). We defer the proofs of these statements to the full version [4]. The size lower bound technique used here for both the functions involves constructing a set of inputs that must all lead to different leaves and hence any decision tree that computes the hazard-free extension correctly requires size at least as large as the size of this input set. The upper bound is shown by an explicit construction.

We present a general construction of decision trees of hazard-free extensions of functions from a decision tree of the underlying Boolean function (Theorem 10) in the full version [4] of this paper. The main idea is to construct the $𝗎$ subtree of the root node in the new decision tree from the $0$ and $1$ subtrees that have been constructed recursively. The $𝗎$ subtree construction can be viewed as a product construction where we replace each leaf in a copy of the $0$ subtree with a modified copy of the $1$ subtree. This product construction works because for every input that reaches the $𝗎$ subtree, the output value can determined by the output values when that bit is $0$ and when it is $1$, which is exactly what the $0$ and $1$ subtrees compute.

We also prove in Theorem 12 that the complexity increases only gradually along with the increase in the amount of uncertainty in the inputs. More specifically, we prove that if the inputs are guaranteed to have at most $k$ bits with value $𝗎$, without any guarantee on where they occur, the exponential blow-up in query complexity is contained to the parameter $k$ (See full version [4] for a proof). This proof also makes use of the product construction mentioned above.

In this paper we initiated a study of query complexity of Boolean functions in the presence of uncertainty, by considering a natural generalization of Kleene’s strong logic of indeterminacy on three variables.

We showed that an analogue of the celebrated sensitivity theorem [13] holds in the presence of uncertainty too. While Huang showed a fourth-power relationship between sensitivity and block sensitivity in the Boolean world, we were able to show these measures are linearly related in the presence of uncertainty. The proof of sensitivity theorem in our setting is considerably different and easier from the proof of sensitivity theorem in the Boolean world. We can parameterize $𝗎$-sensitivity and $𝗎$-query complexity by restricting our attention to inputs that have at most $k$ unstable bits. The setting $k=0$ gives us the Boolean sensitivity theorem and the setting $k=n$, our sensitivity theorem. Can we unify these two proofs using this parameterization? That is, is there a single proof for the sensitivity theorem that works for all $k$?

We showed using $𝗎$-analogues of block sensitivity, sensitivity, and certificate complexity that for all Boolean functions $f$, its deterministic, randomized, and quantum $𝗎$-query complexities are polynomially related to each other. An interesting research direction would be to determine the tightest possible separations between all of these measures. It is interesting to note that our quadratic relationship between deterministic and randomized $𝗎$-query complexity improves upon the best-known cubic relationship in the usual query models. Moreover, our quartic deterministic-quantum relationship matches the best-known relationship in the Boolean world [1]. More generally, it would be interesting to see best known relationships between combinatorial measures of Boolean functions in this model, and see how they compare to the usual query model (see, for instance, [1, Table 1]). A linear relationship between deterministic and randomized query complexities in the presence of uncertainty remains open, but a quadratic deterministic-quantum separation follows from Theorem 6 or from the OR function (via Grover’s search algorithm [12]).

While we studied an important extension of Boolean functions to a specific three-valued logic that has been extensively studied in various contexts, an interesting future direction is to consider query complexities of Boolean functions on other interesting logics. Our definition of $\tilde{f}$ dictates that $\tilde{f}(x)=b\in \{0,1\}$ iff $f(y)=b$ for all $y\in \mathrm{𝖱𝖾𝗌}(x)$, and $\tilde{f}(x)=𝗎$ otherwise. A natural variant is to define a 0-1 valued function that outputs $b\in \{0,1\}$ iff majority of $f(y)$ equals $b$ over all $y\in \mathrm{𝖱𝖾𝗌}(x)$. It is not hard to show that the complexity of this variant of ${\mathrm{𝖬𝖴𝖷}}_n$ is bounded from below by the usual query complexity of Majority on $2^n$ variables, which is $\mathrm{\Omega }(2^n)$ in the deterministic, randomized, and quantum query models.