TR10-156 Authors: Victor Chen, Madhu Sudan, Ning Xie

Publication: 24th October 2010 10:02

Downloads: 812

Keywords:

Given two testable properties $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, under what conditions are the union, intersection or set-difference

of these two properties also testable?

We initiate a systematic study of these basic set-theoretic operations in the context of property

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.