### DIMACS Theoretical Computer Science Seminar

Title: Testing Assignments of Boolean CSPs

Speaker: **Arnab Bhattacharyya**, DIMACS/Rutgers University

Date: Wednesday, October 3, 2012 11:00-12:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Given an instance I of a CSP, a tester for I distinguishes assignments satisfying I from those
which are far from any assignment satisfying I. The efficiency of a tester is measured by its
query complexity, the number of variable assignments queried by the algorithm. In this work,
we characterize the hardness of testing Boolean CSPs according to the relations used to form
constraints. In terms of computational complexity, we show that if a Boolean CSP is sublinear-query
testable (resp., not sublinear-query testable), then the CSP is in NL (resp., P-complete,
parityL-complete or NP-complete) and that if a sublinear-query testable Boolean CSP is
constant-query testable (resp., not constant-query testable), then counting the number
of solutions of the CSP is in P (resp., #P-complete). The classification is done by showing
an Omega(n) lower bound for testing Horn 3SAT and investigating Post's lattice, the inclusion
structure of Boolean algebras associated with CSPs.

Joint work with Yuichi Yoshida

See: http://paul.rutgers.edu/~yixinxu/theory-fall12.html