Check out RSS, or use RSS reader to subscribe this item
Confirmation
Authentication email has already been sent, please check your email box: and activate it as soon as possible.
You can login to My Profile and manage your email alerts.
Sponsored by the Center for Science and Technology Development of the Ministry of Education
Supervised by Ministry of Education of the People's Republic of China
This note presents some hardness results of testing Boolean functions in the random example model. First we present a hardness of testing under arbitrary distributions. As a consequence, we obtain that the class of intersections of halfspaces cannot be tested in arbitrary distributions. Second we present a hardness result of testing under the uniform distribution when assuming weak pseudorandom functions.
Keywords:Property Testing; Intersection of Halfspaces; Weak Pseudorandom Functions