In this chapter we investigate the complexity of C for various n and A. We consider not only the query complexity of C as defined in Chapter 3, i.e., the least m such that there exists a set X for which C ∈ FQ(m,X), but also the number of queries to A itself that are required to compute C . (Note that, numerically speaking, the former complexity cannot exceed the latter.)
In this chapter we investigate the complexity of C for various n and A. We consider not only the query complexity of C as defined in Chapter 3, i.e., the least m such that there exists a set X for which C ∈ FQ(m,X), but also the number of queries to A itself that are required to compute C . (Note that, numerically speaking, the former complexity cannot exceed the latter.)
We consider problems that can be solved by asking certain queries. The deterministic query complexity D(P,n) of a problem P is the smallest number of queries needed to ask in order to find the solution with an input of size n (in the worst case), while the non-deterministic query complexity D0(P,n) is the smallest number of queries needed to ask, in case we know the solution, to prove that it is indeed the solution (in the worst case). Equivalently, D(P,n) is the largest number of queries needed to find the solution in case an Adversary is answering the queries, while D0(P) is the largest number of queries needed to find the solution in case an Adversary chooses the input. We define a series of quantities between these two values, Dk(P,n) is the largest number of queries needed to find the solution in case an Adversary chooses the input, and answers the queries, but he can change the input at most k times. We give bounds on Dk(P,n) for various problems P.
In the query model of multi-variate function computation, the values of the variables are queried sequentially, in an order that may depend on previously revealed values, until the function's value can be determined. The function's computation query complexity is the lowest expected number of queries required by any query order. Instead of computation, it is often easier to consider verification, where the value of the function is given and the queries aim to verify it. The lowest expected number of queries necessary is the function's verification query complexity. We show that for all symmetric functions of independent binary random variables, the computation and verification complexities coincide. This provides a simple method for finding the query complexity and the optimal query order for computing many functions. We also show that if the symmetry condition is removed, there are functions whose verification complexity is strictly lower than their computation complexity, and mention that the same holds when the independence or binary conditions are removed.
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint k on an n-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected (1/2−ε)-approximation using only Oε(logn) queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above 1/4 requires Ω(n/logn) queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a (1−1/e−ε)-approximation using Oε(min{n,n/k}) queries. When k=o(n), our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when k=cn for any fixed rational c<1−1/e−ε, the query complexity reduces to Oε,c(logn), yielding an exponential separation from the classical Ω(n/logn) lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of exp(Ω(ε2n)) queries for achieving a ratio beyond 1/2+ε without constraints, and exp(Ω(ε2k)) queries for exceeding 1−1/e+ε when k/n≤ε. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.
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
This chapter focuses on query complexity, which measures the minimum number of input bits that need to be read to solve a problem, in other words, the minimum depth of any correct decision tree (or branching program). Techniques for upper and lower bounds for deterministic and randomized query complexities are covered. The close relationships between query complexity and other measures known as certificate complexity and sensitivity are also covered. The chapter concludes with techniques for proving lower bounds on the size (as opposed to depth) of decision trees and branching programs.