Back to Boolean Function Analysis
Back to notes

# UG-hardness of Max-Cut

10%

In this note, we are going to see how to derive UG-hardness for approximating Max-Cut based on the existence of Dictator-vs.-No-Notable test. The proof flow is based on the Exercise 7.30 in (O’Donnell, 2014) which mainly followed (Khot, Kindler, Mossel, & O’Donnell, 2007).

## Introduction

In 1995, Goemans and Williamson (Goemans & Williamson, 1995) designed a 0.878 approximation algorithm for Max-Cut, which is one of the first SDP approximation algorithm. However, the lower bound side haven’t match the approximation ratio. Currently, the best NP-hardness inapproximation ratio we get is $16/17\approx0.941176$ by Håstad (Håstad, 2001). Surprisingly, assuming the Unique Game Conjecture (UGC), Khot et. al. (Khot, Kindler, Mossel, & O’Donnell, 2007) showed that the approximation ratio of Goemans and Williamson is optimal! In this note, we are going to see one of the key step of proving the UG-hardness of Max-Cut.

### Recall

Please see the homepage of UGC note for the definition of Unique Game (UG) and the statement of UGC.

Define the $(\alpha,\beta)$-Dictator-vs.-No-Notable test as follows.

$T$ is a $(\alpha,\beta)$-Dictator-vs.-No-Notable test with predicate set $\Psi$ with $0<\beta<\alpha<1$ if the following holds. Given the truth table of a function $f:\Bit^q\rightarrow\Bit$, exists a function $\lambda(\epsilon)$ which will decay to 0 as $\epsilon\rightarrow0$. For any $\epsilon>0$,

• (Completeness) If $f$ is a dictator, then $T$ accepts $f$ with probability at least $\beta$.
• (Soundness) If $f$ has no $(\epsilon,\epsilon)$-notable coordinate, i.e., $\bfI_i^{(1-\epsilon)}[f]\leq\epsilon$ for any $i\in[q]$, then $T$ accepts $f$ with probability at most $\alpha+\lambda(\epsilon)$.
• (Test) $T$ only uses predicates from $\Psi$.

Also, recall the relation of property test and Gap-CSP problem.

Property test Gap-CSP
Test $T$ CSP instance $\mathcal{P}$
A single test A clause
Test type Predicate type
Input function Assignment
Success probability Satisfying fraction

### Proof flow

Here, we first sketch the proof flow and elaborate each steps with some high-level details. Mathematical details will be provided in later section.

• Reduce an UG instance $\mathcal{G}$ to a $\text{Gap-CSP}(\Psi)$ instance $\mathcal{P}$:
• By randomized reduction.
• Encoding the variable of $\mathcal{G}$ with long code.
• Completeness:
• If $\text{OPT}(\mathcal{G})\geq1-\delta$, then $\text{OPT}(\mathcal{P})\geq\beta-O(\delta)$.
• Soundness:
• If there exists assignment $F$ for $\mathcal{P}$ such that $\text{Val}_{\mathcal{P}}(F)\geq\alpha+2\lambda(\epsilon)$, then there exists a randomized assignment for $\mathcal{G}$ with value $\Omega(\lambda(\epsilon)\epsilon^5)$.

## UG-hardness of $\text{Gap-CSP}(\Psi)$

### The reduction

Given an UG instance $\mathcal{G}=(V,E,{\pi_{e}}_{e\in E})$, construct the following instance of $\text{Gap-CSP}(\Psi)$

## References

1. O’Donnell, R. (2014). Analysis of boolean functions. Cambridge University Press.
2. Khot, S., Kindler, G., Mossel, E., & O’Donnell, R. (2007). Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM Journal on Computing, 37(1), 319–357.
3. Goemans, M. X., & Williamson, D. P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6), 1115–1145.
4. Håstad, J. (2001). Some optimal inapproximability results. Journal of the ACM (JACM), 48(4), 798–859.