Questions tagged [query-complexity]

The tag has no usage guidance.

13 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
13
votes
0answers
421 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 ...
7
votes
0answers
145 views

Range min-gap query

The min-gap of an array $A[1..n]$ of $n \ge 2$ elements is defined as $\min_{1 \le i < j \le n}{|A_i - A_j|}$. Now, I am considering a query version of it. Given $A$, a query receives two integers $...
7
votes
0answers
193 views

Are the minimal quantum and classical span programs the same?

A span program is a linear-algebraic way of specifying a boolean function introduced here which has found recent application in quantum query complexity. A span program for a function $f: \{0,1\}^n \...
5
votes
0answers
96 views

Improve analysis of quantum random walk

The paper Quantum Complexity of Testing Group Commutativity considers the problem of identifying if a given group is commutative. The group is given via a certain oracle and the complexity of the ...
3
votes
0answers
122 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", ...
3
votes
0answers
64 views

Estimate smooth vector, from dot-product queries

I have a secret $n$-dimensional vector $\mathbb{s} \in \mathbb{Z}^n$. I don't know $\mathbb{s}$; my goal is to estimate $\mathbb{s}$. I do have an oracle for the function $f_\mathbb{s} : \mathbb{Z}^...
1
vote
0answers
55 views

Bipartite formula complexity lower bound

I'm trying to understand the paper The Bipartite Formula Complexity of Inner Product is Quadratic, by Avishay Tal. The argument is recapped here. I am having trouble understanding the proof Theorem 3 ...
1
vote
0answers
68 views

Query complexity of quantum search with measuring oracle

Consider the following problem: Let $x\in X$ be a uniformly random value. Let $O$ be an oracle that measures whether the register $Q$ contains $x$. More precisely, $O$ measures $Q$ using the ...
1
vote
0answers
141 views

Boolean functions with high query complexity for PAC learning

The most general theorem for PAC learning of Boolean functions that I am aware of is the theorem in section 3.4 of Ryan O'Donnel's book where its basically shown that Boolean functions whose Fourier ...
1
vote
0answers
148 views

Is there a lower bound for the decisional Grover search problem?

What is known about the decisional version of the search problem? By decisional version of the search problem, I mean the problem in which you wish to determine whether there are $0$, or exactly $t$ ...
1
vote
0answers
357 views

Discovering a graph with minimal oracle queries

I have a transitive DAG G which is a subgraph of an unknown DAG R. (The nodes are the same in G and R, but R may have edges not in G.) I can determine the presence of a given edge in R by an oracle ...
0
votes
0answers
47 views

Query complexity for functions $f\colon\left\{0,1\right\}^n\to\left\{0,1\right\}^m$

I'm studying query complexity and I'm trying to understand Bernstein-Vazirani's problem (https://en.wikipedia.org/wiki/Bernstein%E2%80%93Vazirani_algorithm) and Simon's problem (https://en.wikipedia....
0
votes
0answers
28 views

Connectivity with ordered adjacency list

In the adjacency list model, a graph is described through lists that contain the neighbors of any node $i \in [n]$. A query is of the form "What is the $k$-th neighbor of node $i$?". BFS allows to ...