ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-156 | 24th October 2010 05:58

Property Testing via Set-Theoretic Operations

RSS-Feed




TR10-156
Authors: Victor Chen, Madhu Sudan, Ning Xie
Publication: 24th October 2010 10:02
Downloads: 564
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint