Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
Pravesh Kothari, Princeton University
E18-304
Abstract: We present an efficient algorithm to solve semi-random planted instances of any Boolean constraint satisfaction problem (CSP). The semi-random model is a hybrid between worst-case and average-case input models,…