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 ...
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
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 ...
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)$.
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 $...
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 ...
3
Chapters-3,4 in book Analysis of Boolean Functions by Ryan O'Donnell might be a good starting point.
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 ...
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 ...
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
My understanding is that it's not following from [Nisan94], but from [BCW98] (note that there are two citations provided from Theorem 5), specifically their Theorem 2.1. while phrased for quantum, this generalizes to classical models as well.
See Theorem 69 of Troy Lee and Adi Shraibman's survey [LS09], available, e.g., at this address.
[BCW98] Buhrman, ...
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
