For which c, d is Gap2SAT[c, d] in P (such that 0

Question

For which $c, d$ is $Gap2SAT[c, d]$ in $P$  (such that $0<c<d<1$)?

(I know if d=1 then for each c it will be in P, however with which c,d such that  $0<c<d<1$ can I simply return YES?)

Yuval Filmus · Answer

Assuming the Unique Games Conjecture, your problem is solved for MAX-CUT in Ryan O'Donnell and Yi Wu, An optimal SDP algorithm for Max-Cut,
and equally optimal Long Code tests, who determined the gap curve for this problem.

I am not aware of any such work for MAX-2SAT, but Per Austrin has essentially determined the optimal approximation ratio (again, assuming the Unique Games Conjecture) in his paper Balanced MAX 2-SAT might not be the hardest.

In celebrated work, Prasad Raghavendra has essentially determined the optimal approximation ratio for any constraint-satisfaction problem, again assuming the Unique Games Conjecture.

For which c, d is Gap2SAT[c, d] in P (such that 0<c<d<1)?

One Answer

Add your own answers!

Ask a Question