REPORTS > DETAIL:

### Paper:

TR10-156 | 24th October 2010 05:58

#### Property Testing via Set-Theoretic Operations

TR10-156
Authors: Victor Chen, Madhu Sudan, Ning Xie
Publication: 24th October 2010 10:02
Given two testable properties $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, under what conditions are the union, intersection or set-difference
testing. As an application, we give a conceptually different proof that linearity is testable, albeit with much worse query complexity. Furthermore, for the problem of testing disjunction of linear functions, which was previously known to be one-sided testable with a super-polynomial query complexity, we give an improved analysis and show it has query complexity $O(1/\eps^2)$, where $\eps$ is the distance parameter.