approximation hardness 1communication delays 1hypergraph coloring 1precedence constraints 1scheduling 1
From the 1 of 34 linked papers with an AI index.
1 citations · 1 across the 12 of their papers we have counts for
Showing cs.DMShow all
2 papers · 1 filter
cs.DM2026
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…
cs.DM2025
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…