Testing Assignments to Constraint Satisfaction Problems

on YouTube ↗31m

" summary

Gives a precise criterion: CSP assignments admit constant-query testing exactly when the template’s polymorphism algebra has both a majority and a Maltsev (or Pixley) operation, and otherwise testing requires sublinear or linear queries. Proof uses algebraic reductions (PP-interpretation) to show hard cases encode modules or asymmetric binary relations, and uses majority/Maltsev to reduce to binary, complete-graph instances that a simple sampling one-sided tester can verify with constant queries.

AI-written summary · about

" chapters (14)

1. 0:00Start
2. 0:53The Constraint Satisfaction Problem
3. 2:15Graph colourability
4. 3:16The CSP decision problem
5. 6:34A distance function for assignments
6. 11:39Testing assignments to CSPs
7. 15:25Query complexity of CSP(A)
8. 16:53The algebra associated with CSP(A)
9. 18:06Some special polymorphisms
10. 19:27Some examples
11. 20:30Constant query testable templates
12. 21:59The non constant query testable case
13. 23:39The constant query case
14. 26:50Related result and question