Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs
Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs
In this paper, we consider lower bounds on the query complexity for testing CSPs in the bounded-degree model. We mainly consider Boolean CSPs allowing literals. First, for any "symmetric" predicate P : {0, 1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sup> → {0,1} except EQU where k ≥ 3, we show that every (randomized) …