48 citations · 103 across the 33 of their papers we have counts for
3 papers · 2 filters
Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
Joshua Brakensiek, David Conlon, Venkatesan Guruswami +4
In the study of constraint satisfaction problems (CSPs), the non-redundancy of a relation measures the maximum number of clauses in a CSP instance which can be logically independen…
The Reach of Abelian Covers in Hypergraphs
Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
Covers in hypergraphs are frequently studied to capture various forms of dependence between hyperedges. For example, even covers--which check if each vertex appears in an even numb…
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…