# 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.