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


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