Plaintext
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28
www.theoryofcomputing.org
S PECIAL ISSUE : CCC 2019
UG-hardness to NP-hardness
by Losing Half
Amey Bhangale∗ Subhash Khot†
Received July 24, 2019; Revised March 4, 2022; Published March 15, 2022
Abstract. The 2-to-2 Games Theorem (Khot et al., STOC’17, Dinur et al., STOC’18
[2 papers], Khot et al., FOCS’18) shows that for all constants ε > 0, it is NP-hard to
distinguish between Unique Games instances with some assignment satisfying at
least a ( 12 − ε) fraction of the constraints vs. no assignment satisfying more than an
ε fraction of the constraints. We show that the reduction can be transformed in a
non-trivial way to give stronger completeness: For at least a ( 12 − ε) fraction of the
vertices on one side, all the constraints associated with them in the Unique Games
instance can be satisfied.
We use this guarantee to convert known UG-hardness results to NP-hardness.
We show:
1. Tight inapproximability of the
maximum
size of independent sets in degree-d
d
graphs within a factor of Ω log2 d
, for all sufficiently large constants d.
A preliminary version of this paper appeared in the Proceedings of the 34th Computational Complexity
Conference (CCC’19) [12].
∗ Research supported by Irit Dinur’s ERC-CoG grant 772839.
† Research supported by NSF CCF-1813438, Simons Collaboration on Algorithms and Geometry, and Simons
Investigator Award.
ACM Classification: F.2
AMS Classification: 68Q17
Key words and phrases: NP-hardness, inapproximability, Unique Games Conjecture
© 2022 Amey Bhangale and Subhash Khot
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2022.v018a005
A MEY B HANGALE AND S UBHASH K HOT
2. For all constants ε > 0, NP-hardness of approximating the size of the Maximum
Acyclic Subgraph within a factor of 23 + ε, improving the previous ratio of 14
15 + ε
by (Austrin et al., Theory of Computing, 2015).
3. For all constants ε > 0 and for any predicate P−1 (1) ⊆ [q]k supporting a balanced
pairwise independent distribution, given a P-CSP instance with value at least
1 |P−1 (1)|
2 − ε, it is NP-hard to satisfy more than a qk
+ ε fraction of constraints.
1 Introduction
The Unique Games Conjecture is a central open problem in the theory of computing. It states
that for a certain constraint satisfaction problem over a large alphabet, called Unique Games
(UG), it is NP-hard to decide whether a given instance has an assignment that satisfies a (1 − ε)
fraction of the constraints or there is no assignment that satisfies even an ε fraction of the
constraints for an arbitrarily small constant ε > 0. Since the formulation of the conjecture, it has
found interesting connections to tight hardness-of-approximation results for many optimization
problems [18, 19, 23, 27, 17, 22, 24, 25]. One of the most notable implications is the result of
Raghavendra [27] which informally can be stated as follows: Assuming the NP-hardness of
approximating this single CSP (Unique Games) implies tight hardness for approximating every
other constraint satisfaction problem, stated in terms of the integrality gap of a certain canonical
SDP.
The Unique Games Conjecture was inspired by the NP-hardness of approximating a problem
called Label Cover [1]. A Label Cover instance G = (A, B, E, ΣA , ΣB , {πe }e∈E ) consists oftwo sets
of variables, A and B, and a bipartite graph between them with the edge set E. The variables
from A take values from some alphabet ΣA and variables from B take values from ΣB . Every
edge e in E has a d-to-1 projection1 constraint πe : ΣA → ΣB .
For an edge e(a, b), a label α to a and a label β to b satisfy the edge e iff πe (α) = β . In this
language, Unique Games is a Label Cover instance where all the constraints are 1-to-1. We
denote an instance of Unique Games by G = (A, B, E, [L], {πe }e∈E ) where ΣA = ΣB = [L].
Given an instance of Unique Games, the goal is to find an assignment to the vertices
that satisfies a good fraction of the edges. An instance is called ε-satisfiable if there exists an
assignment σ : A ∪ B → [L], that satisfies at least an ε fraction of the edges in the graph. The
Unique Games Conjecture [18] states that for every ε > 0, there exists L such that given a Unique
Games instance which is (1 − ε)-satisfiable, it is NP-hard to find an ε-satisfying assignment.
Note that there is a polynomial-time algorithm that given a 1-satisfiable instance of Unique
Games, finds a 1-satisfying assignment. Recent work [20, 14, 15, 21] has shown that for every
constant ε > 0, it is NP-hard to find an ε-satisfying assignment for a given Label Cover instance
with 2-to-1 projection constraints, even if the instance is (1 − ε)-satisfiable. This directly implies
the following inapproximability for Unique Games.
1A constraint πe : ΣA → ΣB is called a d-to-1 projection constraint, if every β ∈ ΣB has exactly d preimages.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 2
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
Theorem 1.1 (UG-hardness with completeness 1/2 [20, 14, 15, 21]). For every constant ε > 0, there
exists Σ such that for Unique Games instance over Σ, it is NP-hard to distinguish between the following
two cases:
• YES case: The instance is ( 12 − ε)-satisfiable.
• NO case: No assignment satisfies an ε fraction of the constraints.
Although we do not improve upon this theorem in terms of the inapproximability gap, we
show a stronger guarantee in the YES case. Specifically, we show that in the YES case, there is at
least a 12 − ε fraction of the vertices on, say, the left side such that all the edges incident on them
are satisfied by some assignment and also the instance is left-regular. This clearly implies the
above theorem. Formally, the main theorem that we prove is as follows. (See Definition 2.1 for a
formal definition of Unique Games.)
Theorem 1.2 (Main). For every constant δ > 0, there exists L ∈ N such that the following holds. Given
an instance G = (A, B, E, [L], {πe }e∈E ) of Unique Games, which is regular on the A side, it is NP-hard to
distinguish between the following two cases:
• YES case: There exists a set A0 ⊆ A of size ( 12 − δ )|A|, and an assignment that satisfies all the edges
incident on A0 .
• NO case: Every assignment satisfies at most a δ fraction of the edges.
We will denote by val(G) the maximum fraction, over all assignments, of the edges satisfied
and sval(G) to be the maximum fraction, over all assignments, of the vertices in A such that all
the edges incident on them are satisfied. Thus, the above theorem says that for every δ > 0 there
exists a label set [L] such that it is NP-hard to distinguish between the cases sval(G) ⩾ 12 − δ and
val(G) ⩽ δ .
1.1 ( 21 − ε)-satisfiable UG vs. (1 − ε)-satisfiable UG
Let ε > 0 be a very small constant. In the (1 − ε)-satisfiable Unique Games instance, by simple
averaging argument √ it follows that for any satisfying assignment √ σ : A ∪ B → [L], there exists
A0 ⊆ A, |A0 | ⩾ (1 − ε)|A| such that for all v ∈ A0 , at least a (1 − ε) fraction of the edges incident
on v are satisfied. Having such a large A0 is crucial in many UG-reductions. For example, a
typical k-query PCP, used in proving UG-hardness of approximation for k-ary CSPs, samples
v ∈ A uniformly at random √ and k √ neighbors of u1 , u2 , . . . , uk of v uniformly at random. Thus, with
probability at least (1 − ε)(1 − k ε) ≈ 1 all the edges (u, vi ) are satisfiedby any (1 − ε)-satisfying
assignment σ .
In contrast to this, if we take a (1/2)-satisfiable UG instance then the probability that all the
edges (v, ui ) are satisfied is at most 1/2k in the worst case. Therefore, in converting a known
UG-hardness result to an NP-hardness result using the NP-hardness of Unique Games with gap
( 12 − ε, ε), it is not always the case that we lose ‘only half ’ in completeness.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 3
A MEY B HANGALE AND S UBHASH K HOT
Another important property of the Unique Games instance which was used in many
reductions is that it has stronger completeness; there is a (1 − δ ) fraction of the vertices on
one side such that all the edges incident on them are satisfied, i. e., sval(G) ⩾ 1 − δ instead
of val(G) ⩾ 1 − δ . For example, this property was crucial in the hardness of approximating
the maximum size of independent sets in bounded-degree graphs [4] and in many other
reductions [8, 11].
As shown in [23], having completeness val(G) ⩾ 1 − δ for all sufficiently small δ > 0 is
equivalent to having completeness sval(G) ⩾ 1 − δ 0 for all sufficiently small δ 0 > 0. It was crucial
in the reduction that the val(G) is arbitrarily close to 1 for the equivalence to hold. We do not
know a black-box way of showing the equivalence of val(G) = c and sval(G) = c for any c < 1.
Thus, in order to prove Theorem 1.2 with a stronger completeness guarantee, we crucially exploit
the structure of the game given by the known proofs of the 2-to-1 theorems [20, 14, 15, 21]
mentioned in the introduction.
1.2 Implications
Using Theorem 1.2, we show the following hardness results by going over the known reductions
based on the Unique Games Conjecture.
Independent sets in degree-d graphs The first application is approximating the maximum
sized independent set in a degree-d graph, where d is a large constant.
Theorem 1.3. It is NP-hard (under
randomized reductions) to approximate independent sets in a degree-d
d
graph within a factor of O log2 d
, where d is a constant independent of the number of vertices in the
graph.
This improves the NP-hardness of approximation within a factor O logd4 d , as shown in
Chan [13] as well as shows the tightness of the randomized polynomial-time approximation
algorithm given by Bansal et al. [7].
Max-Acyclic Subgraph Given a directed graph G(V, E), the Max-Acyclic Subgraph problem is
to determine the maximum fraction of edges E 0 ⊆ E such that removal of E \ E 0 makes the graph
acyclic (removes all the cycles). We can always make a graph acyclic by removing at most half
the edges; take any arbitrary ordering of the vertices and remove either all the forward edges
or all the backward edges whichever is minimum. This gives a trivial (1/2)-approximation
algorithm. Guruswami et al. [17] showed this is tight by showing that assuming the Unique
Games Conjecture, it is NP-hard to approximate Max-Acyclic Subgraph within a factor of 12 + ε
for all ε > 0. In terms of NP-hardness, Austrin et al. [5] showed NP-hardness of approximating
Max-Acyclic Subgraph within a ratio of 14 65
15 + ε, improving upon the previous bound of 66 + ε by
2
Newman [26]. Our next theorem shows an improved inapproximability of 3 + ε. One interesting
feature of our reduction is that it shows that in the worst case, it is NP-hard to perform better
than the trivial algorithm described above on instances with value at least 3/4.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 4
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
Theorem 1.4. For every constant ε > 0, it is NP-hard to approximate the Max-Acyclic Subgraph problem
within a factor of 23 + ε.
We note that Theorem 1.1 along with the reduction from [17] implies NP-hardness of
approximation of the Max-Acyclic Subgraph problem within a factor of 45 + ε. (See Remark 5.5
for a proof sketch.) Therefore, Theorem 1.4 improves upon this bound too.
Predicates supporting balanced pairwise independent distributions The next result is
approximating Max-k-CSP(P) for a predicate P : [q]k → {0, 1} where P−1 (1) supports a balanced
pairwise independent distribution, i. e., there exists a distribution on P−1 (1) such that 1)
the marginal distribution on each coordinate is uniform and 2) the distribution is pairwise
−1
independent. Given an instance of Max-k-CSP(P), a random assignment satisfies a |P qk(1)| fraction
of the constraints in expectation. Austrin–Mossel [6] showed that given a (1 − ε)-satisfiable
−1
instance of Max-k-CSP(P), it is UG-hard to find an assignment that satisfies more than a |P qk(1)| + ε
fraction of the constraints for any constant ε > 0. This notion is called approximation resistance of
a predicate P where the best efficient algorithm cannot perform any better than just choosing a
random assignment, even if the instance is almost satisfiable. Showing approximation resistance
of such predicates unconditionally (i. e., assuming only P 6= NP) has received significant attention.
For instance, Chan [13] showed that a predicate P is approximation resistant if P−1 (1) contains a
subgroup that supports a balanced pairwise independent distribution. Also, Barak et al. [9]
showed that certain class of algorithms, namely sum-of-squares, cannot be used to perform
better than the random assignment on almost satisfiable instances of Max-k-CSP(P) where P
supports a balanced pairwise independent distribution.
Our main theorem shows approximation resistance of such predicates but on instances
which are (1/2)-satisfiable. If we use Theorem 1.2 as a starting point of the reduction in [6], we
get the following NP-hardness result.
Theorem 1.5. If a predicate P : [q]k → {0, 1} supports a balanced pairwise independent distribution,
−1
then for every constant ε > 0, it is NP-hard to find a solution with value |P qk(1)| + ε if a given P-CSP
instance is ( 12 − ε)-satisfiable.
Other Results Theorem 1.2 implies many more NP-hardness results in a straightforward way
by going over the known UG-reductions but we shall restrict ourselves to proving only the
above three theorems. We only state the following important implication which follows from
the result of Raghavendra [27] and our main theorem. We refer to [27] for the definition of (c, s)
SDP integrality gap of a P-CSP instance.
Theorem 1.6. (Informal) For every constant ε > 0, if a P-CSP has a (c, s) SDP integrality gap instance,
then it is NP-hard to distinguish between ( 2c − ε)-satisfiable instances from at most (s + ε)-satisfiable
instances.
The reduction actually gives a stronger result; instead of completeness ( 2c − ε) one can get
−1
( 2c + 2r − ε) where r = |P qk(1)| for a predicate P : [q]k → {0, 1}.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 5
A MEY B HANGALE AND S UBHASH K HOT
1.3 Overview of the proof
In this section, we give an overview of the proof of Theorem 1.2. The main idea that goes into
proving Theorem 1.2 is very simple and we elaborate it next.
Let V = Fn2 and let Gr(V, `) denote the set of all `-dimensional linear subspaces of V . Consider
the tables F : Gr(V, `) → F`2 and H : Gr(V, ` − 1) → F`−1 0
2 , where for a subspace L (L ), F[L] (H[L ])
0
represents a linear function F[L] : L → F2 (H[L0 ] : L0 → F2 ) on the subspace, by fixing an arbitrarily
chosen basis of L (L0 ).2 The intention is that there should be some global linear function g : V → F2 ,
such that for every L, F[L] = g|L , and for every L0 , H[L0 ] = g|L0 . We consider the Grassmann 2-to-1
test T1 from Figure 1.3 as a means to verify that the tables, F and H, are indeed obtained by
restricting some global linear function.
Given tables F and H, where F assigns to each `-dimensional subspace L ∈ Gr(V, `) a linear
function F[L] : L → F2 , and H assigns to each (` − 1)-dimensional subspace L0 ∈ Gr(V, ` − 1)
a linear function H[L0 ] : L0 → F2 .
• Select an (` − 1)-dimensional subspace L0 ⊆ V uniformly at random.
• Select an `-dimensional subspace L containing L0 uniformly at random.
• Check if F[L]|L0 = H[L0 ].
Figure 1: 2-to-1 Test T1
We have the following two easy observations about the test.
• The test is 2-to-1 in the following sense. Fix any assignment for L0 , which is a linear
function β : L0 → F2 . Consider any linear function α : L → F2 such that α|L0 = β . Since
L0 ⊆ L and the co-dimension of L0 in L is exactly 1, there are exactly two possible choices
for α such that α|L0 = β . Therefore, for every fixing of H[L0 ], there are exactly two settings
of F[L] such that the test accepts the pair (F[L], H[L0 ]).
• The test has perfect completeness, i. e., if F and H are indeed the restrictions of a global linear
function g : V → F2 , then the test passes with probability 1.
The soundness of this test is analyzed in [21] with additional contributions from [14, 10].
They show that if the test passes with probability at least δ > 0, then the tables must be
non-trivially consistent with some global linear function g : V → F2 , where δ > 0 is an arbitrarily
small constant independent of ` and n.
In this paper, we focus on converting the test to a unique test, i. e., a 1-to-1 test, with some
additional structure. One way to convert a 2-to-1 test to a unique test is by choosing a random
2Any linear function f : L → F2 on an `-dimensional space L can be specified by specifying ( f (b1 ), f (b2 ), . . . , f (b` )) ∈
F`2 where b1 , b2 , . . . , b` ∈ L form a basis of L.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 6
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
i ∈ {1, 2} for every pair (L, L0 ) such that L0 ⊆ L and for every linear function β on L0 , and adding
just one accepting pair (αi , β ) where {(α1 , β ), (α2 , β )} are the original accepting assignments
from the 2-to-1 test T1 . This does give a unique test and if F and H are restrictions of a global
linear function to the subspaces, then the test passes with probability 1/2. One drawback of this
test is as follows. Consider a bipartite graph on Gr(V, `) × Gr(V, ` − 1) where two subspaces L, L0
are adjacent iff L0 ⊆ L. Note that the uniform distribution on the edges of this bipartite graph is
the same as the test distribution T1 . We say that an edge (L0 , L) is satisfied by the tables F and
H, if F[L]|L0 = H[L0 ]. For any global linear function g : V → F2 , if F and H are the restrictions
of g, then we can only argue that half the edges are satisfied in the sense of the unique test.
Hence, the similar guarantee of satisfying around half the edges stays in the final Unique Games
instance created from the articles [20, 14, 15, 21] and thus falls short of proving Theorem 1.2.
Now we convert it into a Unique Test T2 (Figure 1.3) with a guarantee that for around half of
the vertices on one side of the bipartite test graph, all the edges incident on them are satisfied if
the tables F and H are the restrictions of some global linear function.
/ × {0, 1} → F`−1
Given tables F and H, where F : Gr(V, `) × (2[`] \ {0}) 2 and H : Gr(V, ` − 1) →
`−1
F2 ,
• Select an (` − 1)-dimensional subspace L0 uniformly at random.
• Select an `-dimensional subspace L containing L0 , x ∈ L \ L0 and b ∈ {0, 1} uniformly
at random.
• Check if F[L, x, b]|L0 = H[L0 ].
Here, F[L, x, b] is thought of as a linear function f : L → F2 such that f (x) = b, and H[L0 ] is
thought of as a linear function L0 → F2 , by choosing arbitrary bases of the linear spaces
Lx = {y ∈ L | y ⊥ x} and L0 , respectively.
Figure 2: Unique Test T2
Towards this goal, we modify the domain of F. We consider two tables, F : Gr(V, `) × (2[`] \
/ × {0, 1} → F`−1
{0}) 2 and H : Gr(V, ` − 1) → F`−1
2 . We fix an arbitrary one-to-one correspondence
between the non-zero elements of the `-dimensional subspace L and 2[`] \ {0} / for every L. Thus,
we can now interpret F as defined on a tuple (L, x, b) where x ∈ L \ {0} and b ∈ {0, 1}. We consider
the entries F[L, x, b] and H[L0 ] as linear functions on the spaces L and L0 , respectively, as follows.
As before, we select an arbitrary basis for every (` − 1)-dimensional subspaces Gr(V, ` − 1). Now
F[L, x, b] ∈ F`−1
2 is thought of as a linear function L → F2 such that
1. at point x it evaluates to b, and
2. the evaluations of the linear function on the subspace Lx = {y ∈ L | y ⊥ x}, which is an
(` − 1)-dimensional subspace, is given by F[L, x, b] in terms of the already chosen basis of
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 7
A MEY B HANGALE AND S UBHASH K HOT
Lx ).
As before, H[L0 ] is thought of as a linear function L0 → F2 in terms of the chosen basis for L0 .
Consider the following bipartite graph Gr(V, `) × (2[`] \ {0})
/ × {0, 1}, Gr(V, ` − 1), E where
(L, x, b) is connected to L0 iff x ∈/ L0 and L0 ⊆ L. The test distribution from the Unique Test T2 is
uniform on the edges of this graph.
We now put permutation constraints on the edges of the graph. For an edge e ∈ E between
(L, x, b) and L0 , we set the following permutation constraint. Extend the linear function given by
H[L0 ] to a linear function H̃L0 ,x,b [L] on L = span{L0 , x} by setting H̃L0 ,x,b [L](x) = b. The accepting
labels for an edge e are F[L, x, b] and H[L0 ] such that H̃L0 ,x,b [L] and F[L] are identical when thought
of as linear functions on L. Note that the constraint is one-to-one.
Fix any global linear function g : V → F2 . From this, we define H[L0 ] as the restriction of g
on L0 . We define the table F partially by setting F[L, x, g(x)] as the restriction of g on L. Thus
for every (L, x, g(x)), it is clear that all the edges attached to it are satisfied by the tables H and F.
The set {(L, x, g(x))} also constitutes half of one side of the bipartite test graph. This particular
structure on the set of satisfying edges from this bipartite graph goes into the final Unique
Games instance that we construct. Therefore, in the YES case of the final reduction, we have that
there is an assignment such that for at least half the vertices on one side, all the edges attached to
them are satisfied. This establishes the completeness of our reduction from the main theorem.
Finally, the soundness of the Unique Test T2 follows directly from the soundness of the 2-to-1
Test T1 and we use this to prove the soundness of our reduction.
2 Preliminaries
We start by defining the Unique Games.
Definition 2.1 (Unique Games). An instance G = (A, B, E, [L], {πe }e∈E ) of the Unique Games
constraint satisfaction problem consists of a bipartite graph (A, B, E), an alphabet [L] and a
permutation map πe : [L] → [L] for every edge e ∈ E. Given a labeling σ : A ∪ B → [L] , an edge
e = (u, v) is said to be satisfied by σ if πe (σ (v)) = σ (u).
G is said to be at most δ -satisfiable if every labeling satisfies at most a δ fraction of the edges.
We will define the following two quantities related to the satisfiability of the Unique Games
instance.
val(G) := max {fraction of edges in G satisfied by σ } .
σ :A∪B→[L]
0
|A |
sval(G) := max ∀e(u, v) s.t. u ∈ A0 , e is satisfied by σ .
σ :A∪B→[L] |A|
The following is a conjecture by Khot [18] which has been used to prove many tight
inapproximability results.
Conjecture 2.2 (Unique Games Conjecture[18]). For every sufficiently small δ > 0 there exists L ∈ N
such that given an instance G = (A, B, E, {πe }e∈E , [L]) of Unique Games it is NP-hard to distinguish
between the following two cases:
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 8
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
• YES case: val(G) ⩾ 1 − δ .
• NO case: val(G) ⩽ δ .
For a subset U of a vector space V , span(U) denotes its span. The notation span(U1 ,U2 ) stands
for span(U1 ∪U2 ) and for x ∈ V , span(x,U) stands for span({x},U). Note that for subspaces L1 , L2
we have span(L1 , L2 ) = L1 + L2 := {x1 + x2 | xi ∈ Li } (the sumset). If L1 ∩ L2 = {0} then L1 + L2 is
the direct sum, also denoted L1 ⊕ L2 .
For 0 < ` < n, let Gr(Fn2 , `) be the set of all `-dimensional subspaces of Fn2 . Similarly, for a
subspace L of Fn2 such that dim(L) > `, let Gr(L, `) be the set of all `-dimensional subspaces of Fn2
contained in L.
3 The Reduction
In this section, we go over the reduction in [15] from a gap 3LIN instance to a 2-to-1 Label Cover
instance and then show how to reduce it to a Unique Games instance in Section 3.4. We retain
most of the notations from [15].
3.1 Outer Game
The starting point of the reduction is the following problem:
Definition 3.1 (Reg-3Lin ). The instance (X, Eq) of Reg-3Lin consists of a set X of n variables,
X = {x1 , x2 , . . . , xn }, taking values in F2 , and a collection Eq of m F2 -linear constraints where each
constraint in Eq is a linear constraint on 3 variables. The instance is regular in the following
ways: every equation consists of 3 distinct variables, every variable xi appears in exactly 5
constraints, and every two distinct constraints share at most one variable.
An instance (X, Eq) is said to be t-satisfiable if there exists an assignment to X which satisfies
at least a t fraction of the constraints. We have the following theorem implied by the PCP
theorem of [2, 3, 16].
Theorem 3.2. There exists an absolute constant s < 1 such that for every constant ε > 0 it is NP-hard to
distinguish between the cases when a given Reg-3Lin instance is at least (1 − ε)-satisfiable vs. at most
s-satisfiable.
We now define an outer 2-prover 1-round game, parameterized by k, q ∈ Z+ and β ∈ (0, 1),
which will be the starting point of our reduction. The verifier selects k constraints e1 , e2 , . . . , ek
from the instance (X, Eq) uniformly at random with repetition. If ei and e j share a variable
for some i 6= j then accept. Otherwise, let xi,1 , xi,2 , xi,3 be the variables in constraint ei . Let
X1 = ki=1 {xi,1 , xi,2 , xi,3 }. The verifier then selects a subset X2 of X1 as follows: for each i ∈ [k],
S
with probability (1 − β ) add xi,1 , xi,2 , xi,3 to X2 and with probability β , select a variable from
{xi,1 , xi,2 , xi,3 } uniformly at random and add it to X2 .
On top of this, the verifier selects q pairs of advice strings (s j , s∗j ) where s j ∈ {0, 1}X2 , and
s∗j ∈ {0, 1}X1 for 1 ≤ j ≤ q as follows : For each j ∈ [q], select s j ∈ {0, 1}X2 uniformly at random.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 9
A MEY B HANGALE AND S UBHASH K HOT
The string s j can be thought of as assigning F2 values to each of the variables from X2 . The
string s∗j ∈ {0, 1}3k is deterministically selected such that its projection on X2 is the same as s j
and the rest of the coordinates are assigned 0.
The verifier sends (X1 , s∗1 , s∗2 , . . . , s∗q ) to Prover 1 and (X2 , s1 , s2 , . . . , sq ) to Prover 2. The verifier
expects an assignment to variables in Xi from Prover i. Finally, the verifier accepts if and only if
the assignment to X1 given by Prover 1 satisfies all the equations e1 , e2 , . . . , ek and the assignment
X2 given by Prover 2 is consistent with the answer of Prover 1.
Completeness: It is easy to see the completeness. If the instance (X, Eq) is (1 − ε)-satisfiable
then there is a provers’ strategy which makes the verifier accept with probability at least
(1 − kε). The strategy is to use a fixed (1 − ε)-satisfying assignment and answer according
to it. In this case, with probability at least (1 − kε), the verifier chooses k constraints which
are all satisfied by the fixed assignment and hence the verifier will accept provers’ answers.
Soundness: Consider the case when the instance (X, Eq) is at most s-satisfiable for s < 1 from
Theorem 3.2. If the provers were given only X1 and X2 without the advice strings, then
the Parallel Repetition Theorem of Raz [28] directly implies that for any provers’ strategy,
they can make the verifier accept with probability at most 2−Ω(β k) . This follows because in
expectation, there are β k constraints out of k where Prover 2 receives one variable from
the constraint. It turns out that a few advice strings will not give provers any significant
advantage.
To see this, for each of these β k constraints, with probability 2−q , all the advice strings
get assigned value 000 to the variables in the constraints and therefore does not leak
any information, about which variable from the constraint was being sent to Prover 2,
to Prover 1. Thus in expectation, there are β2qk constraints vs. variable questions where
Prover 1 knows nothing about which variable was being sent to Prover 2. One can then
argue, by using Raz’s Parallel Repetition Theorem, that any provers’ strategy can make
q
the verifier accept with probability at most 2−Ω(β k/2 ) .
The soundness is formally proved in [20].
Theorem 3.3 (Section 3 in [20]). If the Reg-3Lin instance (X, Eq) is at most s-satisfiable (s < 1 from
Theorem 3.2) then there is no strategy with which the provers can make the verifier accept with probability
q
greater than 2−Ω(β k/2 ) .
Remark 3.4. The importance of the advice strings will come later in the proof of soundness.
Specifically, the proof of Theorem 3.14 (from [15] which we use as a black-box) crucially uses the
advice strings given to the provers.
To prove our main theorem, the reduction is carried out in three steps:
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 10
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
Outer Game
↓ [15]
Gunfolded (A, B, E, Π, ΣA , ΣB ) (unfolded 2-to-1 Game)
↓ [15]
Gfolded (Ã, B, Ẽ, Π̃, ΣA , ΣB ) (folded 2-to-1 Game)
↓ (This work)
UGfolded (A,
b B, E,
b Π,
b Σ) (Unique Game)
The first two steps are explained in the next two subsections. These follow from [15]. The main
contribution of our work is the last step which is given in Section 3.4.
3.2 Unfolded 2-to-1 Game
In this section we reduce a Reg-3Lin instance (X, Eq) to an instance of 2-to-1 Label Cover
Gunfolded = (A, B, E, Π, ΣA , ΣB ).
For an equation e ∈ Eq, let supp(e) = {i1 , i2 , i3 } if e is a linear constraint on xi1 , xi2 , xi3 . A set of
k equations (e1 , e2 , . . . , ek ) is legitimate if the supports of the equations are pairwise disjoint and
for every two different equations ei and e j and for any x ∈ ei and y ∈ e j , the pair {x, y} does not
appear in any equation in Eq. Define U to be the following set family.
( )
k
[n]
U=
[
S∈ S = supp(ei ) and (e1 , e2 , . . . , ek ) is legitimate .
3k i=1
Note that by definition, there is a one-to-one correspondence between the set of legitimate k
tuples of equations and U. For U ∈ U, let XU ⊆ Fn2 be the linear subspace whose elements have
support in U. For an equation e ∈ Eq on xi1 , xi2 , xi3 , let xe be the vector in XU where xi1 = xi2 = xi3 = 1
and rest of the coordinates are 0. Denote by be ∈ F2 the RHS of the equation e. Let HU be the
span of {xe | xe ∈ XU }. Finally, let V be the collection of all sets of variables up to size 3k (thought
of as subsets of [n]). Similar to XU , for V ∈ V, let XV ⊆ Fn2 be the linear subspace whose elements
have support in V .
Vertices (A, B): Let ` k which we will set later. The vertex set of the game Gunfolded is defined
as follows:
A = {(U, L) | U ∈ U, L ∈ Gr(XU , `), L ∩ HU = {0}}.
B = {(V, L0 ) | V ∈ V, L0 ∈ Gr(XV , ` − 1)}.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 11
A MEY B HANGALE AND S UBHASH K HOT
Edges E: The distribution on the edges in Gunfolded is defined by the following process: Choose
X1 and X2 as per the distribution given in the outer verifier conditioned on U ∈ U, where
U = xi ∈X1 {i}. Let V = xi ∈X2 {i}. Choose a random subspace L0 ∈ Gr(XV , ` − 1) and a random
S S
L ∈ Gr(XU , `) such that L0 ⊆ L. Output ((U, L), (V, L0 )) ∈ (A, B).
Labels (ΣA , ΣB ): The label set ΣA = F`2 and the label set ΣB = F`−1
2 . A label σ ∈ ΣA to (U, L) can
be thought of as a linear function σ : L → F2 . Similarly the label σ 0 ∈ ΣB to a vertex (V, L0 ) is
though of as a linear function σ 0 : L0 → F2 . This can be done by fixing arbitrary basis of the
respective spaces.
3.3 Folded 2-to-1 Game
For every assignment to the 3LIN instance, there are many vertices in the graph Gunfolded which
get the same label in accordance with the strategy of labeling the vertices in Gunfolded with
respect to a fixed assignment to X. So we might as well enforce this constraint on the variables
in Gunfolded . This is achieved by folding. In this section, we convert Gunfolded to the following
Game Gfolded = (Ã, B, Ẽ, Π̃, ΣA , ΣB ).
Vertices (Ã, B): Consider the following relation on the vertices in A:
(U1 , L1 ) ∼R (U2 , L2 ) iff L1 + HU1 + HU2 = L2 + HU1 + HU2 .
The following Lemma 3.5 says that ∼R is indeed an equivalence relation, i. e., A = C1 t C2 t . . .,
where each Ci is one of the equivalence classes. In other words, if (U0 , L0 ) ∈ Ci , then
Ci = {(U, L) ∈ A | L + HU + HU0 = L0 + HU + HU0 }.
The proof of the lemma crucially uses the facts that U corresponds to a legitimate set of
equations and that the Reg-3Lin instance is regular, namely, every equation consists of three
distinct variables and every two distinct constraints share at most one variable.
Lemma 3.5 (Lemma 3.2 in [15]). The relation ∼R defined above is an equivalence relation: for every i,
there exists an `-dimensional subspace RCi such that for all (U, L) ∈ Ci ,
HU + L = RCi + HU .
We define the vertex set à as follows:
à = {C(U, L) | (U, L) ∈ A},
where C(U, L) is the equivalence class of (U, L). In other words, in Ã, there is a vertex for every
equivalence class.
Edges Ẽ: The distribution on the edges in Gfolded is defined by the following process: sample
((U, L), (V, L0 )) with respect to E and output (C(U, L), (V, L0 )).
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 12
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
Labels (ΣA , ΣB ): The label set ΣA = F`2 , a label σ to C ∈ Ã can be thought of as a linear function
σ : RC → F2 . As before, the label σ 0 ∈ ΣB to a vertex (V, L0 ) is though of as a linear function
σ 0 : L0 → F2 .
In order to define the constraints on the edges, we need the following definitions:
Definition 3.6. For a space HU + L such that L ∩ HU = {0} and a linear function σ : L → F2 , the
extension of σ , respecting the side conditions, to the whole space HU + L is a linear function
β : HU + L → F2 such that for all xe ∈ XU , β (xe ) = be and β |L = σ .
Note that there is a one-to-one mapping between linear functions on L and their extensions
as all the equations in U are disjoint and hence {xe | xe ∈ XU } form a basis for the space HU .
Definition 3.7. Consider a label σ to a vertex C which is a linear function on RC . The unfolding
of it to the elements of the C is given as follows: For (U, L) ∈ C, define a linear function
σ̃U : HU + L → F2 such that it is equal to the extension of σ to HU + RC respecting the side
conditions.
The spaces HU + L and HU + RC are the same and hence the above definition makes sense.
We are now ready to define the constraints.
Constraints Π̃: Consider linear functions σ : RC → F2 and σ 0 : L0 → F2 . A pair (σ , σ 0 ) satisfies
the edge (C, (V, L0 )) ∈ Ẽ, if for every (U, L) ∈ C such that ((U, L), (V, L0 )) ∈ E, the unfolding σ̃U
when restricted to the subspace L0 is σ 0 , i. e., σ̃U |L0 = σ 0 .
We have the following completeness and soundness guarantee of the reduction from [15].
Lemma 3.8 (Completeness). (Lemma 4.1 in [15]) For every constant ε > 0, if the Reg-3Lin instance
(X, Eq) is (1 − ε)-satisfiable then there exists Ã0 ⊆ Ã, |Ã0 | ⩾ (1 − kε)|Ã|, and a labeling to the 2-to-1 Label
Cover instance Gfolded such that all the edges incident on Ã0 are satisfied.
Lemma 3.9 (Soundness). (Lemma 4.2 in [15], and [21]) For all δ > 0, there exist q, k ≥ 1 and β ∈ (0, 1),
such that if the Reg-3Lin instance (X, Eq) is at most s-satisfiable (where s is from Theorem 3.2) then
every labeling to Gfolded satisfies at most a δ fraction of the edges.
3.4 Reduction to Unique Games
In this section, we convert the Label Cover instance Gfolded to a Unique Games instance
with the stronger completeness guarantee that we are after. We will reduce an instance
Gfolded = (Ã, B, Ẽ, Π̃, ΣA , ΣB ) to an instance of Unique Game UGfolded = (A,
b B, E,
b Π,
b Σ).
b B): We will split each vertex C ∈ Ã into many copies. Fix an `-dimensional subspace
Vertices (A,
RC given by Lemma 3.5. For every x ∈ RC \ {0} and b ∈ {0, 1} we add a copy Cx,b to A.b
[
b=
A {Cx,b | x ∈ RC \ {0}, b ∈ {0, 1}} .
C∈Ã
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 13
A MEY B HANGALE AND S UBHASH K HOT
b The distribution on the edge set Eb is as follows: We first pick ((U, L), (V, L0 )) from
Edges E:
the distribution E. Let (U, L) ∈ C. We then select y ∈ (HU + L) \ (HU + L0 ) and b ∈ {0, 1}
independently and uniformly at random. Note that dim(span{y, HU } ∩ RC ) = 1 since y ∈ / HU and
y ∈ HU + L = HU + RC . Let x ∈ span{y, HU } ∩ RC be the non-zero vector. Output (Cx,b , (V, L0 )).
Claim 3.10. x is distributed uniformly in RC \ (HU + L0 ) conditioned on (U,V, L, L0 ).
Proof. We first claim that x ∈ RC \ (HU + L0 ) by showing x ∈ / HU + L0 . Suppose not, then we
can write x = h + x0 where h ∈ HU and x0 ∈ L0 . We also know that x ∈ span{y, HU } ∩ RC and
RC ∩ HU = {0}. Thus, x can be written as x = h̃ + y where h̃ ∈ HU . This implies that h + x0 = h̃ + y.
In other words, y = h + h̃ + x0 ∈ HU + L0 , a contradiction.
Since each y ∈ (HU + L) \ (HU + L0 ) gives a unique non-zero x ∈ span{y, HU } ∩ RC , we will show
that the number of y ∈ (HU + L) \ (HU + L0 ) that give a fixed x is same for all x ∈ RC \ (HU + L0 )
and this will prove the claim.
Fix any x̃ ∈ RC \ (HU + L0 ), we now claim that the set of all y ∈ (HU + L) \ (HU + L0 ) that
give x̃ is span{x̃, HU } \ HU . Clearly, for any y ∈
/ span{x̃, HU } \ HU , x̃ ∈
/ span{y, HU } and also for
every y ∈ span{x̃, HU } \ HU , x̃ ∈ span{y, HU }. Thus, it remains to show that span{x, HU } \ HU ⊆
(HU + L) \ (HU + L0 ) for all x ∈ RC \ (HU + L0 ).
To prove the inclusion, suppose for contradiction (span{x, HU } \ HU ) ∩ (HU + L0 ) 6= 0. / This
means x+h = h̃+v0 for some h, h̃ ∈ HU and v0 ∈ L0 . This implies x = h+ h̃+v0 ∈ HU +L0 contradicting
x ∈ RC \ (HU + L0 ).
Labels Σ: The label set is Σ = F`−1 2 . A label σ to Cx,b can be thought of as a linear function
σ : RC → F2 such that σ (x) = b. This is done by fixing an arbitrary ` − 1 basis elements from the
subspace {y ∈ RC | y ⊥ x}.
It is easy to see that there is a one-to-one correspondence between the labels Σ and the
linear functions σ on RC such that σ (x) = b. Similar to the previous case of Gfolded , a label from
Σ(= ΣB ) to a vertex (V, L0 ) in B is interpreted as a linear function σ 0 : L0 → F2 .
We define an analogous unfolding of the labels, to the vertices in A, b to the elements of the
corresponding equivalence class. Since the label set here is different from Gfolded , for a label
σ to Cx,b (thought of as a linear function on RC respecting σ (x) = b) we use the notation σbU to
denote its unfolding to (U, L) ∈ Cx,b .
1-to-1 Constraints Π: b Finally the constraint πe : Σ → Σ between the endpoints of an edge
0
e = (Cx,b , (V, L )) is given as follows: Consider linear functions σ : RC → F2 respecting σ (x) = b
and σ 0 : L0 → F2 . A pair (σ , σ 0 ) ∈ πe if for every (U, L) ∈ C such that ((U, L), (V, L0 )) ∈ E and
span{x, HU } ∩ L0 = {0}, the unfolding σ̃U satisfies σ̃U |L0 = σ 0 .
To see that every σ 0 has a unique preimage in πe , for any linear function σ 0 : L0 → F2 , there is
a unique linear function σ : RC → F2 such that σ (x) = b satisfying the above conditions. This is
because of the following claim.
Claim 3.11. Any basis for L0 along with x and {xe | xe ∈ XU } forms a basis for HU + RC for every
(U, L) ∈ C.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 14
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
Proof. Let us unwrap the conditions for putting an edge between (V, L0 ) and Cx,b . One necessary
condition is that (C, (V, L0 )) should be an edge in Ẽ. By the definition of Ẽ, there exists
(U, L) ∈ C such that L0 ⊆ L. Recall, x is such that there exists a y ∈ (HU + L) \ (HU + L0 ) such
that dim(span{y, HU } ∩ RC ) = 1 and x ∈ span(y, HU ) ∩ RC . Therefore x ∈ (HU + L) \ (HU + L0 ) and
hence dim(span{x, HU + L0 }) = k + ` (as HU ∩ L0 = {0}). This implies that any basis of L0 , the basis
{xe | xe ∈ XU } of HU , and x span HU + L. Since by Lemma 3.5 the subspace HU + L is same as the
subspace HU + RC , the claim follows.
We now show the completeness and the soundness of the overall reduction to the Unique
Games instance.
3.4.1 Completeness
Lemma 3.12 (Completeness). For every constant ε > 0, if there exists Ã0 ⊆ Ã, |Ã0 | ⩾ (1 − kε)|Ã|, and a
labeling to the 2-to-1 Label Cover instance Gfolded such that all the edges incident on Ã0 are satisfied,
b |Ab0 | ⩾ ( 1−kε )|A|,
then there exists Ab0 ⊆ A, b and a labeling to Unique Games instance UGfolded such that
2
all the edges incident on Ab0 are satisfied.
Proof. Fix a labeling (A˜, B̃) to Gfolded where A˜ : Ã → ΣA and B̃ : B → ΣB that satisfies all the
edges incident on a (1 − kε) fraction of the vertices in Ã. We will construct a labeling (Ac, B) b to
the instance UGfolded , where Ac: A b → Σ and B b : B → Σ that will satisfy all the edges adjacent to
(1−kε) b in UGfolded .
at least a 2 fraction of vertices A
We will set Bb = B̃. Now to assign a label to Cx,b ∈ A, b we look at the label σ := A˜(C) ∈ F` as a
2
linear function σ : RC → F2 . If σ (x) = b, we set Ac(Cx,b ) to be the same linear function σ : RC → F2
respecting σ (x) = b. Otherwise, we set Ac(Cx,b ) =⊥. It is obvious that exactly half the vertices in
A
b got assigned a label in Σ.
Claim 3.13. If the label A˜(C) to C satisfies all the edges incident on it, then for all x ∈ RC \ {0}, there
exists a unique b ∈ {0, 1} such that the label Ac(Cx,b ) satisfies all the edges incident on Cx,b , unless
Ac(Cx,b ) =⊥.
Proof. For convenience let σ = A˜(C). If we let Γ(C) ⊆ B to be the neighbors of C in Gfolded ,
then the set of neighbors of Cx,b is a subset of Γ(C). Furthermore if (V, L0 ) is connected to
Cx,b in UGfolded then x ∈ / L0 and x ∈ RC . The condition that the edge (C, (V, L0 )) is satisfied by
A˜ means that for all (U, L) ∈ C such that L0 ⊆ L, the unfolding of σ satisfies σ̃U |L0 = B̃((V, L0 )).
Since the unfolding of the label Ac(Cx,b ) to Cx,b gives the same linear function σ̃ , it follows that
σ̃U |L0 = B((V,
b L0 )) for every (U, L) ∈ C and every (V, L0 ) ∈ Γ(C) such that L0 ⊆ L. Therefore Ac
satisfies all the edges incident on Cx,b if Ac(Cx,b ) 6=⊥.
Let Ã0 ⊆ Ã be the set of vertices such that all the edges incident on them are satisfied by the
labeling (A˜, B̃). By assumption |Ã0 | ⩾ (1 − kε)|Ã|. Consider the subset Ab0 ⊆ A
b
Ab0 = {Cx,b | Ac(Cx,b ) 6=⊥, C ∈ Ã0 }.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 15
A MEY B HANGALE AND S UBHASH K HOT
Now, |Ab0 | ⩾ 1−kε b0
2 |A| and from the above claim, all the edges incident on A are satisfied by the
b
labeling (Ac, B).
b
3.4.2 Soundness
Let FU : {L + HU | L ∈ Gr(XU , `), L ∩ HU = {0}} → F`2 . FU [L + HU ] can be thought of as a linear
function L + HU → F2 respecting the side conditions. This is again by fixing an arbitrary basis of
L. Define agreement(FU ) as the probability of the following event:
• Select an (` − 1)-dimensional subspace L0 ∈ XU such that L0 ∩ HU = {0} uniformly at random.
– Select `-dimensional subspaces L1 and L2 containing L0 such that L1 ∩ HU = L2 ∩ HU =
{0} uniformly at random.
– Check if FU [L1 + HU ]|L0 = FU [L1 + HU ]|L0 .
The main technical theorem which was conjectured in [15] and proved in [21] is that if
agreement(FU ) is a positive constant, then there is a global linear function g : XU → F2 respecting
the side conditions and a special (not too small) subset S of {L + HU | L ∈ Gr(XU , `), L ∩ HU = {0}}
such that for a constant fraction of elements in S, FU agrees with g. We will not need the details
of this theorem. Instead, we state the main soundness lemma from [15] which crucially used
the aforementioned structural theorem and also the advice strings as mentioned in Remark 3.4.
Theorem 3.14 (Implied by Lemma 4.1 in [15]). For every constant δ > 0, there exist large enough
` k, q ∈ Z+ and β ∈ (0, 1) such that if there is an unfolded assignment A : A → ΣA to Gunfolded such
that for at least δ fraction of U, agreement(FU ) ⩾ δ , FU [L + HU ] = A (U, L) for every L ∈ Gr(XU , `),
then there exists a provers’ strategy which makes the outer verifier accept with probability at least pδ ,
where pδ is independent of k.
Armed with this theorem, we are ready to prove the soundness of the reduction to the
Unique Games instance UGfolded .
Lemma 3.15 (Soundness). Let δ > 0 and fix q ∈ Z+ , β ∈ (0, 1) and ` k as in Theorem 3.14. If
UGfolded is δ -satisfiable then there exists a provers’ strategy which makes the outer verifier accept with
probability at least p δ 4 .
216
Proof. Fix any δ -satisfying assignment (Ac, B), b Ac: A b → Σ, B b : Bb → Σ to the Unique Games
instance UGfolded . We first get a randomized labeling (A , B̃) to Gfolded where A˜ : Ã → ΣA
˜
and B̃ : B → ΣB as follows: We will keep B̃ = B. b For every C ∈ Ã, we pick a random x ∈ RC
and b ∈ {0, 1} and set A˜(C) = Ac(Cx,b ). We now unfold the assignment A˜ to A . Define
FU [L + HU ] = A (U, L) for every L ∈ Gr(XU , `). Note that FU is a random assignment.
Let p(U) denote the probability that an edge in UGfolded is satisfied conditioned on U.
Consider U such that p(U) ⩾ δ2 . By an averaging argument, there are at least a δ /2 fraction of U
such that p(U) ⩾ δ2 .
4
Claim 3.16. EFU [agreement(FU )] ⩾ p(U)
211
− ok (1).
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 16
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
Proof. Fix a particular U. Define a randomized assignment FU0 [L0 ] as follows: Select a random
V ⊆ U conditioned on the event that L0 ⊆ XV . Set FU0 [L0 ] = B(V,
b L0 ). Consider the following two
distributions:
Distribution DU :
• Select V uniformly at random from {V | ((U, L), (V, L0 )) ∈ E for some L, L0 }
• Select L0 uniformly at random from Gr(XV , ` − 1)
• Select L uniformly at random from {L | L ∈ Gr(XU , `) and L0 ⊆ L}
• Let C be the equivalence class such that (U, L) ∈ C, select x ∼ RC as in the edge distribution
E.
b
• Select b ∈ {0, 1} uniformly at random.
Distribution D0U :
• Select L0 uniformly at random from Gr(XU , ` − 1)
• Select V uniformly at random from {V | ((U, L), (V, L0 )) ∈ E, L0 ∈ Gr(XV , ` − 1) and L ∈
Gr(XU , `)}
• Select L uniformly at random from {L | L ∈ Gr(XU , `) and L0 ⊆ L}
• Let C be the equivalence class such that (U, L) ∈ C, select x ∼ RC as in the edge distribution
E.
b
• Select b ∈ {0, 1} uniformly at random.
We have the following lemma from [15].
Lemma 3.17 (Lemma 3.6 in [15]). Consider the two marginal distributions on the pair (V, L0 ), one with
respect to DU and another with respect to DU0 . If 2` β ≤ 18 , then the statistical distance between the two
√
distributions is at most β k · 2`+4 .
In the distribution DU , there is always a constraint between Cx,b and (V, L0 ) in UGfolded .
Moreover, the distribution of (Cx,b , (V, L0 )) is same as the edge distribution E. b Therefore
h i
p(U) = Pr (Ac(Cx,b ), B(V,b L0 )) satisfy the edge (Cx,b , (V, L0 )) .
DU
Rewriting the above equality,
h i
p(U) = Pr σ b L0 ) | σ = Ac(Cx,b ) .
bU |L0 = B(V,
DU
Using Claim 3.10, the distribution of FU [L + HU ], conditioned on x ∈ RC \ (HU + L0 ), is same
as the distribution Ac(Cx,b ) (with appropriate unfolding of it) chosen with respect to DU . As
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 17
A MEY B HANGALE AND S UBHASH K HOT
|RC \ (HU +L0 )| = |RC |/2, for a random x ∈ RC , the event x ∈ RC \ (HU +L0 ) happens with probability
2 . Since we pick an uniformly random x ∈ RC while defining A (C), which in turn defines
1 ˜
FU [L + HU ], we have
p(U) h
b L0 ) ,
i
⩽ E Pr FU [L + HU ]|L0 = B(V,
2 FU DU
Now, h i h i
b L0 ) ≈ Pr FU [L + HU ]|L0 = B(V,
Pr FU [L + HU ]|L0 = B(V, b L0 ) .
DU 0 DU
follows from the closeness of distributions DU and DU0 on (V, L0 ) given by Lemma 3.17 by setting
β √1k (this setting of β is consistent with the setting of β in Theorem 3.14). Conditioned on L0 ,
the distribution of (V, L0 ) in DU0 is same as the distribution we used to assign FU0 [L0 ] and therefore
we get
p(U) 0 0
− ok (1) ⩽ E Pr FU [L + HU ]|L 0 = F [L ] .
U
2 FU L0 ⊆L
Let E1 be the event that p(U) 0 0
4 − ok (1) ⩽ PrL ⊆L [FU [L + HU ]|L = FU [L ]]. By an averaging argument,
0 0
Pr[E1 ] ⩾ P(U)
4 − ok (1). We now fix an FU for which E1 occurs. By another averaging argument,
there is at least a p(U)/8 fraction of L0 ∈ Gr(XU , ` − 1) such that PrL⊇L0 [FU [L + HU ]|L0 = FU0 [L0 ]] ⩾
p(U) 0
8 − ok (1). For each of such L we have,
Pr 0 [FU [L1 + HU ] = FU [L2 + HU ]] = Pr 0 FU [L1 + HU ]|L0 = FU [L2 + HU ]|L0 = FU0 [L0 ]
L1 ,L2 ⊇L L1 ,L2 ⊇L
p(U)2
⩾ − ok (1).
26
Thus overall, we get
p(U)3
Pr [FU [L1 + HU ] = FU [L2 + HU ] | E1 ] ⩾ − ok (1).
L1 ,L2 ⊇L 0 29
Hence,
p(U)4
E [agreement(FU )] ⩾ Pr[E1 ] · Pr [FU [L1 + HU ] = FU [L2 + HU ] | E1 ] ⩾ − ok (1).
FU L1 ,L2 ⊇L 0 211
There is at least a δ /2 fraction of U such that p(U) ⩾ δ /2. This means for at least a δ /2 fraction
4
of U, E[agreement(FU )] ⩾ 2δ15 − ok (1) using the previous claim. Thus, again by an averaging
argument, there exists a fixed {FU | U ∈ U}, coming from unfolding of some assignment A˜,
such that for at least a δ 4 2−16 fraction of U, we have agreement(FU ) ⩾ δ 4 2−16 . The lemma now
follows from Theorem 3.14.
We now prove the main theorem.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 18
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
Proof of Theorem 1.2 Fix δ > 0. We let q, β and ` k be as given in the setting of Theorem 3.14.
Firstly, if we look at the marginal of the edge distribution on A b then it is uniform and hence
the instance is left-regular.3 Now, starting with an instance (X, Eq), we have the following two
guarantees of the reduction.
1. If the instance (X, Eq) is (1 − 2δk )-satisfiable then by Lemma 3.8 and Lemma 3.12, the
Unique Games instance UGfolded has a property that for at least a (1/2) − δ fraction of the
vertices in A,
b all the edges incident on them are satisfied.
2. Consider the other case in which the instance (X, Eq) is at most s-satisfiable where s < 1.
If the Unique Games instance UGfolded has a δ -satisfying assignment, then by Lemma 3.15
there is a provers’ strategy which can make the outer verifier accept with probability at
q
least p δ 4 2−Ω(β k/2 ) for large enough k. This contradicts Theorem 3.3 and hence in this
216
case, UGfolded has no assignment that satisfies a δ fraction of the edges.
Since by Theorem 3.2, distinguishing between a given instance (X, Eq) being at least (1 − 2δk )-
satisfiable or at most s-satisfiable is NP-hard, this proves our main theorem.
4 Independent set in degree-d graphs
We consider a weighted graph H = (V, E) where the sum of the weights of all the vertices is 1
and also sum of the weights of all the edges is also 1. For S ⊆ V , we will denote the total weight
of the vertices in S by w(S).
Definition 4.1. A graph H is (δ , ε)-dense if for every S ⊆ V (H) with w(S) ⩾ δ , the total weight
of the edges inside S is at least ε.
For ρ ∈ [−1, 1] and β ∈ [0, 1], the quantity Γρ (β ) is defined as:
Γρ (β ) := Pr[X ≤ φ −1 (β ) ∧Y ≤ φ −1 (β )],
where X and Y are jointly distributed normal Gaussian random variables with co-variance ρ
and φ is the cumulative density function of a normal Gaussian random variable.
We will prove the following theorem.
Theorem 4.2. Fix ε > 0, p ∈ 0, 12 , then for all sufficiently small δ > 0, there exists a polynomial-time
reduction from an instance of left-regular Unique Games, G(A, B, E, [L], {πe }e∈E ), to a graph H such that
1. If sval(G) ⩾ c, then there is an independent set of weight c · p in H.
p
2. If val(G) ⩽ δ , then H is (β , Γρ (β ) − ε) dense for every β ∈ [0, 1] and ρ = − p−1 .
The reduction is exactly the same as the one in [4]. We will only show the completeness (1)
from Theorem 4.2 here. The soundness of this theorem is proved in [4]. This theorem will imply
Theorem 1.3 using a randomized sparsification technique of [4] to convert the weighted graph
into a bounded-degree unweighted graph.
3The edges have weights, but it can be made an unweighted left-regular instance by adding multiple edges
proportional to its weight with the same constraint.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 19
A MEY B HANGALE AND S UBHASH K HOT
Let G(A, B, E, [L], {πe }e∈E ) be an instance of Unique Games. The distribution of edges in
H is as follows:
• Select u ∈ B uniformly at random.
• Select two neighbors v1 and v2 of u independently and uniformly at random. Let π1
and π2 be the constraints between (u, v1 ) and (u, v2 ) respectively.
• Select x, y ∈ {0, 1}L , such that for each i ∈ [L], the pair (xi , yi ) is sampled independently
from the distribution D.
• Output the edge (v1 , x ◦ π1 ), (v2 , y ◦ π2 ).
Figure 3: Reduction from UG to Independent Set from [4].
4.1 The AKS reduction
Consider the distribution D on (a, b) ∈ {0, 1}2 such that Pr[a = b = 1] = 0 and each bit is p-biased,
i. e., Pr[b = 1] = Pr[b = 1] = p. For a string x ∈ {0, 1}L and a permutation π : [L] → [L], define
x ◦ π ∈ {0, 1}L as (x ◦ π)i = xπ(i) for all i ∈ [L].
Let G(A, B, E, [L], {πe }e∈E ) be an instance of Unique Games which is regular on the A side.
We convert it into a weighted graph H. The vertex set of H will be A × {0, 1}L . Weight of a vertex
µ p (x)
(v, x) where v ∈ A and x ∈ {0, 1}L is |A| , where µ p (x) := p|x| (1 − p)L−|x| . The edge distribution is
given in Figure 3.
Lemma 4.3 (Completeness). If sval(G) ⩾ c, then there is an independent set in H of weight c · p.
Proof. Fix an assignment ` : A ∪ B → Σ that gives sval(G) ⩾ c. Let A0 ⊆ A be the set of vertices
such all the edges incident on A0 are satisfied by `. We know that |A0 | ⩾ c · |A|. Consider the
following subset of vertices in H.
I = {(v, x) | v ∈ A0 , x`(v) = 1}.
Firstly, the total weight of set I is c · p. We show that I is in fact an independent set in H.
Suppose for contradiction, there exists an edge (v1 , x), (v2 , y) in H with both endpoints are in
I. Let u be the common neighbor of v1 , v2 (one such u must exist). If we let π1 and π2 be the
permutation constraints between (u, v1 ) and (u, v2 ), then the conditions for being an edge implies
that (xπ1 (`(u)) , yπ2 (`(u)) ) should have a support in D. Since all the edges incident on A0 are satisfied,
πi (`(u)) = `(vi ) for i ∈ {1, 2}. Therefore, (x`(v1 ) , y`(v2 ) ) is also supported in D and hence both
cannot be 1 which implies that both cannot belong to I.
Lemma 4.4 (Soundness [4]). For every constant ε > 0, if H is not (β , Γρ (β ) − ε)-dense for some
p
β ∈ [0, 1] and ρ = − p−1 , then G is δ -satisfiable for δ := δ (ε, p) > 0.
Lemma 4.3 and Lemma 4.4 prove Theorem 4.2.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 20
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
5 Maximum Acyclic Subgraph
In this section we state the reduction from [17] and analyze the completeness of the reduction.
Given a directed graph H = (V, E), we will denote by Val(H) the fraction of edges in the
maximum sized acyclic subgraph of H. We need the following definition.
Definition 5.1. A t-ordering of a directed graph H = (V, E) consists of a map O : V → [t]. The
value of a t-ordering O is given by
1
Valt (O) = Pr [O(a) < O(b)] + · Pr [O(a) = O(b)].
(a,b)∈E 2 (a,b)∈E
Define Valt (H) as:
Valt (H) = max Valt (O).
O
The following lemma [17] will be crucial in the reduction from Unique Games to the
Maximum Acyclic Subgraph problem.
Lemma 5.2 ([17]). Given η > 0 and a positive integer t, for every sufficiently large m, there exists a
weighted directed acyclic graph H(V, E) on m vertices along with a distribution D on the orderings
{O : V → [m]} such that:
1. For every u ∈ V and i ∈ [m], PrO∼D [O(u) = i] = m1 .
2. For every directed edge (a → b), PrO∼D [O(a) < O(b)] ⩾ 1 − η.
3. Valt (H) ⩽ 12 + η.
The reduction is given in Figure 4. For a string x ∈ [q]L and a permutation π : [L] → [L], define
x ◦ π ∈ [q]L by (x ◦ π)i = xπ(i) for all i ∈ [L].
Lemma 5.3 (Completeness). For small enough ε, η > 0, if the Unique Games instance G has sval(G) ⩾ c
1 1
then Val(G) ⩾ c · (1 − 2ε)(1 − η) + (1 − c) · 2 − 2m
Proof. Fix an assignment ` : A ∪ B → Σ that gives sval(G) ⩾ c. Let A0 ⊆ A be the set of vertices
such that its edges are satisfied by `, we know that |A0 | ⩾ c · |A|. Consider the following m
ordering O : B × [m]L → [m] of the vertices of G: O(v, x) = x`(v) . We will show that Valm (O) ⩾
c(1 − 2ε)(1 − η) + (1 − c) · 21 − 2m
1
. This will prove the lemma.
Val(G) ⩾ Valm (O) ⩾ Pr[O((v1 , x̃ ◦ π1 ) < O(v2 , ỹ ◦ π2 )]
= Pr[x̃π1 (`(v1 )) < ỹπ2 (`(v2 )) ]
⩾ c · Pr[x̃π1 (`(v1 )) < ỹπ2 (`(v2 )) | u ∈ A0 ]
/ A0 ].
+ (1 − c) · Pr[x̃π1 (`(v1 )) < ỹπ2 (`(v2 )) | u ∈ (5.1)
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 21
A MEY B HANGALE AND S UBHASH K HOT
Let G(A, B, E, [L], {πe }e∈E ) be an instance of Unique Games. Fix a graph H([m], EH ) from
Lemma 5.2 with parameters η > 0 and t ∈ Z+ , along with the distribution D. Construct a
weighted directed graph G on B × [m]L with the following distribution on the edges:
• Select u ∈ A uniformly at random.
• Select two neighbors v1 and v2 of u uniformly at random. Let π1 and π2 be the
constraints between (u, v1 ) and (u, v2 ) respectively.
• Pick an edge e = (a, b) ∈ EH at random from the graph H.
• Select x, y ∈ [m]L , such that for each i ∈ [L], the pair (xi , yi ) is sampled independently
as follows:
– sample O ∼ D, set xi = O(a) and yi = O(b).
• Perturb x and y as follows: for each i ∈ [L], with probability (1 − ε), set x̃i = xi , with
probability ε set x̃i to be uniformly at random from [m]. Do the same thing for y
independently to get ỹ.
• Output the directed edge (v1 , x̃ ◦ π1 ) → (v2 , ỹ ◦ π2 ).
Figure 4: Reduction from UG to Max-Acyclic Graph from [17].
Now, if u ∈ A0 then π1 (`(v1 )) = π2 (`(v2 )) = `(u) and hence,
Pr[x̃π1 (`(v1 )) < ỹπ2 (`(v2 )) | u ∈ A0 ] = Pr[x̃`(u) < ỹ`(u) ]
⩾ (1 − 2ε) · E Pr [O(a) < O(b)]
(a,b)∈EH O∼D
⩾ (1 − 2ε)(1 − η). (5.2)
Now, we can show that Pr[x̃π1 (`(v1 )) < ỹπ2 (`(v2 )) | u ∈ / A0 ] is at least (1 − 2ε)(1 − η) as above if
π1 (`(v1 )) = π2 (`(v2 )). If π1 (`(v1 )) 6= π2 (`(v2 )) then x̃π1 (`(v1 )) and ỹπ1 (`(v1 )) are uncorrelated and are
(m)
distributed uniformly in [m]. Therefore, Pr[x̃π1 (`(v1 )) < ỹπ2 (`(v2 )) | u ∈ / A0 ] = m22 = 12 − 2m
1
. Thus, for
small enough ε and η, we have the following lower-bound.
0 1 1 1 1
Pr[x̃π1 (`(v1 )) < ỹπ2 (`(v2 )) | u ∈
/ A ] ⩾ min (1 − 2ε)(1 − η), − ⩾ − . (5.3)
2 2m 2 2m
Plugging equation (5.2) and equation (5.3) into equation (5.1), we get
1 1
Val(G) ⩾ c · (1 − 2ε)(1 − η) + (1 − c) · − .
2 2m
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 22
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
The following soundness of the reduction is shown in [17].
Lemma 5.4 (Soundness [17]). If the Unique Games instance G has val(G) ⩽ δ then Val(G) ⩽
1 0 0
2 + η + ot (1) + δ , where δ → 0 as δ → 0.
Proof of Theorem 1.4 For every ε 0 < 0, setting ε, η, δ > 0 small enough constants and m large
enough, in the completeness of the reduction we have a maximum acyclic subgraph of size at
least 2c + 12 − ε 0 , whereas in the soundness, it is at most 12 + ε 0 . Since by Theorem 1.2, it is NP-hard
to distinguish between sval(G) ⩾ 12 − δ and val(G) ⩽ δ , we get that it is NP-hard to approximate
1/2+ε 0 2
the size of the Maximum Acyclic Subgraph within a factor of 1/4+1/2−ε 0 −δ /2 ≈ 3 .
Remark 5.5. Instead of sval(G) = 12 , if we only have val(G) = 12 , then the same construction
and the labeling from Lemma 5.3 gives Val(G) ⩾ 58 . To see this, fix an assignment ` : A ∪ B → Σ
which gives val(G) ⩾ 12 . Let αu denote the fraction of edges incident on u that are satisfied by `.
Therefore, we have val(G) = Eu∈A [αu ] = 21 . Using a similar analysis as in the completeness of
2
the reduction, we have Val(G) ⩾ Eu∈A [αu2 · (1 − 2ε)] + Eu∈A [(1 − αu2 ) · 12 ] ⩾ (1 − 2ε) E[ 12 + α2u ]. By
the Cauchy–Schwarz inequality E[αu2 ] ⩾ (E[αu ])2 = 14 and hence Val(G) ⩾ (1 − 2ε) · 58 . This along
with the soundness lemma gives the NP-hardness of 45 .
6 Predicates supporting Pairwise Independence
In this section, we prove Theorem 1.5.
6.1 The Austrin-Mossel reduction
Let D be a distribution on P−1 (1) which is balanced and pairwise independent. For a string
x ∈ [q]L and a permutation π : [L] → [L], define x ◦ π ∈ [q]L such that (x ◦ π)i = xπ(i) for all i ∈ [L].
Let G(A, B, E, [L], {πe }e∈E ) be an instance of Unique Games. We convert it into a P-CSP
instance I as follows. The variable set of I is B × [q]L . The variables are folded in the sense that for
every assignment f : B × [q]L → [q] to the variables, we enforce that for every v ∈ B, x ∈ [q]L and
α ∈ [q],
f (v, x + α L ) = f (v, x) + α,
where additions are (mod q).
The distribution on the constraints is given in Figure 5:
Lemma 6.1 (Completeness). If sval(G) ⩾ c, the I is (c − ε)-satisfiable.
Proof. Fix an assignment ` : A ∪ B → Σ that gives sval(G) ⩾ c. Let A0 ⊆ A be the set of vertices
such that all the edges incident on A0 are satisfied by `, we know that |A0 | ⩾ c · |A|. Thus, with
probability at least c, u ∈ A0 and all edges attached to it are satisfied by `. Consider the following
assignment f to the variables of I : For a variable (v, x), we assign f (v, x) = x`(v) .
Conditioned on u ∈ A0 , we will show that ( f (v1 , x1 ◦ π1 ), f (v2 , x2 ◦ π2 ), . . . , f (vk , xk ◦ πk )) ∈ P−1 (1)
with probability (1 − ε) and this will prove the lemma. Now, ( f (v2 , x2 ◦ π2 ), . . . , f (vk , xk ◦ πk )))
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 23
A MEY B HANGALE AND S UBHASH K HOT
Let G(A, B, E, [L], {πe }e∈E ) be an instance of Unique Games.
• Select u ∈ A uniformly at random.
• Select k neighbors {v1 , v2 , . . . , vk } of u uniformly at random. Let π j be the constraint
between (u, v j ) for all j ∈ [k].
• Select x1 , x2 , . . . , xk ∈ [q]L , such that for each i ∈ [L] sample (xi1 , xi2 , . . . , xik ) independently
as follows:
– with probability (1 − ε), (xi1 , xi2 , . . . , xik ) is sampled from the distribution D.
– with probability ε, (xi1 , xi2 , . . . , xik ) is sampled from [q]k uniformly at random.
• Output the constraint ((v1 , x1 ◦ π1 ), (v2 , x2 ◦ π2 ), . . . , (vk , xk ◦ πk )).
Figure 5: Reduction from UG to a P-CSP instance I from [6].
is same as ((x1 ◦ π1 )`(v1 ) , (x2 ◦ π2 )`(v2 ) , . . . , (xk ◦ πk )`(vk ) ), which in turns equals (xπ1 1 (`(v1 ) , xπ2 2 (`(v2 ) , . . . ,
xπk k (`(vk ) ). Since ` satisfies all the edges (u, vi ), we have that for all j ∈ [k], π j (`(v j )) = `(u) =: i for
some i ∈ [L]. Therefore we get ( f (v1 , x1 ◦ π1 ), f (v2 , x2 ◦ π2 ), . . . , f (vk , xk ◦ πk )) = (xi1 , xi2 , . . . , xik ), and
according to the distribution, it belongs to P−1 (1) with probability (1 − ε).
We have the following soundness of the reduction.
−1
Lemma 6.2 (Soundness [6]). If the instance I is P qk(1) + η -satisfiable, then G is δ := δ (η, ε, k, q) > 0
satisfiable, where η → 0 as δ → 0.
The completeness and soundness of the reduction, along with our main theorem, imply
Theorem 1.5.
Acknowledgements. We would like to thank all the anonymous reviewers for their comments
which helped in improving the presentation significantly.
References
[1] Sanjeev Arora, László Babai, Jacques Stern, and Z Sweedyk: The hardness of approximate
optima in lattices, codes, and systems of linear equations. J. Comput. System Sci., 54(2):317–
331, 1997. Preliminary version in STOC’93. [doi:10.1006/jcss.1997.1472] 2
[2] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof
verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998.
Preliminary version in FOCS’92. [doi:10.1145/278298.278306] 9
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 24
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
[3] Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: A new char-
acterization of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in FOCS’92.
[doi:10.1145/273865.273901] 9
[4] Per Austrin, Subhash A. Khot, and Muli Safra: Inapproximability of vertex cover
and independent set in bounded degree graphs. Theory of Computing, 7(3):27–43, 2011.
[doi:10.4086/toc.2011.v007a003] 4, 19, 20
[5] Per Austrin, Rajsekar Manokaran, and Cenny Wenner: On the NP-hardness of approx-
imating ordering-constraint satisfaction problems. Theory of Computing, 11(10):257–283,
2015. [doi:10.4086/toc.2015.v011a010] 4
[6] Per Austrin and Elchanan Mossel: Approximation resistant predicates from pairwise
independence. Comput. Complexity, 18(2):249–271, 2009. [doi:10.1007/s00037-009-0272-6] 5,
24
[7] Nikhil Bansal, Anupam Gupta, and Guru Guruganesh: On the Lovász theta function for
independent sets in sparse graphs. SIAM J. Comput., 47(3):1039–1055, 2018. Preliminary
version in STOC’15. [doi:10.1137/15M1051002] 4
[8] Nikhil Bansal and Subhash A. Khot: Inapproximability of hypergraph vertex cover and
applications to scheduling problems. In Proc. 37th Internat. Colloq. on Automata, Languages,
and Programming (ICALP’10), pp. 250–261. Springer, 2010. [doi:10.1007/978-3-642-14165-
2_22] 4
[9] Boaz Barak, Siu On Chan, and Pravesh K. Kothari: Sum of squares lower bounds
from pairwise independence. In Proc. 47th STOC, pp. 97–106. ACM Press, 2015.
[doi:10.1145/2746539.2746625] 5
[10] Boaz Barak, Pravesh K. Kothari, and David Steurer: Small-Set Expansion in Short-
code Graph and the 2-to-2 Conjecture. In Proc. 10th Innovations in Theoret. Comp. Sci.
conf. (ITCS’19), pp. 9:1–12. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019.
[doi:10.4230/LIPIcs.ITCS.2019.9] 6
[11] Amey Bhangale, Rajiv Gandhi, Mohammad Taghi Hajiaghayi, Rohit Khandekar, and Guy
Kortsarz: Bi-covering: Covering edges with two small subsets of vertices. SIAM J. Discr.
Math., 31(4):2626–2646, 2017. [doi:10.1137/16M1082421] 4
[12] Amey Bhangale and Subhash A. Khot: UG-hardness to NP-hardness by losing half. In Proc.
34th Comput. Complexity Conf. (CCC’19), pp. 3:1–20. Schloss Dagstuhl–Leibniz-Zentrum
fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.3] 1
[13] Siu On Chan: Approximation resistance from pairwise-independent subgroups. J. ACM,
63(3):27:1–32, 2016. [doi:10.1145/2873054] 4, 5
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 25
A MEY B HANGALE AND S UBHASH K HOT
[14] Irit Dinur, Subhash A. Khot, Guy Kindler, Dor Minzer, and Muli Safra: On non-optimally
expanding sets in Grassmann graphs. In Proc. 50th STOC, pp. 940–951. ACM Press, 2018.
[doi:10.1145/3188745.3188806] 2, 3, 4, 6, 7
[15] Irit Dinur, Subhash A. Khot, Guy Kindler, Dor Minzer, and Muli Safra: Towards a
proof of the 2-to-1 games conjecture? In Proc. 50th STOC, pp. 376–389. ACM Press, 2018.
[doi:10.1145/3188745.3188804] 2, 3, 4, 7, 9, 10, 11, 12, 13, 16, 17
[16] Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy: Interac-
tive proofs and the hardness of approximating cliques. J. Comput. System Sci., 43(2):268–292,
1996. [doi:10.1145/226643.226652] 9
[17] Venkatesan Guruswami, Rajsekar Manokaran, and Prasad Raghavendra: Beating the
random ordering is hard: Inapproximability of maximum acyclic subgraph. In Proc. 49th
FOCS, pp. 573–582. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.51] 2, 4, 5, 21, 22, 23
[18] Subhash A. Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC,
pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017] 2, 8
[19] Subhash A. Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell: Optimal
inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput.,
37(1):319–357, 2007. [doi:10.1137/S0097539705447372] 2
[20] Subhash A. Khot, Dor Minzer, and Muli Safra: On independent sets, 2-to-2
games, and Grassmann graphs. In Proc. 49th STOC, pp. 576–589. ACM Press, 2017.
[doi:10.1145/3055399.3055432] 2, 3, 4, 7, 10
[21] Subhash A. Khot, Dor Minzer, and Muli Safra: Pseudorandom sets in Grassmann graph
have near-perfect expansion. In Proc. 59th FOCS, pp. 592–601. IEEE Comp. Soc., 2018.
[doi:10.1109/FOCS.2018.00062] 2, 3, 4, 6, 7, 13, 16
[22] Subhash A. Khot and Assaf Naor: Approximate kernel clustering. Mathematika, 55(1–
2):129–165, 2009. Preliminary version in FOCS’08. [doi:10.1112/S002557930000098X]
2
[23] Subhash A. Khot and Oded Regev: Vertex cover might be hard to approximate to within
2 − ε. J. Comput. System Sci., 74(3):335–349, 2008. [doi:10.1016/j.jcss.2007.06.019] 2, 4
[24] Subhash A. Khot, Madhur Tulsiani, and Pratik Worah: A characterization of
strong approximation resistance. In Proc. 46th STOC, pp. 634–643. ACM Press, 2014.
[doi:10.1145/2591796.2591817] 2
[25] Subhash A. Khot and Nisheeth K. Vishnoi: The Unique Games Conjecture, integrality gap
for cut problems and embeddability of negative-type metrics into `1 . J. ACM, 62(1):8:1–23,
2015. [doi:10.1145/2629614] 2
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 26
UG- HARDNESS TO NP- HARDNESS BY L OSING H ALF
[26] Alantha Newman: The maximum acyclic subgraph problem and degree-3 graphs. In Proc.
4th Internat. Workshop on Approximation Algorithms for Combinat. Opt. Probl. (APPROX’01),
pp. 147–158. Springer, 2001. [doi:10.1007/3-540-44666-4_18] 4
[27] Prasad Raghavendra: Optimal algorithms and inapproximability results for every CSP?
In Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414] 2, 5
[28] Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998.
[doi:10.1137/S0097539795280895] 10
AUTHORS
Amey Bhangale
Assistant professor
University of California, Riverside
California, USA
bhangale cs ucr edu
https://www.cs.ucr.edu/~bhangale/
Subhash Khot
Professor
Courant Institute of Mathematical Sciences
New York University, USA
khot cs nyu edu
https://cs.nyu.edu/~khot/
ABOUT THE AUTHORS
Amey Bhangale is an Assistant Professor in the Computer Science Department at
the University of California, Riverside.
Amey got his undergraduate degree from VJTI, Mumbai. In the final year of his
undergraduate studies, he met Prof. Rajiv C. Gandhi, who was visiting Mumbai
in 2010/11 on a Fulbright scholarship and taught a course on approximation
algorithms at VJTI. This encounter influenced Amey to pursue research in the
theory of computing.
Amey graduated from Rutgers University in 2017 under the supervision of
Swastik Kopparty. He spent two wonderful years in Israel where he was a
postdoctoral fellow at the Weizmann Institute of Science, hosted by Irit Dinur.
He is interested in approximation algorithms, hardness of approximation and
the analysis of Boolean functions. He enjoys playing and watching tennis (and
hardly ever says no to anyone who invites him to play tennis).
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 27
A MEY B HANGALE AND S UBHASH K HOT
Subhash Khot is a Professor in the Computer Science Department at New York
University. He has a Ph. D. from Princeton University, completed in 2003 under
the supervision of Sanjeev Arora.
His teacher and mentor at Vyankatrao Highschool, Mr. Vaman G. Gogate played
a decisive role in directing his attention to mathematics. If not for Mr. Gogate’s
guidance and some fortuitous turn of events, the chance of someone from the
remote town of Ichalkaranji pursuing mathematical research was strictly nil.
Subsequently, Mr. Gogate also mentored Amit Deshpande and Raghav Kulkarni
(CS theorists) and Abhijit Gadde (string theorist). He is in touch with all his past
students and continues to provide guidance on all aspects of life.
T HEORY OF C OMPUTING, Volume 18 (5), 2022, pp. 1–28 28