Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 (...
user avatar
  • 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 ...
user avatar
  • 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)$.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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] ...
user avatar
  • 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 ...
user avatar
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.
user avatar
  • 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) = \...
user avatar
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)...
user avatar
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 ...
user avatar
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 $...
user avatar
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$ (...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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$. ...
user avatar
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 ...
user avatar
  • 8,641

Only top scored, non community-wiki answers of a minimum length are eligible