48 citations · 103 across the 33 of their papers we have counts for
6 papers · 1 filter
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…
The Richness of CSP Non-redundancy
Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen +2
In the field of constraint satisfaction problems (CSP), a clause is called redundant if its satisfaction is implied by satisfying all other clauses. An instance of CSP is call…
Robust Factorizations and Colorings of Tensor Graphs
Joshua Brakensiek, Sami Davies
Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3-coloring have primarily centered around SDP-based rounding. However, it is likely that importan…
Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees
Joshua Brakensiek, Aaron Potechin
In this paper, we prove almost tight bounds on the size of sound monotone switching networks accepting permutations sets of directed trees. This roughly corresponds to proving almo…