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

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

The non-redundancy (NRD) of a constraint satisfaction problem (CSP) is a combinatorial quantity closely tied to the behavior of CSPs in various computational models including their…