10 citations · 11 across the 5 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2016★ 1 cited
All or nothing: toward a promise problem dichotomy for constraint problems
Lucy Ham, Marcel Jackson
A finite constraint language is a finite set of relations over some finite domain . We show that intractability of the constraint satisfaction problem $\operatorna…
cs.CC2016
Gap theorems for robust satisfiability: Boolean CSPs and beyond
Lucy Ham
A computational problem exhibits a "gap property" when there is no tractable boundary between two disjoint sets of instances. We establish a Gap Trichotomy Theorem for a family of…