Name
Abstract | ||
|---|---|---|
We characterize the set of properties of Boolean-valued functions f:X ->{0,1} on a finite domain X that are testable with a constant number of samples (x,f(x)) with x drawn uniformly at random from X. Specifically, we show that a property P is testable with a constant number of samples if and only if it is (essentially) a k-part symmetric property for some constant k, where a property is k-part symmetric if there is a partition X1, horizontal ellipsis ,Xk of X such that whether f:X ->{0,1} satisfies the property is determined solely by the densities of f on X1, horizontal ellipsis ,Xk. We use this characterization to show that symmetric properties are essentially the only graph properties and affine-invariant properties that are testable with a constant number of samples and that for every constant d >= 1, monotonicity of functions on the d-dimensional hypergrid is testable with a constant number of samples. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1002/rsa.20807 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | DocType | Volume |
Property testing,sample complexity,partial symmetry | Journal | 55.0 |
Issue | ISSN | Citations |
1.0 | 1042-9832 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eric Blais | 1 | 286 | 22.49 |
| Yuichi Yoshida | 2 | 469 | 44.88 |