# Questions tagged [query-complexity]

The tag has no usage guidance.

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

0answers
97 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 ...
0answers
126 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", ...
0answers
66 views

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}^... 0answers 74 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 ... 0answers 43 views ### Non-rigid isomorphic structures In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ... 0answers 59 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 ... 0answers 145 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 ... 0answers 149 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$... 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 ... 0answers 53 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....