Min-CSPs on Complete Instances II:
Polylogarithmic Approximation for Min-NAE-3-SAT

In the context of Min-$k$-CSPs, the objective function is the fraction of violated constraints. Hence, for a Min-$k$-CSP instance $ℐ$, we define $\mathrm{OPT}$ to be the minimum over all the variable assignments $\alpha$ of the fraction of constraints in $ℐ$ unsatisfied by $\alpha$. With such an objective, the trick discussed above ceases to work: a highly satisfiable instance has a very small optimal value, possibly even $\mathrm{OPT}\le O(1/n^k)$. Due to this eventuality, we cannot afford to additively lose an $ϵ$ term for each constraint: it would result in an objective value of, say, $ϵ+\mathrm{OPT}\gtrsim n\cdot \mathrm{OPT}$ unless $ϵ\ll 1/n^{k-1}$. Unfortunately, the degree $d$ of the pseudodistribution needs to be larger than the number $r=O(1/{ϵ}^2)$ of variables we condition on, so setting $ϵ\ll 1/n^{k-1}$ is prohibitive.

On the flip side of the above discussion, one can deduce that if $\mathrm{OPT}\ge 1/\text{polylog}(n)$ we can in fact afford to lose an additive $O(ϵ)$ term for $ϵ=1/\text{polylog}(n)$ and still run in $n^{O(r)}=n^{\text{polylog}(n)}$ time. Even more so, if $\mathrm{OPT}\ge 1/\text{polylog}(n)$ then we always get a $\text{polylog}(n)$-approximation, no matter what solution we output (since the value we obtain is always at most $1$). We can therefore restrain ourselves to consider instances with small optimal value.

Let $\mu$ be an optimal pseudodistribution for our instance $ℐ$, and let us denote by $\delta =\mathrm{val}(\mu )$ the fractional objective value achieved by $\mu$ on $ℐ$. Thanks to ˜1, we can assume $\delta \le \mathrm{OPT}\le 1/\text{polylog}(n)$. Recalling that we are in the realm of complete instances, a simple averaging yields the following observation.

We remark that a version of Insight 2 remains true for dense – but not necessarily complete – instances up to an $\mathrm{\Omega }(1)$ loss in the lower bound. However, being dense is not a “hereditary property”, while being complete is a “hereditary property”: any variable-induced sub-instance of a complete instance is also complete and in particular dense, while this might not be the case for dense instances. Thus, assuming that $ℐ$ is complete allows us to benefit from Insight 2 locally to any variable-induced sub-instance. As we will see, this is instrumental to our algorithm.

Consider any constraint $P_{\{u,v,w\}}$ that is unsatisfied with probability at most ${\delta }^{\prime }$ over ${\mu }_{\{u,v,w\}}$, for some ${\delta }^{\prime }\in [0,1]$. By Insight 2, we can assume that ${\delta }^{\prime }\le 2\delta \le 1/\text{polylog}(n)$. Then one can see that, among the six satisfying assignments of $P_{\{u,v,w\}}$, there is one that retains probability mass at least $(1-1/\text{polylog}(n))/6\ge 1/7$ in ${\mu }_{\{u,v,w\}}$. Call this satisfying assignment $({\alpha }_u^{\ast },{\alpha }_v^{\ast },{\alpha }_w^{\ast })$. Assuming for simplicity that the literals of $P_{\{u,v,w\}}$ are all positive, we conclude that exactly two of ${\alpha }_u^{\ast },{\alpha }_v^{\ast },{\alpha }_w^{\ast }$ must be equal. By symmetry, we can assume that ${\alpha }_v^{\ast }={\alpha }_w^{\ast }=0$ and ${\alpha }_u^{\ast }=1$. We now consider the pseudodistribution $\tilde{\mu }={\mu |}_{(v,w)\leftarrow ({\beta }_v,{\beta }_w)}$ obtained by conditioning on the variables $v,w$ taking the random value $({\beta }_v,{\beta }_w)\sim {\mu }_{v,w}$. We can observe that $({\beta }_v,{\beta }_w)=({\alpha }_v^{\ast },{\alpha }_w^{\ast })=(0,0)$ with probability at least $1/7$. Therefore, if such an event occurs, we have ${\tilde{\mu }}_u(0)\le 14\delta$, as one can deduce from Table 1. In this case, we say that $u$ becomes $O(\delta )$-fixed in $\tilde{\mu }$.

We now continue to look at a fixed constraint $P_{\{u,v,w\}}$ as above, and consider the following random experiment: draw a random pair of variables $x,y$ together with a random assignment $({\beta }_x,{\beta }_y)\sim {\mu }_{x,y}$ sampled from their local distribution, and let $\tilde{\mu }={\mu |}_{(x,y)\leftarrow ({\beta }_x,{\beta }_y)}$ be the pseudodistribution obtained by conditioning on the pair $(x,y)$ taking value $({\beta }_x,{\beta }_y)$. With probability $1/\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ we hit the pair $(v,w)$, i.e., $(x,y)=(v,w)$, and with probability $1/7$ we have $({\beta }_x,{\beta }_y)=({\beta }_v,{\beta }_w)=(0,0)$. This means that the variable $u$ becomes $O(\delta )$-fixed in $\tilde{\mu }$ with probability at least $0.1/\left(\genfrac{}{}{0pt}{}{n}{2}\right)$. By Insight 2, we know that for many (i.e., $\mathrm{\Omega }(n)$) choices for $u$, there are many (i.e., $\mathrm{\Omega }(n^2)$) triples $P_{\{u,v,w\}}$ that can $O(\delta )$-fix $u$, as the one considered in the discussion above. Using the linearity of expectation and Markov’s inequality, we can then conclude the following.

A formal version of this fact is stated in Lemma 4.1.

We recall that conditioning on a random assignment $({\beta }_x,{\beta }_y)\sim {\mu }_{x,y}$ preserves the objective value in expectation, i.e., $𝔼[\mathrm{val}(\tilde{\mu })]=\mathrm{val}(\mu )=\delta$. Hence, Insight 3 seems to suggest that conditioning on just two variables allows making nontrivial progress towards the goal of rounding the pseudodistribution: the entropy of $\mathrm{\Omega }(n)$ variables should drastically decrease while preserving the expected objective value. However, the conditioning alone is not enough, as its effect decreases when the entropy becomes already small but still nontrivial (e.g., if all but $\sqrt{n}$ variables are $O(\delta )$-fixed, the above argument cannot guarantee any more progress). While independent rounding suffices for Max-CSPs in this case, its additive loss can still be prohibitive for the minimization objective.

In order to bypass this barrier, we additionally use thresholding to round many $O(\delta )$-fixed variables to exactly $0$ or $1$. Formally, $\widehat{\mu }$ is a new pseudodistribution where for each variable $u$ that is $O(\delta )$-fixed in $\tilde{\mu }$, fix $u$ to the bit retaining $1-O(\delta )$ of the probability mass of ${\tilde{\mu }}_u$.

We now zoom in on a constraint $P_{\{u,v,w\}}$ with only positive literals where, say, $u$ has been fixed to $1$ in $\widehat{\mu }$. Call $\gamma$ the probability that $P_{\{u,v,w\}}$ is unsatisfied by an assignment sampled from ${\tilde{\mu }}_{\{u,v,w\}}$ for convenience. One can observe that the probability of $P_{\{u,v,w\}}$ being violated by an assignment sampled from ${\widehat{\mu }}_{\{u,v,w\}}$ equals ${\widehat{\mu }}_{\{u,v,w\}}(1,1,1)$. This is because the assignment $(0,0,0)$ has probability mass $0$ in ${\widehat{\mu }}_{\{u,v,w\}}$, since we fixed $u$ to $1$. Then, with the help of Table 2, we can convince ourselves that the probability of $P_{\{u,v,w\}}$ being unsatisfied by an assignment sampled from ${\widehat{\mu }}_{\{u,v,w\}}$ is no larger than $\gamma$ up to an additive $O(\delta )$ error.

From the above discussion, we conclude that the fractional objective value $\mathrm{val}(\widehat{\mu })$ of $\widehat{\mu }$ is at most $\mathrm{val}(\tilde{\mu })+O(\delta )$. Recalling that $𝔼[\mathrm{val}(\tilde{\mu })]=\mathrm{val}(\mu )=\delta$, Insight 3 can then be refined as follows.

A formal version of this fact can be obtained by combining Lemma 4.1 and Lemma 4.2.

In order to materialize the strategy of Algorithm 1, we need to control the deviations of $\mathrm{val}(\widehat{\mu })$ from $\delta$ at every level of the recursion. More precisely, let ${\mu }^{(i)}$ be the pseudodistribution at the beginning of the $i$-th recursion level, and let ${\delta }_i$ the fractional objective value $\mathrm{val}({\mu }^{(i)})$ of the pseudodistribution ${\mu }^{(i)}$.

For the sake of exposition, here let us ignore the hidden constant in $O(\delta )$ and assume $𝔼[\mathrm{val}({\mu }^{(i)})]$ $=\mathrm{val}({\mu }^{(i-1)})$ (the ignored error comes from the clauses at least one of whose variables is completely fixed by the threshold step, so it can be controlled via the concept of the aggregate value defined in equation (1) of Section 4). With this assumption, at every level $i$ of the recursion we have

Applying this identity at every level, we get

where the last inequality follows assuming that the pseudodistribution on which we first call the algorithm is optimal. Now, one can intuitively see that the deviation of the last pseudodistribution ${\mu }^{(\text{\#levels})}$ from its expected objective value translates to the approximation ratio achieved by the algorithm. Therefore, we are interested in bounding such deviation. To do so, we have to peel off one expectation operator at a time in the above equation by means of Markov’s inequality. At every level $i$, the guarantee would then be $\mathrm{val}({\mu }^{(i)})\le \lambda \cdot \mathrm{val}({\mu }^{(i-1)})$ with probability $1-1/\lambda$. Since this gives

we need a $\lambda$ such that ${\lambda }^{\text{\#levels}}\le \tilde{O}(1)$. Recalling that $\text{\#levels}=\mathrm{\Omega }(\log n)$, we must hence require $\lambda \le 1+1/\log n$. Unfortunately, Markov’s inequality ensures $1+1/\log n$ multiplicative increase with only $p_{\text{val}}=O(1/\log n)$ success probability. If we call $p_{\text{fix}}=1/1000$ the probability that $\widehat{\mu }$ fixes $n/1000$ variables, we realize that

We are therefore unable to conclude that there exists a choice of $x,y,{\beta }_x,{\beta }_y$ for which we both have that ${\mu }^{(i)}$ fixes $n/1000$ variables and ${\mu }^{(i)}\le (1+1/\log n)\cdot {\mu }^{(i-1)}$. For the left-hand side above to be less than one, we need $p_{\text{fix}}\ge 1-O(1/\log n)$.

Recalling that we allow our algorithm to run in $n^{\text{polylog}(n)}$ time, we can assume to have a $\text{polylog}(n)$-degree pseudodistribution at our disposal. Supported by this, the natural thing to do is modifying each level of the recursion as follows: condition on $O(\log \log n)$ random pairs - as opposed to one - and their respective assignments. While this should boost $p_{\text{fix}}\ge 1-O(1/\log n)$, we now have more conditioning steps that could deviate from the expectation. However, suppose we could condition on a random set of $O(\log \log n)$ pairs of variables whose joint local distribution is close (in total variation distance) to the product of their marginal distributions: then, we would both obtain the high probability guarantee and simultaneously have only one deviation from the objective value to control. A standard way to ensure that the joint distribution of $t$ (pairs of) variables is $ϵ$-close to independent is by additionally conditioning on $\text{poly}(2^t/ϵ)$ variables [33, 36]. Since we want $t=O(\log \log n)$ and $ϵ=1/\text{polylog}(n)$, we can afford to do so with our $\text{polylog}(n)$-degree pseudodistribution.

A formal version of this algorithm is presented and analyzed in Section 4.

Notice that before we reach lines 3 or 9, every recursive call to Algorithm 2 involves one conditioning step and one thresholding step. Let us consider in particular a call of Algorithm 2 that starts from a pseudodistribution $\mu \in 𝒟(V,d)$, and a set of unfixed variables $V_{\mathrm{U}}\subseteq V$ such that neither line 3 nor 9 is reached. Then, the conditioning step produces a pseudodistribution $\tilde{\mu }$. This step does not change the assignment $\alpha$, or the set of unfixed variables $V_{\mathrm{U}}$. Next, the thresholding step rounds some variables in $\tilde{\mu }$ and produces a pseudodistribution $\widehat{\mu }$, and updates the assignment $\alpha$. Let us call this updated assignment ${\alpha }^{\prime }$ and let $V_{\mathrm{U}}^{\prime }=\{v\in V\mid {\alpha }_v^{\prime }=\frac{1}{2}\}$ be the set of unfixed variables with respect to ${\alpha }^{\prime }$. For the sake of convenience, let us set define $A(\mu ):=A^{V_{\mathrm{U}}}(\mu )$, $A(\tilde{\mu }):=A^{V_{\mathrm{U}}}(\tilde{\mu })$, and $A(\widehat{\mu }):=A^{V_{\mathrm{U}}^{\prime }}(\widehat{\mu })$. In words, $A(\mu )$ and $A(\tilde{\mu })$ are defined with respect to the set $V_{\mathrm{U}}$, whereas $A(\widehat{\mu })$ is defined with respect to the set $V_{\mathrm{U}}^{\prime }$ obtained after thresholding. We will show two things: first, we argue that $|V_{\mathrm{U}}^{\prime }|\le 99/100\cdot |V_{\mathrm{U}}|$, and second we argue that the increase in the aggregate value $A(\widehat{\mu })-A(\mu )$ is at most $50A(\mu )/\log n$.

Recall our setting of parameters: $K={10}^{20}$, $r={(\log n)}^{100K}$, $t=K\log \log n$, $ϵ=1/10\log n$, $\tau =K{\log }^{2}n$, $c=200K^2$. Since lines 3 and 9 are not reached, we can assume that $|V_{\mathrm{U}}|\ge c_1\ge K^2{\log }^{100}n$ and that $\mathrm{val}(ℐ[V_{\mathrm{U}}],\mu [V_{\mathrm{U}}])\le \frac{1}{10\tau }$. By the guarantee of Lemma 4.1 with $W=V_{\mathrm{U}}$ and $\rho =\mu [V_{\mathrm{U}}]$, there exists $r^{\prime }\in \{0,\mathrm{\dots },r\}$ such that

We also observe that for all $i\in \{0,1,2,3\}$ we have

which follows from the property of conditional expectation¹¹1Note that while the conditioning “fixes” the variables we condition on, we still do not add these variables to $V_{\mathrm{U}}$ - this happens only after the thresholding step. Hence, the sets $V_{\mathrm{U}}$ and $V_{\mathrm{F}}$ remain unchanged, and therefore a constraint which contributes to ${\mathrm{LP}}_i^{V_{\mathrm{U}}}(\mu )$ continues to contribute to ${\mathrm{LP}}_i^{V_{\mathrm{U}}}({\mu |}_{C\leftarrow \gamma })$ for all $i\in \{0,1,2,3\}$.. This in turn means that

By Markov’s inequality, it follows that

It follows that there exists a choice of $𝐜\in W^{r^{\prime }+2t}$ and $\gamma \in \mathrm{supp}({\mu }_C)$ such that we simultaneously have

In particular, we must have

Next, we analyze the rounding step. Note that the pseudo-distribution $\widehat{\mu }$ is obtained by rounding $\tilde{\mu }$. By using Lemma 4.2 with $\rho =\tilde{\mu }$, it follows that

Note that $\tau \delta \left(\genfrac{}{}{0pt}{}{|V_{\mathrm{U}}|}{3}\right){\log }^{2}n=\tau \cdot {\mathrm{LP}}_3^{V_{\mathrm{U}}}(\mu ){\log }^{2}n\le \frac{A(\mu )}{\log n}$, since $\delta \left(\genfrac{}{}{0pt}{}{|V_U|}{3}\right)={\mathrm{LP}}_3^{V_U}(\mu )$. This gives