7
votes
Accepted
Las Vegas vs Monte Carlo randomized decision tree complexity
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 ...
- 13.3k
7
votes
Las Vegas vs Monte Carlo randomized decision tree complexity
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 ...
- 13.5k
5
votes
Are there distribution properties which are "maximally" hard to test?
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 ...
- 4,331
5
votes
Information complexity of query algorithms?
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 ...
- 2,391
5
votes
Accepted
Tolerance parameter of statistical query model and adaptivity
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 (...
- 881
5
votes
Quantum evasiveness conjecture?
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 ...
- 814
5
votes
Accepted
What's the proof of this lemma by Hajnal about the randomized query complexity of monotone graph properties?
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)$.
- 1,733
4
votes
Accepted
The SQ argument in Balazs Szorenyi's paper
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 ...
- 18k
4
votes
Complexity of approximating a real function using queries
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 ...
- 10k
4
votes
Accepted
Does MCMC belong to the statistical query model?
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] ...
- 881
4
votes
Accepted
What is the impact of encodings of sparse structures on the complexity of the model checking problem?
I don't know of any natural logic, but the following is in any case a logic for which the combined complexity of the model-checking problem is different for matrix and list encodings.
First, we know ...
- 736
3
votes
decision tree complexity and query complexity
Chapters-3,4 in book Analysis of Boolean Functions by Ryan O'Donnell might be a good starting point.
- 1,984
3
votes
Bounding the gap between quantum and deterministic query complexity
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) = \...
- 3,860
3
votes
Bounding the gap between quantum and deterministic query complexity
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)...
- 13.3k
3
votes
Quantum evasiveness conjecture?
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 ...
- 13.3k
2
votes
Accepted
Complexity of Parallelogram Range Minimum Query
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 $...
- 513
2
votes
Accepted
Agnostic query learning for DFAs
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$ (...
- 4,331
2
votes
On motivation towards study of width parameters beyond treewidth
It is not hard to see that if a class of queries has arity bounded by $a$ and hypertree width bouded by $k$, then it will also have treewidth bounded by $a\cdot k$. Indeed, any bag in a hypertree ...
- 1,855
1
vote
Accepted
Composition theorem for randomized communication complexity
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, ...
- 4,331
1
vote
What is known about learning a maximal independent set in a (very) sparse graph?
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 ...
- 10.3k
1
vote
Accepted
Randomized and deterministic query complexity of symmetric functions
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$. ...
- 293
1
vote
Accepted
What are the most fundamental metrics (criterions) of database performance?
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 ...
- 8,641
Only top scored, non community-wiki answers of a minimum length are eligible