Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ONE-SIDED ERROR:
Reports tagged with One-Sided Error:
TR13-109 | 11th August 2013
Oded Goldreich, Dana Ron

#### On Sample-Based Testers

Revisions: 1

The standard definition of property testing endows the tester with the ability to make arbitrary queries to elements''
of the tested object.
In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object.
While sample-based testers were defined by
Goldreich, Goldwasser, and Ron ({\em JACM}\/ ... more >>>

TR14-115 | 27th August 2014
Roei Tell

#### Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees

Revisions: 1

A few years ago, Blais, Brody, and Matulef (2012) presented a methodology for proving lower bounds for property testing problems by reducing them from problems in communication complexity. Recently, Bhrushundi, Chakraborty, and Kulkarni (2014) showed that some reductions of this type can be deconstructed to two separate reductions, from communication ... more >>>

ISSN 1433-8092 | Imprint