Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SAMPLE-BASED:
Reports tagged with sample-based:
TR15-089 | 31st May 2015

#### Trading query complexity for sample-based testing and multi-testing scalability}

We show here that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than $1$, power of $n$. Since the query ... more >>>

TR16-201 | 19th December 2016
Eric Blais, Yuichi Yoshida

#### A Characterization of Constant-Sample Testable Properties

We characterize the set of properties of Boolean-valued functions on a finite domain $\mathcal{X}$ that are testable with a constant number of samples.
Specifically, we show that a property $\mathcal{P}$ is testable with a constant number of samples if and only if it is (essentially) a $k$-part symmetric property ... more >>>

ISSN 1433-8092 | Imprint