Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

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: 3156
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