22 citations · 107 across the 16 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
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-…
cs.CC2019★ 19 cited
Improved hardness for H-colourings of G-colourable graphs
Marcin Wrochna, Stanislav Živný
We present new results on approximate colourings of graphs and, more generally, approximate H-colourings and promise constraint satisfaction problems. First, we show NP-hardness of…