Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random.

Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar

Browse the full STOC paper archive.