8
votes
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,350
7
votes
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,451
6
votes
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; ...
- 11.7k
5
votes
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$ ...
- 643
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 ...
- 4,451
4
votes
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,451
3
votes
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,451
3
votes
Lower bound on probability of getting two close points in a sample of $n$ points
Here's a counter-example showing your desired bound is not possible, unless I am mistaken. It's a simple variant of the example in Roei's comment.
Fix any $n$ and $N\ge 4n$. Take $D$ to contain $N/...
- 9,595
2
votes
Property testable in sublinear time in bounded degree graphs but not in general graphs
Chapter 10.5.1 of Oded Goldreich's Introduction to Property Testing (2017) discusses exactly that question. (See his website for an overview of the book, and (free) access to the drafts.)
Now, Theorem ...
- 4,451
2
votes
Trivial upper bound for distribution testing
Let's denote $N:=|\Omega|$. Then $\Theta(|N|/\epsilon^2)$ examples are both necessary and sufficient to learn the distribution to additive precision $\epsilon$ in total variation. This follows from ...
- 10.3k
2
votes
Accepted
Robustness to non-uniform randomness vs. one-sidedness
Only one-sided deciders are robust to bad coins, under your definition; no other decider can be robust to bad coins. Let $D$ be a decider that is not one-sided. For $x \in \mathcal{Y}$, let $\...
- 11.7k
1
vote
Are there hypothesis classes that are hard to learn but easy to test?
Please define testing precisely (under what distribution? known/unknown?). In the meantime, here is an example of what you may be looking for. Consider the example in the Kearns-Vazirani book, of ...
- 10.3k
Only top scored, non community-wiki answers of a minimum length are eligible