ICS 2011
|
|
Welcome to ICS2011
Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, 211-222, 978-7-302-24517-9
Tsinghua University Press
Given two testable properties P1 and P2, 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/ε2), where ε is the distance parameter. Preview: 
|
Copyright 2010-2011, Institute for Computer Science, Tsinghua University, All Rights Reserved.