Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Tag Info

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

### 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

### 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

### 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
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

### 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
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
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 ...

### 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
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
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 ...

### 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

### 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

• 513
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

### 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