Why the $\textbf{PCP}(\log n, 1)$ construction of completeness $c$ and soundness $s$ for an $NP$ language $L$ implies $s/c$ inapproximability for $L$?

Question

In the introductory chapter of $\textbf{PCP}$ in Arora and Barak, I read the proof that why a $\textbf{PCP}(\log n, 1)$ of completeness 1 and soundness 1/2 for an $NPC$ language $L$ will imply that there exists a $\rho$ for which $\rho$-approximation algorithm for MAX-3-SAT does not exist unless $P = NP$. But in the paper, https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf authors say that "We construct a PCP that reads two bits from the proof and accepts if and only if the two bits are unequal. The completeness and soundness are $c$ and $s$ respectively. This implies that MAX-CUT is $NP$-hard to approximate within any factor greater than $s/c$." What is the proof for this?

Answer 1

The authors give a reduction $x \mapsto f(x)$ from some NP-hard problem $X$ to MAX-CUT with the following properties:

• If $x$ is a YES instance then $OPT(f(x)) \geq c$.
• If $x$ is a NO instance then $OPT(f(x)) \leq s$.

Here $OPT(y)$ is the optimal value of the MAX-CUT instance $y$.

Suppose now that you had an algorithm for MAX-CUT with approximation ratio $\rho > s/c$, which means that for every instance $y$, $ALG(y) \geq \rho OPT(y)$, where $ALG(y)$ is the value of the instance produced by the algorithm. We can use this algorithm to solve $X$, since $x$ is a YES instance of $X$ iff $OPT(f(x))>s$ (I'll let you verify that).

This informally explains the statement in the paper. Any more formal explanation requires a definition of "NP-hard to approximate". One possibility is as follows. Let $Y$ be a maximization problem. We say that $Y$ is NP-hard to approximate within a factor of $\rho$ if for every problem $X \in \mathsf{NP}$ there exists a polytime computable reduction $f$ which on input $x$ produces a tuple $(y,v)$, where $y$ is an instance of $Y$ and $v$ is a number, with the following properties:

• If $x$ is a YES instance of $X$ then $OPT(y) \geq v$.
• If $x$ is a NO instance of $X$ then $OPT(y) < \rho v$.

This generalizes the usual definition of NP-hardness for optimization problems, which corresponds to the choice $\rho = 1$. Under this definition, if $Y$ is NP-hard to approximate within a factor of $\rho$ and there is a polytime $\rho$-approximation algorithm for $Y$, then $\mathsf{P} = \mathsf{NP}$. Finally, according to this definition, MAX-CUT is indeed NP-hard to approximate to within any factor strictly larger than $s/c$.