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

# Tag Info

Accepted

### Is testing easier/harder than learning?

If the learning algorithm is proper (i.e. it always produces a hypothesis from the class $F_n$), then it also gives a testing algorithm -- simply run the learning algorithm, and see whether the ...
• 9,800
Accepted

### What is the reason for using a "Lines-Oracle" in the PCP Theorem?

The lines oracle is used to decrease the query complexity of the test from $d+1$ to $2$, at the expense of using a larger alphabet. If you don't mind making $d+1$ queries, then the lines oracle is ...
• 5,055
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,055
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,331
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; ...
• 10.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$ ...
• 633
Accepted

### Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$

Here are the lower bounds I can show. I conjecture that for a fixed $\epsilon$, the right lower bound is $\Omega( \log n)$, but naturally I might be wrong. I am going to use a decreasing sequence (...
• 9,556

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

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

### Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$

Lower bound At least $\Omega(1/\sqrt{\epsilon})$ queries are necessary to distinguish the two cases. Consider the sequence $a_1,\dots,a_n$ given by $\epsilon,2\epsilon,3\epsilon,4\epsilon,\dots$, ...
• 10.3k
Accepted

### Distance of arbitrary vectors to Hadamard code

What you are asking is the covering radius of the Hadamard code. I am not sure what the answer is but the covering radius of the punctured Hadamard code is at least $\frac{N}{2} - \frac{\sqrt{N}}{2}$, ...
Accepted

### Determining the number of clusters using property testing algorithm

First. One can do better as far as the sampling - at least if $d$ is large - $O(\frac{kd \log k}{\epsilon} \log \frac{1}{\epsilon})$ should follow easily from relative approximations http://sarielhp....
• 9,556

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/... • 8,133 3 votes Accepted ### Hitting set of very restricted linear forms There is a tight lower bound of size$\Omega(n/ \log n)$by simple counting argument. Suppose there is a hitting set$H=\{\alpha_{1},\dots,\alpha_{k}\}$of size$k$. We will show that there is always ... • 1,120 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,331 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,331 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$\...
• 10.3k
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 ...