What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Questions tagged [query-complexity]

The tag has no usage guidance.

46 questions
Filter by
Sorted by
Tagged with
479 views

### Natural, untestable graph properties

In graph property testing, an algorithm queries a target graph for the presence or absence of edges and needs to determine whether the target either has a certain property or is $\epsilon$-far from ...
767 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 ...
360 views

### Models of computation strictly between classical and quantum in terms of query complexity

It is well known quantum computers are strictly more powerful than their classical counterparts in terms of query complexity. Are there other models (natural or artificial) that are strictly ...
478 views

### Reconstructing a tree from separator queries

Suppose $T$ is an constant-degree tree whose structure we do not know. The problem is to output the tree $T$ by asking queries of the form: "Does the node $x$ lie on the path from node $a$ to node $b$?...
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 ...
483 views

### Using the extra power of the negative adversary method

The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that ...
422 views

### Information complexity of query algorithms?

Information complexity has been a very useful tool in communication complexity, mainly used to lower bound the communication complexity of distributed problems. Is there an analogue of information ...
799 views

### Las Vegas vs Monte Carlo randomized decision tree complexity

Background: Decision tree complexity or query complexity is a simple model of computation defined as follows. Let $f:\{0,1\}^n\to \{0,1\}$ be a Boolean function. The deterministic query complexity of ...
268 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 ...
422 views

### How can one find the “hard” probability distribution on the input for recursive boolean functions?

Update: Since, it seems there is no progress regarding this question, any idea, conjecture, hunch, or advice is welcome. For example, are there any partial or incomplete results? What are the main ...
399 views

### Can quantum algorithms with exponential speed-up be rederived using span-programs?

The general adversary lower-bound is now known to characterize quantum query complexity due to breakthrough work by Reichardt et al. The same line of work also establishes connections to the span ...
539 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 ...
672 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, ...
450 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 (...
665 views

### Lower bounds on the Threshold function

In decision tree complexity of a boolean function, a very well know lower bound method is to find a (approximate) polynomial that represents the function. Paturi gave a characterization for symmetric ...
357 views

### Finding out a set by intersection comparison

The following problem recently emerged from my research and I would like to ask if anyone knows if this problem was considered before or has heard of anything that might be related. The general ...
191 views

193 views

78 views

### Agnostic query learning for DFAs

Angluin's membership+equivalence query algorithm allows to efficiently and exactly learn a target $n$-state DFA. But what if the target DFA is huge, or the target concept is not even a regular ...
124 views

### Approximation class of finding decision trees with minimal depth

We are given some sets $S_1, \cdots , S_n$ and two disjoint sets $A$ and $B$. A decision tree is a binary tree where each node asks "$x \in S_i?$" for some $i$, taking the left branch means "yes", ...