We initiate the study of a new model of query complexity of Boolean functions where, in addition to 0 and 1, the oracle can answer queries with unknown''. The query algorithm is expected to output the function value if it can be conclusively determined by the partial information gathered, and it must output unknown'' if not. We formalize this model by using Kleene's strong logic of indeterminacy on three variables to capture unknowns. We call this model the `u-query model'. We relate the query complexity of functions in the new u-query model with their analogs in the standard query model. We show an explicit function that is exponentially harder in the u-query model than in the usual query model. We give sufficient conditions for a function to have u-query complexity asymptotically the same as its query complexity. Using u-query analogs of the combinatorial measures of sensitivity, block sensitivity, and certificate complexity, we show that deterministic, randomized, and quantum u-query complexities of all total Boolean functions are polynomially related to each other, just as in the usual query models.
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.
In this thesis we study various models of query complexity. A query algorithm computes a function under the restriction that the input can be accessed only by making probes to the the bits of the input. The query complexity of a function f is the minimum number of probes made by any query algorithm that computes f. In this thesis, we consider three different models of query complexity, (1) deterministic decision tree complexity (query complexity when the underlying algorithm is deterministic), (2) approximate decision tree complexity aka. property testing (query complexity when the underlying algorithm is probabilistic and only expected to ”approximately ” compute f) and quantum query complexity (query complexity when the underlying algorithm is allowed to make quantum queries). The main results in this thesis are: • We study the relation between deterministic decision tree complexity and other combinatorial measures of complexity measures like sensitivity and block sensitivity. We prove that for minterm-transitive functions the sensitivity is quadratically related to block sensitivity which is polynomially
Certificate complexity
(C(f)) is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity
(D) and other query models such as bounded-error randomized and quantum complexity
(R,Q), but not as well for quantum zero-error
(Q0) and exact query complexity
(QE), where there is no agreed-upon certificate 'object' (even for
Q). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of
C,RC (randomized certificate complexity) and
QC (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on
QE and
Q0, the quantum analogues of
D and
R0, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for
Q0, but rational degree and
Q are asymptotically smaller.
We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.22 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a seemingly unrelated measure called one-sided unambiguous certificate complexity. We also show that one-sided unambiguous certificate complexity is lower-bounded by fractional block sensitivity, which means we cannot use these techniques to get a super-quadratic separation between block sensitivity and sensitivity. Along the way, we give a power 1.22 separation between certificate complexity and one-sided unambiguous certificate complexity, improving the power 1.128 separation due to Goos [FOCS 2015]. As a consequence, we obtain an improved lower-bound on the co-nondeterministic communication complexity of the Clique vs. Independent Set problem.
Computational models typically assume that operations are applied in a fixed sequential order.In recent years several works have looked at relaxing this assumption, considering computations without any fixed causal structure and showing that such "causally indefinite" computations can provide advantages in various tasks.Recently, the quantum query complexity of Boolean functions has been used as a tool to probe their computational power in a standard complexity theoretic framework, but no separation in exact query complexity has thus-far been found.In this paper, we investigate this problem starting with the simpler and fully classical notion of deterministic query complexity of Boolean functions, and using classical-deterministic processes -which may exhibit causal indefiniteness -as a generalised computational framework.We first show that the standard polynomial and certificate lower bounds of deterministic query complexity also hold in such generalised models.Then, we formulate a Boolean function for which causal indefiniteness permits a reduction in query complexity and show that this advantage can be amplified into a polynomial separation.Finally, with the insights gained in the classical-deterministic setting, we give a Boolean function whose quantum query complexity is reduced by causally indefinite computations.
We study the query complexity of computing a function f:{0,1}^n-->R_+ in expectation. This requires the algorithm on input x to output a nonnegative random variable whose expectation equals f(x), using as few queries to the input x as possible. We exactly characterize both the randomized and the quantum query complexity by two polynomial degrees, the nonnegative literal degree and the sum-of-squares degree, respectively. We observe that the quantum complexity can be unboundedly smaller than the classical complexity for some functions, but can be at most polynomially smaller for functions with range {0,1}. These query complexities relate to (and are motivated by) the extension complexity of polytopes. The linear extension complexity of a polytope is characterized by the randomized communication complexity of computing its slack matrix in expectation, and the semidefinite (psd) extension complexity is characterized by the analogous quantum model. Since query complexity can be used to upper bound communication complexity of related functions, we can derive some upper bounds on psd extension complexity by constructing efficient quantum query algorithms. As an example we give an exponentially-close entrywise approximation of the slack matrix of the perfect matching polytope with psd-rank only 2^{n^{1/2+epsilon}}. Finally, we show there is a precise sense in which randomized/quantum query complexity in expectation corresponds to the Sherali-Adams and Lasserre hierarchies, respectively.