Property Testing via Set-Theoretic Operations

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\mathrm{/}{\text{eps}}^2)$, where $\text{eps}$ is the distance parameter.