22 citations · 107 across the 16 of their papers we have counts for
Showing 2019 · cs.DMShow all
2 papers · 2 filters
cs.DM2019★ 22 cited
The complexity of promise SAT on non-Boolean domains
Alex Brandts, Marcin Wrochna, Stanislav Živný
While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, Guruswami, and Håstad roved a result known as "-SAT is NP-hard" [FOCS'14/SICOMP'17]. They sh…
cs.DM2019
Pliability and Approximating Max-CSPs
Miguel Romero, Marcin Wrochna, Stanislav Živný
We identify a sufficient condition, treewidth-pliability, that gives a polynomial-time algorithm for an arbitrarily good approximation of the optimal value in a large class of Max-…