Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances

Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2

We say that an instance of a constraint satisfaction problem (CSP) is non-redundant if the satisfaction of each clause cannot be implied by the satisfaction of the other clauses in…