We say that an algorithm robustly decides a CSP if it distinguishes >(1-epsilon)-satisfiable instances from <(1-r(epsilon))-satisfiable instances, where r(epsilon)->0 as epsilon->0. We prove that the canonical linear program robustly decides a CSP iff it has width 1. We also prove that this is exactly the class of CSP's testable with constantly many queries (in the so-called bounded degree model).

Joint work with Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida and Yuan Zhou.