# Tag Info

Accepted

### Distinguishing a biased coin with a small set of tests

Yes. Such families are called "averaging samplers", and there are plenty of constructions for them. You can find a more information about them (and about the more general notion of sampler) in this ...
Accepted

### Trivial upper bound for distribution testing

You might find this short note helpful ($\LaTeX$ code available  if the binary link breaks). I am reproducing the relevant part below: Theorem. (Folklore) Learning an unknown distribution over ...
Accepted

### How long does it take to find a short cycle in a random graph?

No, you can't beat $\Theta(\sqrt{n})$ queries. I will explain how to formalize exfret's proof sketch of this, in a way that works for adaptive algorithms. This is all anticipated in exfret's answer; ...

### How long does it take to find a short cycle in a random graph?

Let’s assume we can only query the $i$th edge of a given vertex’s adjacency list (which I am assuming is not sorted) or whether two given vertices are adjacent. In this case it should take $\sqrt n$ ...

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

### Property testing in other metrics?

The work of Berman, Raskhodnikova, and Yaroslavtsev  introduces testing of functions $f\colon [n]^d\to \mathbb{R}$ with regard to $L_p$ distances, for $p\geq 1$. It is meant to capture situations ...

### Are there hypothesis classes that are hard to learn but easy to test?

Take the class $\mathcal{M}$ of monotone boolean functions under the uniform distribution on $\{0,1\}^n$: it is known that $O(\sqrt{n}/\varepsilon^2)$ queries are sufficient to test it (even with ...