# Tag Info

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

### 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 ...
• 849
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,743
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 ...
• 18.2k

### 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 ...
• 10.6k
Accepted

### Independent set queries with preprocessing

If the graph is uniformly sparse in the sense that every subgraph with $n$ vertices contains at most $d \cdot n$ edges for some small $d$, then degeneracy ordering could be exploited to have $O(|E|)$ ...
• 1,821
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 ...
• 1,099

### 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 ...
• 2,174

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