ICS Theory Group

ICS 269, Spring 2005: Theory Seminar

4 Mar 2005:
"Some 3CNF Properties are Hard to Test" by Eli Ben-Sasson, Prahladh Harsha and Sofya Raskhodnikova.
Presented by Nodari Sitchinava.

Abstract: Property testing deals with a relaxation of decision problems where one must determine whether an input belongs to a particular set, called property, or is far from it. For example, for a boolean formula φ on n variables, the associated property Pφ is a collection of n-bit strings that satisfy φ. The authors prove that there are 3CNF properties (properties for boolean formulae in 3CNF form) that require a linear number of queries, even for adaptive tests. In contrast, it is known that 2CNF properties can be tested with O(sqrt(n)) queries. I will briefly indroduce property testing and present the proof of hardness of 3CNF properties testing.

This paper appeared in STOC'03.