8
I guess there are at least 3 questions in your question. I don't have a satisfactory answer to all of them, so this isn't a complete answer. Hopefully there will be more answers that answer all your questions.
The question in the title: Can quantum algorithms with exponential speed-up be rederived using span-programs?
As you noted, the general adversary ...
7
This question has been resolved!
A few days ago Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs uploaded a preprint showing the existence of a total function $f$ which satisfies
$R_0(f) = \tilde{\Omega}(R_2(f)^{2})$
and even
$R_0(f) = \tilde{\Omega}(R_1(f)^{2})$,
where $R_1(f)$ denotes 1-sided ...
7
As far as I know, this is still open. A very recent paper that mentions these quantities and some bounds is Aaronson et al: Weak parity (see http://arxiv.org/abs/1312.0036). You can also see chapter 14 of Jukna: Boolean funcions and the 1999 (still beats 1998!) survey by Buhrman and de Wolf. Another very recent paper about randomized decision tree complexity ...
6
For total functions it is impossible to achieve more than a polynomial separation (i.e. $D(f) = O(Q^6(f))$) in the quantum query model, for more info see this cstheory blog post. With promise problems, you can have exponential seperations between the quantum and classical query complexity. However, classical query complexity is sometimes very deceptive in ...
5
This is an answer to the last question: MA in the query complexity model.
It isn't always possible to make the prover do all the work (or even any work at all). The reason is that an MA-prover is trying to convince you that the answer is YES. But the problem can be chosen so that in the YES case, there's nothing interesting that the prover can tell you. ...
5
I wasn't sure what you were asking in Rev 1 of the question, but in Rev 4 you've added a more precise question that I can answer:
Can I get quadratic speed-up e.g. for finding a satisfying assignment to some quantified formular $\forall x \exists y\; \varphi(x,y)$?
Before that question can be answered, we have to make the model precise. We can think of ...
5
Sorry for unearthing this post -- it is quite old, but I figured having it answered may not be that bad an idea.
First, it looks like you performed your Chernoff bound with some slightly odd setting of parameters. Note that to perform your suggested "testing by learning" approach, it is sufficient to learn the distribution in total variation distance (or $\...
5
Anindya Sen and I have a paper in ALT '13 where we give an $\tilde O(n \sqrt{n})$ algorithm for this problem. We don't know if a better algorithm is possible.
5
Yes, information theory is useful for proving lower bounds on the query complexity of problems in Computer Science.
Alexander Golynski gave a good example in his ground breaking paper titled "Cell probe lower bounds for succinct data structures", presented at SODA 2009. He uses information theory to prove a lower bound on query complexity, which in turns ...
5
I sent an email to Péter Hajnal, and he kindly confirmed that the bound in the lemma should be $\Omega(\frac{\Delta_L(G)}{\lceil \delta_L(G) \rceil} n)$.
5
What you are saying is that given $N$ random samples one cannot simulate an algorithm that makes $T$ queries to VSTAT$(N)$. If the $T$ queries are chosen adaptively then one might need more samples (the best upper bound is $\sqrt{T} N$ samples).
This is true but not an issue for the planted clique paper you mentioned. That paper is concerned with proving a ...
4
Let me first clarify what the paper states: "Most algorithmic approaches used in practice and in theory on a wide variety of problems can be implemented using only access to such an [meaning SQ] oracle". So the question is not really whether MCMC "falls into the SQ framework" (the framework does not place any restrictions on computation) but whether the ...
4
This is a standard adversary argument, not very different from adversary arguments taught in undergraduate algorithms courses. If you are unfamiliar with such arguments, then you can check out these notes by Jeff Erickson.
The idea for the proof is that the SQ oracle is controlled by an adversary, and the adversary does not have to initially commit to a ...
4
Since the quantum query complexity typically denotes the bounded-error quantum query complexity, there's some ambiguity. A more precise question could be: "What is the quantum query complexity to decide nontrivial monotone graph properties with probability at least $2/3$?".
A natural example in this context is the monotone property of having a single edge. ...
4
Not a complete answer, but hopefully a good starting point. It is very instructive to (always!) first consider the discrete analog of your question. If $X$ is some set and $f:X\to\{0,1\}$, what is the minimal number of evaluation queries needed to uniquely identify $f$? As already noted in the OP, the question only makes sense if one fixes a function class $...
3
Chapters-3,4 in book Analysis of Boolean Functions by Ryan O'Donnell might be a good starting point.
3
If you want a conjecture without big-Oh notation for bounded-error quantum query complexity (or for that matter bounded-error randomized query complexity), this will be messy since the bound will have to depend on $\epsilon$, the allowed error. For example, the property "G contains an edge" is evasive for deterministic algorithms, but a $\epsilon$-error ...
3
A lot of progress has been made on this question in 2015.
First, in arXiv:1506.04719 [cs.CC], the authors have improved on the quadratic separation by showing a total function $f$ with
$$
Q(f) = \widetilde{O}(D(f)^{1/4}).
$$
On the other hand, in arXiv:1512.04016 [quant-ph], it was shown that the quadratic relationship between quantum and deterministic ...
3
If we restrict attention to graph properties, then we can prove slightly improved bounds compared to the general bounds you mention:
In a classic paper it was shown that $D(f)$ is bounded by $O(Q(f)^6)$ for total functions, $O(Q(f)^4)$ for monotone total functions, and $O(Q(f)^2)$ for symmetric total functions.
First I think the 6th power bound can be ...
2
It will depend on the model of communication: (1) If the proof is known by both players, (2) if only parts of it is known by Alice and the rest by Bob, or (3) if only one of the players receives the proof (say Alice). Plus, if the communication uses public or private coins.
For instance, in (3) with public coins, Merlin could send a copy of y to Alice, and ...
2
This can be reduced to rectangular RMQ in $O(n^2)$ time and space. Create a new array $H$ where $H[i][i+j] := G[i][j]$, padding entries $H[i][k]$ with $k < i$ or $k \ge i + n$ with $\infty$. Run $RMQ(a, b, c, d)$ on $H$ whenever you would run $RMQ_P(a, b, c, d)$ on $G$.
Now run your favorite 2D-RMQ algorithm such as this. Perhaps you want to be very ...
2
As mentioned in the comments, if you allow some extra additive slack of $\varepsilon\in(0,1]$ (an input parameter) in the error guarantee, and relax the success probability from one to $1-\delta$ (another input parameter), then the question becomes equivalent to agnostic PAC-learning the class $\mathcal{C}_n$ of $n$-state DFAs with membership queries.
...
1
Roughly $O(k \log(n/k))$ queries suffice, in the regime you are talking about.
We can equivalently think of this as finding a minimal vertex cover for $G$, given ability to query whether a particular set is a vertex cover or not. The algorithm is as follows:
Let $S := V$ (the set of all vertices).
While $S$ is not a minimal vertex cover:
Pick a random ...
1
Ok, I found the answer in this survey: http://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf
The sensitivity $s(f)$ of a (nonconstant) symmetric function $f$ is $s(f) \geq \lceil\frac{n+1}{2}\rceil$. However, $D(f) \geq s(f)$ and $R_{1/4}(f) \geq \frac{s(f)}{3}$...
There are other interesting results concerning symmetric functions in this survey (see ...
1
Some of the performance-related things you can objectively compare between different databases:
IO complexity and computational complexity of different queries. E.g. there are different ways to do joins, sorting, different kinds of indices (including "no indices"), with objectively different asymptotic complexity. There are also column-oriented and row-...
Only top voted, non community-wiki answers of a minimum length are eligible
