39 citations · 308 across the 129 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.CG2015★ 3 cited
Dissection with the Fewest Pieces is Hard, Even to Approximate
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +4
We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of $1+1/1…
cs.CC2015★ 1 cited
Near-Optimal UGC-hardness of Approximating Max k-CSP_R
Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
In this paper, we prove an almost-optimal hardness for Max -CSP based on Khot's Unique Games Conjecture (UGC). In Max -CSP, we are given a set of predicates each of w…
cs.DS2015
Approximating Dense Max 2-CSPs
Pasin Manurangsi, Dana Moshkovitz
In this paper, we present a polynomial-time algorithm that approximates sufficiently high-value Max 2-CSPs on sufficiently dense graphs to within approximation…