Fall 2016

Testing Assignments to Constraint Satisfaction Problems

Thursday, November 10th, 2016 4:00 pm4:30 pm

Add to Calendar

For a finite relational structure A, let CSP(A) denote the CSP instances whose constraint relations are taken from A. We consider CSP(A) from the perspective of property testing: given an instance of CSP(A) and query access to an assignment, one wants to decide whether the assignment satisfies the instance, or is far from doing so.  We establish a dichotomy theorem completely characterizing the structures A such that CSP(A) is constant-query testable: (i) If A has a majority polymorphism and a Maltsev polymorphism, then CSP(A) is constant-query testable with one-sided error. (ii) Else, testing CSP(A) requires a super-constant number of queries.  This is joint work with Hubie Chen and Yuichi Yoshida.