Questions tagged [query-complexity]
The query-complexity tag has no usage guidance.
7
questions
17
votes
1answer
2k views
Algorithm for optimizing decision trees
Background
A binary decision tree $T$ is a rooted tree where each internal node (and root) is labeled by an index $j \in \{1,..., n\}$ such that no path from root to leaf repeats an index, the leafs ...
18
votes
3answers
810 views
Trade off between time and query complexity
Working directly with time complexity or circuit lower bounds is scary. Hence, we develop tools like query complexity (or decision-tree complexity) to get a handle on lower bounds. Since each query ...
10
votes
4answers
680 views
Bounding the gap between quantum and deterministic query complexity
Although exponential separations between bounded-error quantum query complexity ($Q(f)$) and deterministic query complexity ($D(f)$) or bounded-error randomized query complexity ($R(f)$) are known, ...
11
votes
1answer
553 views
Lower bounds for learning in the membership query and counterexample model
Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a ...
10
votes
1answer
451 views
Span programs, witness size, and certificate complexity
A span program is a linear-algebraic way of specifying a boolean function introduced here. Recently, this model was used to show that the negative adversary method provides a tight characterization (...
13
votes
1answer
269 views
Are there distribution properties which are “maximally” hard to test?
A distribution testing algorithm for a distribution property P (which is just some subset of all distributions over [n]) is allowed access to samples according to some distribution D, and is required ...
7
votes
2answers
469 views
Quantum query complexity and certificate complexity
A certificate for an input $x$ is a subset of bits $S \subseteq \{1,...,n\}$ such that for all inputs $y$, $(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$. Then $C_x(f)$ is the minimum ...
