# 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 ...
• 5,625
Accepted

### Trivial upper bound for distribution testing

You might find this short note helpful ($\LaTeX$ code available [1] if the binary link breaks). I am reproducing the relevant part below: Theorem. (Folklore) Learning an unknown distribution over ...
• 4,481
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; ...
• 12.3k

### 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$ ...
• 653

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

### Property testing in other metrics?

The work of Berman, Raskhodnikova, and Yaroslavtsev [1] 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 ...
• 4,481

### 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 ...
• 4,481