# A Chronology of Set Cover Inapproximability Results

Erika Melder

## Abstract

It is well-known that an algorithm exists which approximates the NP-complete
problem of Set Cover within a factor of ln(n), and it was recently proven that
this approximation ratio is optimal unless P = NP. This optimality result is
the product of many advances in characterizations of NP, in terms of
interactive proof systems and probabilistically checkable proofs (PCP), and
improvements to the analyses thereof. However, as a result, it is difficult to
extract the development of Set Cover approximation bounds from the greater
scope of proof system analysis. This paper attempts to present a chronological
progression of results on lower-bounding the approximation ratio of Set Cover.
We analyze a series of proofs of progressively better bounds and unify the
results under similar terminologies and frameworks to provide an accurate
comparison of proof techniques and their results. We also treat many
preliminary results as black-boxes to better focus our analysis on the core
reductions to Set Cover instances. The result is alternative versions of
several hardness proofs, beginning with initial inapproximability results and
culminating in a version of the proof that ln(n) is a tight lower bound.

##  1 Introduction

###  1.1 The Set Cover Problem

The optimization problem Set Cover is defined as follows:

######  Definition 1.1 (Set Cover).

Given a set $U$ (a _universe_) of $n$ elements and sets
$S_{1},S_{2},\dots,S_{k}\subseteq U$, with the guarantee that every element of
$U$ is in at least one of the $S_{i}$, find a minimal collection of subsets
whose union is $U$.

This problem is well-known to be NP-complete [10]. As such, the best efficient
generic solution we can hope for is an approximation algorithm, which finds a
solution to any instance with no more than some function of the smallest
possible number of sets. The approximation version of Set Cover is defined as
follows:

######  Definition 1.2 (Set Cover Approximation).

For a Set Cover instance $\mathcal{S}$, let $\text{OPT}(\mathcal{S})$ be the
number of sets $S_{i}$ used in a minimal solution of $\mathcal{S}$. An
algorithm is said to $a(n)$-approximate Set Cover, where $a$ is a function of
the number of universe elements $n$ in $\mathcal{S}$, if it can generate a
solution to any Set Cover instance $\mathcal{S}$ using at most
$a(n)\cdot\text{OPT}(\mathcal{S})$ sets.

In particular, we are interested in approximations where $a(n)$ is minimized,
and which run in polynomial time.

The lower bounds on time complexity of these approximations are well-studied.
Notably, several algorithms exist which are proven to $\ln n$-approximate Set
Cover [9, 11]. On the other hand, there have been several results proving that
efficient approximation is impossible within certain thresholds. The proofs of
these impossibility results are nontrivial, and rely heavily on the machinery
of interactive proof systems [8, 3] and the subsequent framework of
_probabilistically checkable proofs_ (PCP) [1, 2]. This paper will trace key
developments in proofs of Set Cover inapproximability, beginning with the
initial inapproximability result of Lund and Yannakakis [12], and progressing
chronologicaly to explore what techniques were necessary to arrive at the
current results. The ultimate goal will be to prove the following:

######  Theorem 1.3 (Inapproximability of Set Cover).

Unless $\text{P}=\text{NP}$, Set Cover cannot be approximated within $c\ln n$
for any $0<c<1$.

###  1.2 A Note on the Timeline

The papers are presented in chronological order of their results, but the
years of publication listed are those of the respective journals that the
papers are ultimately published in. Much of the work on this problem was done
collaboratively, with initial results sparking debate and further work before
those initial results were printed, and with several papers receiving
revisions to reflect newly-obtained results of their successors reliant upon
the initial results. For ease of reference, the papers in the main portion of
this paper will be referred to by the date that they were published, though
this will cause some of these papers to seemingly appear out of order.
Appendix Appendix A: Chronological Timelines presents timelines of these
papers arranged by rough order of initial results, in the form of a rough
sketch of which results were strictly necessary to produce others.

##  2 Lund and Yannakakis, 1994 [12]

An initial result was the following theorem:

######  Theorem 2.1.

Unless $\text{NP}\subseteq\text{DTIME}(n^{\text{polylog}(n)})$, Set Cover
cannot be approximated within a ratio of $c\log n$ for any positive
$c<\frac{1}{4}$.

The proof of this result is nontrivial, relying on a modification of a Feige-
Lovász proof system for SAT, originally developed in [7]. This section
presents a simplified, descriptive version of the proof. We omit complex
proofs of background information and treat them as black boxes to present only
the core logic behind the key result.

###  2.1 Preliminary Constructions

In this section, we will describe two critical constructions which are
necessary to complete the proof.

####  2.1.1 Feige-Lovász Verifier for SAT

An interactive proof system is defined as follows:

######  Definition 2.2 (Interactive Proof System).

Fix an input size $n$. A _two-prover, one-round interactive proof system_ is a
system which takes in an input of size $n$ and outputs Yes or No. It has two
kinds of components: a _verifier_ and _provers_.

  * •

A _verifier_ consists of the following:

    * –

A finite input alphabet $\Sigma$.

    * –

A finite set $R$ of random seeds of length $\mathcal{O}(\text{polylog}(n))$.

    * –

A finite set of queries of length $\mathcal{O}(\text{polylog}(n))$ that can be
asked to each prover. In this case, there will be two provers, so the verifier
will have two such sets, $Q_{1}$ and $Q_{2}$.

    * –

A finite set of answers of length $\mathcal{O}(\text{polylog}(n))$ that can be
received from each prover. Again, there will be two such sets in this case,
$A_{1}$ and $A_{2}$.

    * –

A polynomial-time computable function $f:\Sigma^{n}\times R\to Q_{1}\times
Q_{2}$, which generates a pair of queries based on a random seed and an input.

    * –

A polynomial-time computable function $\Pi:\Sigma^{n}\times R\times
A_{1}\times A_{2}\to\\{\textsf{Yes},\textsf{No}\\}$ which determines the
output based on the input, seed, and query answers.

  * •

The $i$th _prover_ in the system is a function from $Q_{i}$ to $A_{i}$.

The verifier takes an input $x\in\Sigma^{n}$, and selects a random seed $r$
uniformly randomly from $R$. It computes $f(x,r)$ and receives a query pair
$(q_{1},q_{2})$. It then provides these two queries to the provers, who in
turn provide the answer pair $(a_{1},a_{2})$; this process of sending queries
and receiving answers is known as _message passing_ , and the “one-round”
designation of the prover refers to using only one iteration of message
passing. After this, the verifier computes $\Pi(x,r,a_{1},a_{2})$, and accepts
or rejects the input based on the result. A diagram of the process can be seen
in Figure 2.1.

Input $\varphi$Query $q_{1}$Query $q_{2}$Random Seed $r$Prover $P_{1}$Prover
$P_{2}$Answer $a_{1}$Answer
$a_{2}$$f(\varphi,r)$$\Pi(\varphi,r,a_{1},a_{2})$Output Yes/No

Figure 2.1: A standard two-prover one-round proof system.

A common example of such a proof system would be a probabilistic 3SAT
verifier. Such a verifier takes in a formula $\varphi$. It selects a random
clause $C$ and a random integer $i\in\\{1,2,3\\}$. The verifier asks prover 1
what assignment of variables, if any, satisfies clause $C$, and then asks
prover 2 for an assignment of the $i$th variable of $C$, either 0 or 1
(corresponding to False and True). Note here that the answer sets would be
$A_{1}=\\{0,1\\}^{3}$ and $A_{2}=\\{0,1\\}$. After receiving both answers, the
verifier then outputs Yes if and only if both verifiers agree on their
assignment of variable $i$. It is clear that this system is not deterministic;
observe that no strategy of the provers can correctly classify both the
formula $x_{1}\lor x_{2}\lor x_{3}$ and the formula $\neg x_{1}\lor\neg
x_{2}\lor\neg x_{3}$ with probability 1.

Lund and Yannakakis, building on the work of Feige and Lovász in [7],
described a two-prover, one-round interactive proof system for SAT in [12],
which was subsequently used as a component of the gap-preserving reduction to
prove Set Cover inapproximable. Their result is as follows:

######  Theorem 2.3 (Proof System for SAT).

There exists a two-prover, one-round interactive proof system for SAT that
takes an input formula $\varphi$ and has the following properties:

  * •

If $\varphi\in\textsc{SAT}$, then there exists a pair of provers such that the
verifier will always output Yes.

  * •

If $\varphi\notin\textsc{SAT}$, then for all pairs of provers, the verifier
accepts with probability at most $\frac{1}{n}$, where $n$ is the input size.

  * •

For a fixed prover $P_{i}$, the verifier’s queries to that prover are
uniformly random across the possible query set $Q_{i}$.

  * •

The choice of $q_{2}$ is independent of the choice of $q_{1}$.

  * •

For any pair $(r,a_{1})$ of a seed and an answer from prover 1, there is at
most one $a_{2}\in A_{2}$ that would result in a pair of accepting answers
(i.e. $\Pi(\varphi,r,a_{1},a_{2})=\textsf{Yes}$).

  * •

$|Q_{1}|=|Q_{2}|$, meaning that the verifier has the same number of potential
queries for each prover. (This can be assumed without loss of generality.)

We will use the existence of such a proof system as a cornerstone of the
reduction. Note that the input size is fixed for verifiers of this nature, so
we simply select an appropriate verifier to accommodate the size of our input.
In this case, the size may be considered to be the number of literals in the
formula.

####  2.1.2 Special Set System

Another critical construction is a special set system (which is a variant of
an $(n,k)$-universal set as defined in [15] and described in Definition 5.1),
defined as follows:

######  Definition 2.4 (Special Set System).

A _special set system_ $\beta_{m,d}=\\{B;C_{1},C_{2},\dots,C_{m}\\}$ consists
of the following:

  * •

A set $B$, referred to as the _universe_ of the set system.

  * •

$m$ subsets $C_{1},C_{2},\dots,C_{m}\subseteq B$, referred to as _special
sets_.

Additionally, it has the following property, known as its _special property_ :

  * •

No collection of $d$ or fewer indices $i\in\\{1,2,\dots,m\\}$ satisfies
$\bigcup_{i}D_{i}=B$, where $D_{i}=C_{i}$ or $\overline{C_{i}}$.

Lund and Yannakakis prove the following lemma:

######  Lemma 2.5.

For any positive integers $m$ and $d$, there exists a special set system
$\beta_{m,d}$ with those parameters, and its universe $B$ has
$|B|=\mathcal{O}(2^{2d}m^{2})$. Moreover, such a set system can be explicitly
constructed for any $m,d$ in $\text{DTIME}(n^{\text{polylog}(n)})$.

The construction given by Lund and Yannakakis results in a set system whose
elements are bit-vectors. For the purposes of the proof, the actual elements
contained in the set system are irrelevant; only the special property is
required.

One crucial corollary follows from taking the contrapositive of the special
property:

######  Corollary 2.6.

Let $\beta_{m,d}=\\{B;C_{1},C_{2},\dots,C_{m}\\}$ be a special set system, and
let
$A\subseteq\\{C_{1},\dots,C_{m},\overline{C_{1}},\dots,\overline{C_{m}}\\}$ be
a collection of $C_{i}$’s and their complements, with $|A|\leq d$. Then for
some $j\in\\{1,2,\dots,m\\}$, both $C_{j}$ and $\overline{C_{j}}$ are in $A$.

We will use this corollary to ensure the presence of the gap in our reduction.

###  2.2 The Proof

The remainder of Section 2 will be devoted to proving the following lemma
using the proof structure of [12], and highlighting the critical techniques
therein.

######  Lemma 2.7.

For a Set Cover instance $\mathcal{S}$, let $\textsf{OPT}(\mathcal{S})$ denote
the smallest number of sets needed to fully cover the universe of
$\mathcal{S}$. Then, for any CNF formula $\varphi$, we can construct an
instance of Set Cover $\mathcal{S}_{\varphi}$ in
$\text{DTIME}(n^{\text{polylog}(n)})$ such that:

  * •

If $\varphi\in\textsc{SAT}$, then
$\textsf{OPT}(\mathcal{S}_{\varphi})=|Q_{1}|+|Q_{2}|$, where $Q_{i}$ is the
set of queries that may be asked to prover $i$ in an appropriate Feige-Lovász
SAT proof system for $\varphi$, and

  * •

If $\varphi\notin\textsc{SAT}$, then $\textsf{OPT}(\mathcal{S}_{\varphi})\geq
c\log N(|Q_{1}|+|Q_{2}|)$ for any $0<c<\frac{1}{4}$.

This would complete a gap-inducing reduction from SAT to Set Cover. Because
SAT is NP-complete, this would prove that Set Cover is inapproximable within
$c\log(n)\cdot\textsf{OPT}$ for any $0<c<\frac{1}{4}$, unless
$\text{NP}\subseteq\text{DTIME}(n^{\text{polylog}(n)})$. The second
possibility is because the special set system construction can be done in
$\text{DTIME}(n^{\text{polylog}(n)})$ as shown in [12]. This would
subsequently prove Theorem 2.1.

####  2.2.1 Initial Setup

Consider an input formula $\varphi$ of length $n$, and an appropriate Feige-
Lovász verifier for SAT. Recall that the verifier consists of sets
$R,Q_{1},Q_{2},A_{1},$ and $A_{2}$, and functions $f$ and $\Pi$, as in
Definition 2.2.

Construct the special set system $\beta_{m,d}$, where $m=|A_{2}|$ and $d$ is
an even integer to be determined later. Since $m=|A_{2}|$, we can associate
each special set $C_{a}$ with a corresponding answer $a\in A_{2}$. Define
$S=R\times B$, where $R$ is the random seed set of the verifier and $B$ is the
universe of $\beta_{m,l}$. The set $S$ will be the universe for our Set Cover
instance.

We next add one subset to our Set Cover instance $\mathcal{S}_{\varphi}$ for
each query-answer pair in $Q_{1}\times A_{1}$ and $Q_{2}\times A_{2}$. Note
that ultimately the inapproximability result is independent of the number of
subsets in the instance, but the actual construction of the appropriate
verifier is the source of the number of subsets. Let $q(r,i)$ be the query
that the verifier asks prover $i$ when using seed $r$. Because $\varphi$ is an
input to the query-generating function $f$, determining this query depends on
$\varphi$. Let $a_{2}(r,a_{1})$ be the answer that prover 2 can give such that
$\Pi(\varphi,r,a_{1},a_{2}(r,a_{1}))$ accepts, or Null if no such answer
exists. Recall that Theorem 2.3 guarantees that $a_{2}(r,a_{1})$ is unique if
it exists.

The sets corresponding to $Q_{1}\times A_{1}$ are given by

$S_{q_{1},a_{1}}=\\{(r,b)\in R\times B:q_{1}=q(r,1),\text{and
}a_{2}(r,a_{1})\text{ is non-{Null}, and }b\notin C_{a_{2}(r,a_{1})}\\}.$

This is the set of all seed-element pairs in $R\times B$ where:

  * •

$q_{1}$ is the question asked to prover 1 for input $\varphi$ and seed $r$;

  * •

There is an answer from prover 2 $a_{2}(r,a_{1})$ that causes the verifier to
accept when $a_{1}$ is the answer from prover 1; and

  * •

$b$ is _not_ in the special set corresponding to $a_{2}(r,a_{1})$.

The sets corresponding to $Q_{2}\times A_{2}$ are defined similarly:

$S_{q_{2},a_{2}}=\\{(r,b):q_{2}=q(r,2)\text{ and }b\in C_{a_{2}}\\}.$

This is the set of all seed-element pairs in $R\times B$ where:

  * •

$q_{2}$ is the question asked to prover 2 for input $\varphi$ and seed $r$;
and

  * •

$b$ _is_ in the special set corresponding to $a_{2}$.

Then the Set Cover instance has universe set $U$ and all $S_{q_{i},a_{i}}$ for
$i=1,2$ as subsets. One important lemma arises from this construction. A
diagram of the construction dependencies for the instance can be seen in
Figure 2.2.

Set Cover InstanceUniverse SetSubsetsVerifier for SATRandom SeedsQuestions for
$P_{1}$Questions for $P_{2}$Answers from $P_{1}$Answers from $P_{2}$Special
Set SystemUniverse SetSubsets Figure 2.2: A diagram of Lund and Yannakakis’s
proof structure.

######  Lemma 2.8.

For a fixed seed $r\in R$, we can cover all elements $\\{(r,b)\\}_{b\in B}$
with any two sets $S_{q(r,1),a_{1}}$ and $S_{q(r,2),a_{2}(r,a_{1})}$.

###### Proof of Lemma 2.8.

Fix a seed $r$. Assume $a_{2}(r,a_{1})$ exists and consider the two sets
$S_{q(r,1),a_{1}}$ and $S_{q(r,2),a_{2}(r,a_{1})}$. Take a pair $(r,b)$. Then
there are two cases:

  * •

Case 1: $(r,b)\in S_{q(r,1),a_{1}}$. Done.

  * •

Case 2: $(r,b)\notin S_{q(r,1),a_{1}}$. Since $q(r,1)$ is the question asked
to prover 1 for seed $r$ and $a_{2}(r,a_{1})$ exists, the only way this is
possible is if $b\in C_{a_{2}(r,a_{1})}$. But then, since $q(r,2)$ is the
question asked to prover 2 for seed $r$, and $b\in C_{a_{2}(r,a_{1})}$, it
follows that $(r,b)\in S_{q(r,2),a_{2}(r,a_{1})}$ by construction.

Since all $(r,b)$ must be in one of the two sets, their union must cover all
of $\\{(r,b)\\}_{b\in B}$. ∎

An important corollary of Lemma 2.8 arises, which allows us to conclude bounds
on the sizes of optimal and suboptimal coverings and thus propagate the gap.
The statement of the corollary is as follows:

######  Corollary 2.9.

For a fixed seed $r\in R$, any covering which uses $d$ or fewer of the sets
$S_{q_{i},a_{i}}$ to cover $\\{(r,b)\\}_{b\in B}$ must contain two sets of the
form $S_{q(r,1),a_{1}}$ and $S_{q(r,2),a_{2}(r,a_{1})}$.

###### Proof of Corollary 2.9.

Assume not. Notice that sets $S_{q(r,1),a_{1}}$ cover all pairs $(r,b)$ for
which $b\in\overline{C_{a_{2}(r,a_{1})}}$, which is the complement of a
special set. Similarly, the sets $S_{q(r,2),a_{2}}$ cover all pairs $(r,b)$
for which $b\in C_{a_{2}}$, which is a special set. By assumption, there is no
pair of sets $S_{q(r,1),a_{1}}$ and $S_{q(r,2),a_{2}(r,a_{1})}$ in the
covering, so none of the sets $\overline{C_{a_{2}(r,a_{1})}}$ are complements
of any of the sets $C_{a_{2}}$.

However, this means that a collection of $d$ or fewer of the special sets
$C_{a}$ and their complements $\overline{C_{a}}$ is able to cover all $b\in
B$, since there is one pair $(r,b)$ for each $b\in B$. By Corollary 2.6, some
set and its own complement must be in the collection, which contradicts the
assumption. Therefore, a pair of sets of the form $S_{q(r,1),a_{1}}$ and
$S_{q(r,2),a_{2}(r,a_{1})}$ must be in the covering. ∎

With this knowledge, we can reformulate Lemma 2.7:

######  Lemma 2.10.

Let $\mathcal{S}$ be a Set Cover instance. Then, for any CNF formula
$\varphi$, we can construct an instance of Set Cover $\mathcal{S}_{\varphi}$
in $\text{DTIME}(n^{\text{polylog}(n)})$ such that:

  * •

If $\varphi\in\textsc{SAT}$, then
$\textsf{OPT}(\mathcal{S}_{\varphi})=|Q_{1}|+|Q_{2}|$.

  * •

If $\varphi\notin\textsc{SAT}$, then $\textsf{OPT}(\mathcal{S}_{\varphi})\geq
c\log(|R\times B|)\cdot(|Q_{1}|+|Q_{2}|)$ for any $0<c<\frac{1}{4}$.

We will prove each part of Lemma 2.10 separately.

####  2.2.2 Proving the First Part

The proof of the first part is straightforward. We seek to prove that if
$\varphi\in\textsc{SAT}$, then
$\textsf{OPT}(\mathcal{S}_{\varphi})=|Q_{1}|+|Q_{2}|$.

Assume that $\varphi\in\textsc{SAT}$. Then there exists some pair of provers
which makes the verifier accept with probability 1. This means that for all
seeds, if seed $r$ generates query pair $(q_{1},q_{2})$, then the answer pair
$(a_{1},a_{2})$ returned by the provers causes $\Pi(\varphi,r,a_{1},a_{2})$ to
output Yes. Notice that this means the sets $S_{q(r,1),a_{1}}$ and
$S_{q(r,2),a_{2}(r,a_{1})}$ cover all $\\{(r,b)\\}_{b\in B}$, and such a pair
of sets therefore exists in our instance for every seed $r$. Additionally,
because the prover’s strategies are fixed, there is exactly one set per query
in the strategy, meaning there are $|Q_{1}|+|Q_{2}|$ corresponding sets in the
instance. Since the sets in the strategy are able to cover all pairs, it
follows that the size of a minimal covering for $S$ is $|Q_{1}|+|Q_{2}|$. This
proves the first part.

####  2.2.3 Proving the Second Part

The proof of the second part is more involved. We seek to prove that if
$\varphi\notin\textsc{SAT}$, then $\textsf{OPT}(\mathcal{S}_{\varphi})\geq
c\log(|R\times B|)\cdot(|Q_{1}|+|Q_{2}|)$ for any $0<c<\frac{1}{4}$.

Assume that $\varphi\notin\textsc{SAT}$. Define a bipartite graph $G$, and let
the two sets of nodes be $Q_{1}$ and $Q_{2}$. Add an edge $e_{r}$ between
queries $q_{1}\in Q_{1}$ and $q_{2}\in Q_{2}$ if there is some random seed $r$
such that $f(\varphi,r)=(q_{1},q_{2})$. By the properties of the proof system,
and because $|Q_{1}|=|Q_{2}|$, $G$ is $\frac{|R|}{|Q_{1}|}$-regular.

Consider some arbitrary covering $\mathcal{C}$ of $S$. We will use this to
define a cost function $c$ as follows:

  * •

The cost of a node $c(q)$ is the number of sets $S_{q,a}$ in $\mathcal{C}$ for
which the query is $q$.

  * •

The cost of an edge $c(e_{r})$, where $e_{r}=(q_{1},q_{2})$, is the sum of the
costs of its incident nodes, $c(q_{1})+c(q_{2})$.

Note that if the cost of edge $e_{r}$ is $\leq d$, then because $\mathcal{C}$
is a covering, it follows that all pairs $\\{(r,b)\\}_{b\in B}$ can be covered
in fewer than $d$ sets. By Corollary 2.9, it follows that seed $r$ has a pair
of satisfying answers to its queries.

Let an edge $e_{r}$ be called _good_ if $c(e_{r})\leq d$, and let it be called
_bad_ otherwise. Let $\delta$ be the fraction of good edges in $G$. We then
prove two lemmas:

######  Lemma 2.11.

If $\varphi\notin\textsc{SAT}$, there exists provers such that the verifier
accepts with probability at least $\frac{\delta}{d^{2}}$.

###### Proof of Lemma 2.11.

Define $d$ strategies $P_{i,1},P_{i,2},\dots,P_{i,d}$ for each of the two
provers $P_{i}$ as such:

  * •

For each query $q\in Q_{i}$, look at the strategies $a\in
A_{i}:S_{q,a}\in\mathcal{C}$. Order the strategies arbitrarily.

  * •

The answer $P_{i,j}$ gives to query $q$ will be the $j$th element of the
ordering of $q$’s answers, or an arbitrary answer if there are no more in the
ordering.

If a seed $r$ is chosen uniformly randomly, it has probability $\delta$ of
corresponding to a good edge, meaning that there is an accepting pair of
answers for $r$’s queries. These answers must belong to some pair of
strategies of the provers by pigeonhole principle, since there are at most $d$
question-answer pairs corresponding to each query on a good edge, and each of
the $d$ strategies provides a different answer out of those in the covering.
This means that some pair of strategies has at least a $\frac{\delta}{d^{2}}$
chance of making the verifier accept: probability $\delta$ that the edge
$e_{r}$ is good, and probability at least $\frac{1}{d^{2}}$ that our
strategies choose an accepting answer pair in response. ∎

######  Lemma 2.12.

The size of the covering set, $|\mathcal{C}|$, is at least
$(1-\delta)\cdot\frac{d}{2}\cdot(|Q_{1}|+|Q_{2}|)$.

###### Proof of Lemma 2.12.

The sum of all edge costs is bounded below by the sum of all bad edge costs.
Since each bad edge costs $>d$, and the number of bad edges is
$(1-\delta)\cdot|R|$, we can conclude that the sum of edge costs is strictly
bounded below by $(1-\delta)\cdot|R|\cdot d$.

The sum of all edge costs is also equal to the sum of all costs of the
corresponding vertices to each edge. Since $G$ is
$\frac{|R|}{|Q_{1}}$-regular, this evaluates to
$\frac{|R|}{|Q_{1}|}\cdot\sum_{q\in Q_{1}\cup Q_{2}}c(q)$. By construction,
the sum of all individual vertex costs is $C$.

Combining these two facts yields

$\displaystyle\frac{|R|}{|Q_{1}|}|\mathcal{C}|$ $\displaystyle>(1-\delta)|R|d$
$\displaystyle|\mathcal{C}|$ $\displaystyle>(1-\delta)\cdot d\cdot|Q_{1}|$
$\displaystyle|\mathcal{C}|$ $\displaystyle>(1-\delta)\cdot\frac{d}{2}\cdot
2|Q_{1}|$ $\displaystyle|\mathcal{C}|$
$\displaystyle>(1-\delta)\cdot\frac{d}{2}\cdot(|Q_{1}|+|Q_{2}|)$

since $|Q_{1}|=|Q_{2}|$. ∎

Now we can complete the proof. By Lemma 2.11, if $\varphi\notin\textsc{SAT}$,
then $\frac{\delta}{d^{2}}\leq\frac{1}{n}$. Substituting directly into the
result of Lemma 2.12 yields that

$|\mathcal{C}|\geq\left(\frac{d}{2}-\frac{d^{3}}{2n}\right)(|Q_{1}|+|Q_{2}|).$

Choose arbitrarily large $k>0$ and let $d=\max(k\log|R|,k\log|A_{2}|)$. This
choice of $d$ ensures that the following step will hold.

Note that $|R\times B|=|R||B|$, and by construction,
$|B|=\mathcal{O}(2^{2d}|A_{2}|^{2})$. This means that

$\log(|R||B|)\leq 2d\left(1+\frac{3}{2k}\right).$

We may make $k$ arbitrarily large, which makes the $\frac{3}{2k}$ vanish as
$k$ increases. This results in the simplified statement

$\log(|R||B|)\leq 2d$

Solving for $d$, substituting into the result of Lemma 2.12, and simplifying
yields

$|\mathcal{C}|\geq\frac{1}{2}\cdot\left(\frac{\log(|R||B|)}{2}-\frac{\log(|R||B|)^{3}}{8|R||B|}\right)\cdot(|Q_{1}|+|Q_{2}|).$

We may assume that $\log(|R||B|)^{3}\ll 8|R||B|$, which yields the final
result of

$|\mathcal{C}|\geq\frac{1}{4}\cdot\log(|R||B|)\cdot(|Q_{1}|+|Q_{2}|)$

which proves the second part of the claim. This proves Lemma 2.10, hence
proving Lemma 2.7 and completing the reduction.

###  2.3 Using a Randomized Construction

By using a randomized construction for the special set system, rather than a
deterministic one, Lund and Yannakakis are able to construct it in
$\text{ZTIME}(n^{\text{polylog}(n)})$, where ZTIME is zero-error probabilistic
polynomial time (the class of languages decidable via Las Vegas algorithms).
The size of the new special set is $|B|=(d+d\ln m+2)2^{d}$, which is
approximately the square root of the size of the deterministic algorithm,
which is $|B|=\mathcal{O}(2^{2d}m^{2})$. Using this, they achieve the
following result.

######  Theorem 2.13.

Unless $\text{NP}\subseteq\text{ZTIME}(n^{\text{polylog}(n)})$, Set Cover
cannot be approximated within a ratio of $c\log n$ for any positive
$c<\frac{1}{2}$.

This is a stronger result than using the deterministic construction, but
requires a stronger assumption in turn. As such, it is effectively
incomparable to the deterministic result in terms of quality.

##  3 Bellare, Goldwasser, Lund, and Russell, 1993 [4]

###  3.1 Inapproximability Result

The main theorem that this paper achieves is as follows:

######  Theorem 3.1.

  1. 1.

Unless $\text{P}=\text{NP}$, Set Cover cannot be approximated within a ratio
of $c$ for any constant $c$.

  2. 2.

Unless $\text{NP}\subseteq\text{DTIME}(n^{\mathcal{O}(\log\log n)})$, Set
Cover cannot be approximated within a ratio of $c\log n$ for any positive
$c<\frac{1}{8}$.

These results come from increasing the number of provers in the system to
four, and providing a slightly different construction. Though the assumptions
of these results are weaker, the constants are also worse; therefore, this
result is effectively incomparable with the result of Section 2.

###  3.2 The Sliding Scale Conjecture

The paper also formulates the following conjecture, a weaker version of which
was ultimately proven in [5].

######  Conjecture 3.2 (Sliding Scale Conjecture).

There exist two-prover, one-round proof systems for SAT that have logarithmic
randomness, logarithmic answer sizes, and $\frac{1}{n}$ error probability.

Contingent on this conjecture, the authors posit that better Set Cover results
are achievable. In particular, they observe that a Set Cover result arises
from a weaker form of the conjecture.

######  Conjecture 3.3 (Weak Sliding Scale Conjecture for Set Cover).

Suppose that for some constant $p$ and some function
$\epsilon(n)=\frac{1}{\log^{\omega(1)}n}$, SAT has $p$-prover proof systems
with logarithmic randomness, logarithmic answer sizes, and error
$\epsilon(n)$. Then, unless $\text{P}=\text{NP}$, Set Cover cannot be
approximated within a ratio of $c\log n$ for any positive $c<\frac{1}{2p}$.

While this conjecture remains unproven, it forms the basis of the Projection
Games Conjecture in [13].

##  4 Raz, 1998 [16]

Raz does not focus on Set Cover in this paper; rather, he offers a
breakthrough in error of multi-prover interactive proof systems in the form of
the following lemma:

######  Lemma 4.1 (Raz Repetition Lemma).

If a two-prover, one-round proof system is repeated $\ell$ times independently
in parallel, then the error is $2^{-c\ell}$, where $c>0$ is constant and is
dependent only on the error in the original proof system and the length of the
answers in that proof system.

This implies that parallel repetition of a two-prover one-round proof system
reduces the error of the system exponentially fast. Taken in combination with
Theorems 2.1 and 2.13, the hardness assumptions can be relaxed, yielding the
following:

######  Theorem 4.2.

  1. 1.

Unless $\text{NP}\subseteq\text{DTIME}(n^{\mathcal{O}(\log\log n)})$, Set
Cover cannot be approximated within a ratio of $c\log n$ for any positive
$c<\frac{1}{4}$.

  2. 2.

Unless $\text{NP}\subseteq\text{ZTIME}(n^{\mathcal{O}(\log\log n)})$, Set
Cover cannot be approximated within a ratio of $c\log n$ for any positive
$c<\frac{1}{2}$.

Both parts of this theorem are strict improvements on the results of [12]; the
first part is also a strict improvement over the second part of Theorem 3.1
from [4].

##  5 Naor, Schulman, and Srinivasan, 1995 [15]

###  5.1 $(n,k)$-Universal Sets

The key component of this paper was the development of new techniques for
constructing $(n,k)$-universal sets, which are defined as follows:

######  Definition 5.1 ($(n,k)$-Universal Set).

An $(n,k)$-universal set $T\subseteq\\{0,1\\}^{n}$ is a minimal set of
bitstrings such that, for any set of indices $S\subseteq[n]$ with $|S|=k$, the
projection of $T$ on $S$ (defined as the set of subsequences of bitstrings of
$T$ taken at the indices in $S$) is exactly the set $\\{0,1\\}^{k}$.

Naor, Schulman, and Srinivasan developed new deterministic procedures for
constructing these sets in [15]. Their main result is the following:

######  Theorem 5.2.

There is a deterministic, explicit construction of $(n,k)$-universal sets of
size $2^{k}k^{\mathcal{O}(\log k)}\log n$.

The theorem is a corollary of their more general result on $k$-restriction
problems. Their procedure makes the deterministic construction much more
efficient, yielding performance on par with the randomized construction. This
unifies the deterministic and randomized lower bounds, yielding the following
refinement of Theorem 4.2:

######  Theorem 5.3.

Unless $\text{NP}\subseteq\text{DTIME}(n^{\mathcal{O}(\log\log n)})$, Set
Cover cannot be approximated within a ratio of $c\log n$ for any positive
$c<\frac{1}{2}$.

###  5.2 $(n,k,b)$-Anti-Universal Sets

In addition to $(n,k)$-universal sets, another result of Naor _et al._ on
restriction games involves a structure known as $(n,k,b)$-anti-universal sets,
which were initially proposed by Feige and are a cornerstone of the reduction
in [6]. They are defined as follows:

######  Definition 5.4 ($(n,k,b)$-Anti-Universal Set).

An $(n,k,b)$-anti-universal set $\mathcal{T}\subseteq[n]\times[b]$ is a family
of functions $t_{i}:[n]->[b]$ where, for every pair of vectors $u\in[n]^{k}$
and $v\in[b]^{k}$, there is a function $t_{j}\in\mathcal{T}$ which transforms
$u$ into a vector that disagrees with $v$ on each coordinate (meaning that
$t_{j}$ takes every element $u_{i}\in u$ to something _other_ than the
corresponding element $v_{i}\in v$).

This is a generalization of $(n,k)$-universal sets, which are simply the
special case where $b=2$. Naor _et al._ achieve the following result:

######  Theorem 5.5.

For any fixed $b$, there is a deterministic, explicit construction of
$(n,k,b)$-anti-universal sets of size
$\left(\frac{b}{b-1}\right)^{k}k^{\mathcal{O}(\log k)}\log n$.

In combination with the reduction of Section 6, this is sufficient to prove
Theorem 6.1.

##  6 Feige, 1998 [6]

Feige provides the first crucial innovation by generalizing the frameworks of
[12] and by beginning from MAX 3SAT-5 rather than conventional SAT. The
ultimate result is as follows:

######  Theorem 6.1.

Unless $\text{NP}\subseteq\text{DTIME}(n^{\mathcal{O}(\log\log n)})$, Set
Cover cannot be approximated within a ratio of $c\ln n$ for any positive
$c<1$.

We will proceed to give a proof of this theorem following the constructions
given by Feige.

###  6.1 Preliminary Constructions

In this section, we describe several constructions and concepts necessary for
Feige’s proof, many of which are generalizations of constructions in Section
2.

####  6.1.1 Interactive Proof System for MAX 3SAT-5

The problem of MAX 3SAT-5 is a particular member of a family of SAT problems
with restrictions on the number of clauses each variable appears in. The
problem statement is:

######  Definition 6.2 (MAX 3SAT-5).

Consider a CNF boolean formula $\varphi$ on $n$ variables and $\frac{5}{3}n$
clauses, where the following three conditions hold (such formulas are known as
3SAT-5 formulas):

  * •

Each clause contains 3 literals.

  * •

Each variable appears in exactly 5 clauses.

  * •

No variable appears in the same clause more than once.

The problem of MAX 3SAT-5 is to determine the maximum number of clauses that
are simultaneously satisfiable.

The following is a theorem of Feige:

######  Theorem 6.3.

For some $\varepsilon>0$, it is NP-hard to distinguish between 3SAT-5 formulas
that are completely satisfiable, and those with at most a $(1-\varepsilon)$
fraction of clauses simultaneously satisfiable.

It is this gap in distinguishability that will ultimately lead to the gap
reduction.

Feige also presents an explicit protocol for a two-prover system for MAX
3SAT-5. (See Definition 2.2 for the structure of such a system.) This is
different from the methodology of Lund and Yannakakis, who used a theorem
asserting the existence of such a protocol without actually describing it.

A two-prover, one-round protocol for MAX 3SAT-5 is as follows:

  * •

The first prover is a function
$P_{1}:\left[\frac{5n}{3}\right]\to\\{0,1\\}^{3}$. This can be thought of as a
function receiving the index of some clause in $\varphi$, and returning a
prospective assignment to the three variables in the clause in order.

  * •

The second prover is a function $P_{2}:\\{1,2,3\\}\to\\{0,1\\}$. This can be
thought of as a function being told to look at the first, second, or third
variable in the clause that $P_{1}$ received, and giving that variable a
prospective assignment.

  * •

The verifier accepts if both of the following are true:

    * –

The assignment given by $P_{1}$ satisfies the clause.

    * –

The assignment given by $P_{2}$ agrees with the assignment that $P_{1}$ gave
the variable in question.

Analysis of this proof system results in the following theorem:

######  Theorem 6.4.

Let $\varphi$ be a 3CNF-5 formula, and let $\varepsilon$ be the fraction of
unsatisfied clauses in the assignment that satisfies the _most_ possible
clauses. Then, under the optimal strategy of the provers, the verifier accepts
with probability $1-\frac{\varepsilon}{3}$.

Note that the error in this proof system is still high. To reduce the error,
the system can be run in parallel: choose $\ell$ clauses and one variable from
each clause, and then have the provers provide assignments to everything at
once. By Lemma 4.1, this reduces the error to $2^{-c\ell}$ for some positive
constant $c$ dependent only on the original error and the answer lengths;
because the original error is independent of $n$ and the answer lengths are
fixed, the new error is thus $2^{-c\ell}$ for a universal constant $c$.

####  6.1.2 Generalization to $k$ Provers

Let $k$ be an arbitrarily large constant. Consider a binary code containing
$k$ code words of length $\rho=\Theta(\log\log n)$, weight $\frac{\rho}{2}$,
and pairwise Hamming distance at least $\frac{\rho}{3}$. Such a code can be
used to construct a $k$-prover, one-round protocol for MAX 3SAT-5:

  * •

The verifier selects $\rho$ clauses $C_{1},\dots,C_{\rho}$ uniformly randomly,
and selects one _distinguished variable_ in each clause $x_{1},\dots,x_{\rho}$
uniformly randomly.

  * •

Associate each prover $P_{i}$ with a code word of length $\rho$. Because the
code word has weight $\frac{\rho}{2}$, half of its bits are 0 and half are 1.
Consider bit $j$ of the code word.

    * –

If bit $j$ is 0, prover $P_{i}$ is sent the distinguished variable $x_{j}$.

    * –

If bit $j$ is 1, prover $P_{i}$ is sent the clause $C_{j}$.

In this way, each prover receives $\frac{\rho}{2}$ clauses and
$\frac{\rho}{2}$ distinguished variables to assign, and does not receive any
distinguished variables from the clauses it is assigning.

  * •

The answer each prover $P_{i}$ provides is a length $2\rho$ bitstring
consisting of assignments of all variables sent to $P_{i}$: the
$\frac{\rho}{2}$ distinguished variables, and the $\frac{3\rho}{2}$ variables
in the clauses.

We say that provers $P_{i}$ and $P_{j}$ are _consistent_ if their assignments
to the distinguished variables agree on each coordinate of their respective
code words. It does not matter whether $P_{i}$ and $P_{j}$ agree on non-
distinguished variables of clauses, or whether they are each internally
consistent on assigning the distinguished variable the same truth value in
different clauses.

To establish a clear gap, Feige introduces the notion of weak and strong
acceptance of a given formula: the system _weakly accepts_ a formula if _some_
pair of provers is consistent, and it _strongly accepts_ a formula if _every_
pair of provers is consistent. A diagram of the $k$-prover extension can be
seen in 6.1.

Input $\varphi$Query $q_{1}$Query $q_{k}$Random Seed $r$Prover $P_{1}$Prover
$P_{k}$Answer $a_{1}$Answer
$a_{k}$$f(\varphi,r)$$\Pi(\varphi,r,a_{1},\dots,a_{k})$ Output Strong Accept/
Weak Accept/No

Figure 6.1: A $k$-prover one-round proof system simply extends the 2-prover
model.

Based on this, Feige then provides the following lemma:

######  Lemma 6.5.

Consider a 3CNF-5 formula $\varphi$.

  * •

If $\varphi$ is satisfiable, then there exists a strategy of the provers that
always strongly accepts.

  * •

If at most a $(1-\varepsilon)$ fraction of clauses of $\varphi$ are
simultaneously satisfiable, then the verifier weakly accepts with probability
at most $k^{2}\cdot 2^{-c\rho}$, where $k$ is the number of provers and $c$ is
a positive constant depending only on $\varepsilon$.

The error term in the second case is due to pairwise invocation of Lemma 4.1.

####  6.1.3 Partition System

Feige also defines a _partition system_ , a generalization of the special set
system in Definition 2.4 and an invocation of the $(n,k,b)$-anti-universal set
of Definition 5.4.

######  Definition 6.6 (Partition System).

A _partition system_ $\beta(m,\mathcal{L},k,d)$ has the following properties:

  * •

There is a universe set $\beta$, with $|\beta|=m$.

  * •

There is a collection of $\mathcal{L}$ distinct partitions of $\beta$,
$p_{1},\dots,p_{\mathcal{L}}$.

  * •

For $1\leq i\leq\mathcal{L}$, partition $p_{i}$ is a collection of $k$
disjoint subsets of $\beta$ whose union is $\beta$.

  * •

Any cover of $\beta$ by subsets such that no two subsets are from the same
partition requires at least $d$ subsets.

Feige obtains the following results:

######  Lemma 6.7.

For every $c\geq 0$ and sufficiently large $m$, there exists a partition
system $\beta(m,\mathcal{L},k,d)$ such that all of the following hold:

  * •

$\mathcal{L}\simeq(\log m)^{c}$.

  * •

$k$ may be chosen arbitrarily as long as $k<\ln\frac{m}{3}\ln\ln m$.

  * •

$d=(1-f(k))k\ln m$, where $\lim\limits_{k\to\infty}f(k)=0$.

Moreover, such a partition system can be constructed in
$\text{ZTIME}(m^{\mathcal{O}(\log m)})$. By Theorem 5.5, there also exists a
deterministic construction taking time linear in $m$ and satisfies
$m=\left(\frac{k}{k-1}\right)^{d}d^{\mathcal{O}(\log d)}\log\mathcal{L}$ for
arbitrary constant $k$.

###  6.2 The Proof

Because the core lemma of Feige’s paper relies on the construction, we defer
presenting it until after the initial setup.

####  6.2.1 Initial Setup

Consider a $k$-prover system for MAX 3SAT-5. The verifier’s randomness is
represented by a seed bitstring $r$ of length $\rho\log 5n$. There are
$R=(5n)^{\rho}$ such seeds. Each seed induces a selection of $\rho$ clauses
and $\rho$ distinguished variables, one from each of the clauses. Next, each
seed $r\in R$ is associated with a distinct partition system
$\beta_{r}(m,\mathcal{L},k,d)$ with the following properties:

  * •

$\mathcal{L}=2^{\rho}$

  * •

$m=n^{\Theta(\rho)}$

  * •

$d=(1-f(k))k\ln m$

Note that the corresponding universe of our Set Cover instance will be
$\mathcal{B}=\bigcup_{r}\beta_{r}$. This makes the size of the universe
$N=mR=n^{\Theta(\rho)}(5n)^{\rho}$.

Within a given partition system $\beta_{r}$, each of the $2^{\rho}$ partitions
$p_{r,j}$ is associated with a $\rho$-bit string $s_{r,j}$, representing
assignments to the distinguished variables. Each subset within $p_{r,j}$ is
associated with a unique prover $i$; denote the subset associated with prover
$i$ in partition $j$ of system $\beta_{r}$ by $\beta_{r}[j,i]$.

We seek to generate a subset $S_{q,a,i}$ for each question-answer pair $(q,a)$
of prover $P_{i}$. As before, let $q(r,i)$ be the question sent to prover
$P_{i}$ when using seed $r$. For all $r$ such that $q=q(r,i)$, consider the
induced selection of distinguished variables given by the bitstring $r$. From
the corresponding answer $a$, consider the induced assignment $a_{r}$ to the
distinguished variables on each coordinate. Because every assignment is
represented by some partition in the system $\beta_{r}$, some partition
$p^{*}_{r}$ in that system has $a_{r}$ as its associated string. Consider the
subset $\beta_{r}[p^{*}_{r},i]$. Define

$S_{q,a,i}=\bigcup_{\\{r\mid q=q(r,i)\\}}\beta_{r}[p^{*}_{r},i]$

or the union of the subset corresponding to prover $P_{i}$ in the partition
corresponding to the answers of $a$, across all partition systems whose seed
asks question $q$. This generates the sets of our Set Cover instance. A
diagram of the dependencies in this construction can be found in Figure 6.2.

Set Cover InstanceUniverse SetSubsetsCollection of Partition SystemsUniverse
SetsPartitionsSets in PartitionsVerifier for MAX 3SAT-5Random SeedsQuestion
SetsAnswer SetsProvers Figure 6.2: A diagram of Feige’s proof structure.

Finally, observe that each prover can be asked a total of
$Q=n^{\rho/2}\cdot\left(\frac{5n}{3}\right)^{\rho/2}$ questions. We now state
the core lemma:

######  Lemma 6.8.

Let $\varphi$ be a 3CNF-5 formula.

  * •

If $\varphi$ is satisfiable, then the universe set $\mathcal{B}$ of $N=mR$
points can be covered by $kQ$ subsets.

  * •

If at most a $(1-\varepsilon)$ fraction of the clauses of $\varphi$ are
simultaneously satisfiable, then $\mathcal{B}$ requires $(1-2f(k))kQ\ln m$
subsets to be covered, where $\lim\limits_{k\to\infty}f(k)=0$.

We will prove each part of Lemma 6.8 separately.

####  6.2.2 Proving the First Part

The first part is straighforward. Consider a satisfiable 3CNF-5 formula
$\varphi$. Then by Lemma 6.5, there is a strategy that always strongly
accepts; in particular, it is one that corresponds to a satisfying assignment
of $\varphi$. Fix the provers’ strategy to be consistent with a satisfying
assignment $a$ for $\varphi$. Consider the sets $S_{q,a,i}$ for which prover
$P_{i}$ replies to question $q$ with the satisfying assignment $a$. Fix a seed
$r$ and, from among the considered sets, look at the sets $S_{q_{i},a_{i},i}$
for all $1\leq i\leq k$, corresponding to the questions induced by seed $r$
and the answers in alignment with the satisfying assignment for each prover.
The universe $\mathcal{B}$ is completely covered by these $k$ sets because,
for the partition $p^{*}_{r}$ corresponding to $a$, the subset
$\beta_{r}[p^{*}_{r},i]$ is in $S_{q_{i},a_{i},i}$ for every $i$ by
construction, and their union thus completes the partition.

This argument applies to every seed $r$. This means that each seed’s portion
is coverable by $k$ sets. By the uniformity of the system, each question $q$
must be askable, so each question must have a corresponding satisfying
strategy; this means that $kQ$ sets are used in the covering.

####  6.2.3 Proving the Second Part

Consider now a 3CNF-5 formula $\varphi$ with only a $(1-\varepsilon)$ fraction
of the clauses simultaneously satisfiable. Then by Lemma 6.5, any strategy of
the provers weakly accepts with probability at most $k^{2}\cdot 2^{-c\rho}$.
Set $\delta=2f(k)$ and assume by way of contradiction that there exists a
cover $\mathcal{C}$ of size $|\mathcal{C}|\leq(1-\delta)kQ\ln m$. As in the
proof of Lemma 2.7, we will use this to define a cost function $c$ over seeds:

  * •

Let $q$ be a question asked to prover $P_{i}$. The cost of that question
$c(q,i)$ is the number of sets $S_{q,a,i}$ in $\mathcal{C}$ for which the
query is $q$.

  * •

The cost of a seed $c(r)$ is $\sum_{i=1}^{k}c(q(r,i),i)$, or the sum of all
individual costs of the $k$ questions induced by that seed.

Let a seed $r$ be called _good_ if $c(r)<\left(1-\frac{\delta}{2}\right)k\ln
m$, and let it be called _bad_ otherwise. Unlike the proof of Lund and
Yannakakis for Lemma 2.7, where we began with deducing an acceptance
probability and then reasoned about the size of the covering set, here we
assume an upper bound on the size of the covering set and then are able to
deduce a lower bound on the fraction of good seeds. We will then use this to
prove a lemma on the acceptance probability.

######  Lemma 6.9.

The fraction of good seeds is at least $\frac{\delta}{2}$.

###### Proof of Lemma 6.9.

Assume not. Then consider the sum of costs of all seeds. Note that in this
case, $\left(1-\frac{\delta}{2}\right)$ is the lower bound on the fraction of
bad seeds. This yields

$\sum_{r\in
R}c(r)\geq\left(1-\frac{\delta}{2}\right)R\cdot\left(1-\frac{\delta}{2}\right)k\ln
m=\left(1-\frac{\delta}{2}\right)^{2}kR\ln m$

Note that $\left(1-\frac{\delta}{2}\right)^{2}>(1-\delta)$, resulting in

$\sum_{r\in R}c(r)>(1-\delta)kR\ln m$

However, consider that we can also sum the costs of all seeds by adding the
costs of each question asked to each prover by each seed, as in

$\sum_{r\in R}c(r)=\sum_{r\in R}\sum_{i=1}^{k}c(q(r,i),i)$

Note that by uniformity of the proof system, each question is asked
$\frac{R}{Q}$ times across the whole seed set. Also, by construction, the sum
of weights of all questions across all provers must be $|\mathcal{C}|$.
Combining these facts yields

$\sum_{r\in R}c(r)=\sum_{r\in
R}\sum_{i=1}^{k}c(q(r,i),i)=\frac{R}{Q}\sum_{(q,i)}c(q,i)=\frac{R}{Q}|\mathcal{C}|$

Substituting this equality into the result of the first sum gives

$|\mathcal{C}|>(1-\delta)kR\ln m\geq|\mathcal{C}|$

which is a contradiction. ∎

######  Lemma 6.10.

Let $\mathcal{C}$ be a covering of $\mathcal{B}$ with
$|\mathcal{C}|\leq(1-\delta)kQ\ln m$. Then, for some strategy of the provers,
the verifier weakly accepts $\varphi$ with probability at least
$\frac{2\delta}{(k\ln m)^{2}}$.

###### Proof.

Consider a randomized strategy of the provers where, on question $q$, prover
$P_{i}$ selects an answer uniformly randomly from the answers $a$ whose sets
$S_{q,a,i}$ are in the covering $|\mathcal{C}|$. Note that, for a fixed seed
$r$, the corresponding partition system $\beta_{r}$ admits a bijection between
the sets $\beta_{r}[i,j]$ participating in the cover of $\beta_{r}$, and sets
$S_{q,a,i}$ in the covering $\mathcal{C}$.

Next, consider a good seed $r$. By the property of the partition system, any
covering that does not use two subsets from the same partition requires at
least $d=(1-f(k))k\ln m$ subsets. Recall that $\delta=2f(k)$ by definition.
Since $r$ is good, its partition system $\beta_{r}$ is covered by
$c(r)<\left(1-\frac{\delta}{2}\right)k\ln m=(1-f(k))k\ln m$ subsets. This is
fewer than $d$, so by contraposition, $\beta_{r}$ must contain two subsets
from the same partition in its covering, namely $\beta_{r}[p_{r}^{*},i]$ and
$\beta_{r}[p_{r}^{*},j]$ for some provers $P_{i}$ and $P_{j}$. By the earlier
bijection, these correspond to two subsets $S_{q_{i},a_{i},i}$ and
$S_{q_{j},a_{j},j}$ in the covering $\mathcal{C}$.

Assume the verifier chooses $r$ as its seed. Then prover $P_{i}$ gets question
$q_{i}$ and chooses an answer uniformly randomly from the set $A_{r,i}$ of all
answers $a$ for which $S_{q_{i},a,i}$ is in $\mathcal{C}$. The answer $a_{i}$
is among these. Prover $P_{j}$ behaves symmetrically and has a corresponding
set $A_{r,j}$. Because $r$ is a good seed, $|A_{r,i}|+|A_{r,j}|<k\ln m$. This
means that the joint probability the provers will choose to answer with the
specific answers $a_{i}$ and $a_{j}$ is at least $\left(\frac{1}{(k\ln
m)/2)}\right)^{2}=\frac{4}{(k\ln m)^{2}}$. These answers are consistent, so
the verifier will weakly accept if they are chosen.

By Lemma 6.9, the probability $r$ is good is at least $\frac{\delta}{2}$. So
the strategy weakly accepts with a probability at least
$\frac{\delta}{2}\cdot\frac{4}{(k\ln m)^{2}}=\frac{2\delta}{(k\ln m)^{2}}$.
This strategy can be made deterministic by fixing the optimal coin tosses in
the randomized strategy, which does not change this lower bound. ∎

To complete the proof of the second bullet of Lemma 6.8, let
$\rho=\Theta(\log\log n)$ and $m=n^{\Theta(\rho)}$. Then

$\frac{2\delta}{(k\ln m)^{2}}>k^{2}\cdot 2^{-c\rho}$

which is a contradiction as the lower bound for weak acceptance probability is
higher than the upper bound. Therefore, the size of the cover cannot be as
stated and it must be strictly larger than $(1-\delta)kQ\ln m$. This proves
Lemma 6.8 and thus Theorem 6.1.

##  7 Moshkovitz, 2015 [13]

Moshkovitz further generalizes the framework of Feige to produce even more
refined results. She shifts the underlying framework from multi-prover
interactive systems to _probabilistically checkable proofs_ (PCP), for which
many new analysis techniques had been developed in the decade since Feige’s
lower bound. Notably, PCPs are capable of being analyzed in terms of
projection games, which is a framework that lends itself well to Set Cover.
She also begins from the more general Label Cover problem rather than MAX
3SAT-5, which enables an alternative model of Set Cover. The partition system
is exchanged for a bipartite graph coloring with unique properties. Finally,
she introduces a modified variant of Conjecture 3.2, the _Projection Games
Conjecture_ , which the new result is contingent on a weakened version of.
These allow her to achieve the following result:

######  Theorem 7.1.

Unless $\text{P}=\text{NP}$ and assuming the Projection Games Conjecture
holds, Set Cover cannot be approximated within a ratio of $c\ln n$ for any
positive $c<1$.

We will proceed to give a proof of this result following the constructions
given by Moshkovitz.

###  7.1 Preliminary Constructions

In this section, we describe constructions and concepts needed for the proof.
There are many parallels to prior constructions.

####  7.1.1 Projection Games

######  Definition 7.2 (Projection Game).

A _projection game_ takes the following inputs:

  * •

A bipartite graph $G=((A,B),E)$.

  * •

Finite alphabets $\Sigma_{A},\Sigma_{B}$.

  * •

A set $\Phi$ containing a function $\pi_{e}:\Sigma_{A}\to\Sigma_{B}$ for every
edge $e\in E$. These functions $\pi_{e}$ are the _projections_.

The _size_ of the game is defined as $|A|+|B|+|E|$. The following two concepts
are also introduced:

  * •

A _labeling_ is a function mapping a vertex set to its corresponding alphabet,
either $\phi_{A}:A\to\Sigma_{A}$ or $\phi_{B}:B\to\Sigma_{B}$.

  * •

A pair of labelings $\phi_{A}$ and $\phi_{B}$ _satisfies_ edge $e=(a,b)$ if
$\pi_{e}(\phi_{A}(a))=\phi_{B}(b)$; that is, if the projection $\pi_{e}$ takes
the label of $a$ to the label of $b$.

The goal of the game is to find labelings $\phi_{A}$ and $\phi_{B}$ that
satisfy as many edges as possible. An example of a small game is given in
Figure 7.1.

$\mathbf{A}$$\mathbf{B}$Projections$\sigma_{1}$$\sigma_{2}$$\nu$$e_{1}:\pi_{1}$$e_{2}:\pi_{2}$$e_{1}$$e_{2}$
Figure 7.1: A small projection game with labelings
$\sigma_{1},\sigma_{2}\in\Sigma_{A}$ and $\nu\in\Sigma_{B}$. The goal is to
try to choose labels such that $\pi_{1}(\sigma_{1})=\pi_{2}(\sigma_{2})=\nu$.

The following theorem is due to Moshkovitz:

######  Theorem 7.3.

Let $\mathcal{P}$ be a projection game of size $n$ with alphabets of size $k$
and soundness error $\varepsilon$, where $k$ and $\varepsilon$ may be
functions of $n$. Then, it is NP-hard to distinguish between the case where
all edges can be satisfied, and the case where at most a $\varepsilon$
fraction of edges can be satisfied.

Unlike the result of Feige, here, the error is explicitly related to the
soundness error of the underlying projection game.

####  7.1.2 The Projection Games Conjecture

In [14], Moshkovitz and Raz proved the following theorem

######  Theorem 7.4 (Almost-Linear-Size PCP Theorem).

There exists $c>0$ such that for every $\varepsilon\geq xN^{-c}$, SAT with an
input size of $n$ can be reduced to a projection game of input size
$N=n^{1+o(1)}\cdot\text{poly}\left(\frac{1}{\varepsilon}\right)$ over an
alphabet of size $\text{exp}\left(\frac{1}{\varepsilon}\right)$ and soundness
error $\varepsilon$.

In [13], Moshkovitz adapts the Sliding Scale Conjecture of Bellare _et al._
(Conjecture 3.2) to this framework, and conjectures that the alphabet size can
be made polynomial in $\frac{1}{\varepsilon}$ rather than exponential. The
formal statement of the conjecture is as follows:

######  Conjecture 7.5 (Projection Games Conjecture).

There exists $c>0$ such that for every $\varepsilon\geq N^{-c}$, SAT with an
input size of $n$ can be reduced to a projection game of input size
$N=n^{1+o(1)}\cdot\text{poly}\left(\frac{1}{\varepsilon}\right)$ over an
alphabet of size $\text{poly}\left(\frac{1}{\varepsilon}\right)$ and soundness
error $\varepsilon$.

In both of the above, we may assume without loss of generality that the
projection game is _bi-regular_ , meaning that all $a\in A$ share a common
degree and so do all $b\in B$, though they need not be the same degree for
both $A$ and $B$.

We will ultimately formulate the core lemma of Moshkovitz in terms of this
conjecture. The full form of the conjecture is not needed to prove that Set
Cover is inapproximable; rather, only a certain weaker version of it is
necessary. This version in particular was proven by Dinur and Steurer in [5],
which leads to the tightest possible lower bound of $ln(n)$ and concludes
development of the bound.

####  7.1.3 Agreement

Let $G=((A,B),E)$ and assume that $(G,\Sigma_{A},\Sigma_{B},\Phi)$ is a
projection game for deciding SAT. Let $\phi_{A}$ be a labeling of $A$. We say
that $A$’s vertices _totally disagree_ on a vertex $b\in B$ if, for all pairs
of neighbors $a_{1},a_{2}\in A$ of $b$, the edges $e_{1}=(a_{1},b)$ and
$e_{2}=(a_{2},b)$ are associated with projections $\pi_{1}$ and $\pi_{2}$ for
which $\pi_{1}(\phi_{A}(a_{1}))\neq\pi_{2}(\phi_{A}(a_{2}))$. In effect, this
means that every pair of neighbors of $b$ is connected by edges whose
projections map those neighbors’ labels to different elements of $\Sigma_{b}$
(this is independent of whether or not they agree with the labeling of $b$).
This induces the following definition:

######  Definition 7.6 (Agreement Soundness Error).

Consider an unsatisfiable formula $\varphi$ and the projection game
$(G,\Sigma_{A},\Sigma_{B},\Phi)$ as described above. The graph $G$ has
_agreement soundness error_ $\varepsilon$ if, for any labeling $\phi_{A}$,
$A$’s vertices totally disagree on at least a $(1-\varepsilon)$ fraction of
the $b\in B$.

Moshkovitz presents two lemmas about agreement. The first asserts that there
is a way to construct bi-regular graphs such that any fine-enough partition of
the first vertex set forces most vertices of the second vertex set to be
connected to many different subsets of the partition. The second connects
agreement soundness to the overall soundness of a projection game.

######  Lemma 7.7.

For $0<\varepsilon<1$, for infinitely many $n$ and $D$, there is an explicit
construction of a bi-regular graph $H=((U,V),E)$ with $|U|=n$, $V$-degree $D$,
and $|V|\leq n^{\mathcal{O}(1)}$ such that the following property holds:

  * •

For every partition of $U$ into subsets $U_{1},\dots,U_{m}$ such that
$|U_{i}|\leq\varepsilon|U|$ for all $i$, the fraction of vertices $v\in V$
with more than one neighbor in any $U_{i}$ is at most $\varepsilon D^{2}$.

######  Lemma 7.8.

Let $D\geq 2$ and $\varepsilon>0$. Given a projection game with soundness
error $\varepsilon^{2}D^{2}$, we can construct a projection game with
agreement soundness error $2\varepsilon D^{2}$ and $B$-degree $D$ in its
second vertex set. The transformation preserves the alphabets and increases
the game size by only a constant factor.

####  7.1.4 List-Agreement

There is a generalization of agreement known as list-agreement, which operates
under _$\ell$ -labelings_, a more general version of labelings that assign
$\ell$ labels to each vertex rather than just one. As before, let
$G=((A,B),E)$ and assume that $(G,\Sigma_{A},\Sigma_{B},\Phi)$ is a projection
game for deciding SAT. For $\ell\geq 1$, let
$\widehat{\phi_{A}}:A\to\binom{\Sigma_{A}}{\ell}$ be an $\ell$-labeling of
$A$. We say that $A$’s vertices _totally list-disagree_ on a vertex $b\in B$
if, for all pairs of neighbors $a_{1},a_{2}\in A$ of $b$, the edges
$e_{1}=(a_{1},b)$ and $e_{2}=(a_{2},b)$ are associated with projections
$\pi_{1}$ and $\pi_{2}$ such that, for all pairs of labels
$\sigma_{1}\in\widehat{\phi_{A}}(a_{1})$ and
$\sigma_{2}\in\widehat{\phi_{A}}(a_{2})$,
$\pi_{1}(\sigma_{1})\neq\pi_{2}(\sigma_{2})$. In the case of $\ell=1$, this is
exactly the original notion of total disagreement; in general, it is the
statement that the images of $\pi_{1}$ on the labels of $a_{1}$ and $\pi_{2}$
on the labels of $a_{2}$ are disjoint. As before, this induces a corresponding
notion of soundness:

######  Definition 7.9 (List-Agreement Soundness Error).

Consider an unsatisfiable formula $\varphi$ and the projection game
$(G,\Sigma_{A},\Sigma_{B},\Phi)$ as described above. The graph $G$ has _list-
agreement soundness error_ $(\ell,\varepsilon)$ if, for any $\ell$-labeling
$\widehat{\phi_{A}}$, $A$’s vertices totally list-disagree on at least a
$(1-\varepsilon)$ fraction of the $b\in B$.

There is a relationship between the agreement soundness error of a given
projection game and the corresponding list-agreement soundness error, codified
in the following lemma. The proof is short, so we present the proof as well.

######  Lemma 7.10.

Let $\ell\geq 1$ and $0<\varepsilon<1$. A projection game with agreement
soundness error $\varepsilon$ has list-agreement soundness error
$(\ell,\varepsilon\ell^{2})$.

###### Proof of Lemma 7.10.

Assume not. Then there exists some $\ell$-labeling
$\widehat{\phi_{A}}:A\to\binom{\Sigma_{A}}{\ell}$ such that, on a fraction of
of $B$’s vertices strictly larger than $\varepsilon\ell^{2}$, $A$’s vertices
do not totally list-disagree.

Define a labeling $\phi_{A}:A\to\Sigma_{a}$ by assigning each vertex $a\in A$
one of the labels in $\widehat{\phi_{A}}(a)$ at random. If some $b\in B$ has
neighbors $a_{1},a_{2}$ that do not list-disagree on $b$ under
$\widehat{\phi_{A}}$, then they agree on $b$ under $\phi_{A}$ with probability
at least $\frac{1}{\ell^{2}}$. Therefore, the expected fraction $b\in B$ that
has at least two neighbors in agreement is strictly larger than
$\varepsilon\ell^{2}\cdot\frac{1}{\ell^{2}}=\varepsilon$. However, this
fraction is also $\varepsilon$ by assumption. Contradiction as this implies
$\varepsilon>\varepsilon$. ∎

This progressive relationship between the three notions of soundness will
allow us to state and prove the core lemma of Moshkovitz’s proof.

###  7.2 The Proof

In terms of projection games, Moshkovitz seeks to prove the following lemma:

######  Lemma 7.11.

For every $0<\alpha<1$, there exists $c$ a function of $\alpha$ such that, if
the Projection Games Conjecture holds with soundness error
$\varepsilon=\frac{c}{(\log_{2}n)^{4}}$, then it is NP-hard to approximate Set
Cover on inputs of size $N=n^{\mathcal{O}(1/\alpha)}$ better than
$(1-\alpha)\ln N$.

This lemma would, contingent on the Projection Games Conjecture, close the gap
between the algorithm of Johnson given in [9] and the result of Feige. The
following corollary comes from progressively applying Lemmas 7.8 and 7.10 to
Conjecture 7.5:

######  Corollary 7.12.

For any $\ell=\text{polylog}(n)$, for any constant prime power $D\geq 2$ and
constant $0<\alpha<1$, SAT on input size $n$ can be reduced to a projection
game of size $N=\text{poly}(n)$ with alphabet size $\text{poly}(n)$ and
$B$-degree $D$, and where the list-agreement soundness error is
$(\ell,\alpha)$.

With this corollary, we are able to set up and prove Lemma 7.11.

####  7.2.1 Initial Setup

Let $\mathcal{G}$ be a projection game for SAT as in Corollary 7.12. Assume
$\mathcal{G}$ is bi-regular with $A$-degree $D_{A}$ and $B$-degree $D_{B}$. We
will construct a partition system $\beta(m,\mathcal{L},k,d)$ as in Definition
6.6 corresponding to $\mathcal{G}$. Recall that this construction is
deterministic and efficient by Theorem 5.5. Additionally, unlike Feige, this
proof requires just one partition system. The parameters will be as follows:

  * •

The universe set will be $\beta$, with $|\beta|=m\leq\text{poly}(k^{\log
k},\log\ell)$.

  * •

The number of partitions will be $\mathcal{L}=|\Sigma_{B}|$.

  * •

The number of sets per partition will be $k=D_{B}$.

  * •

The minimum set requirement $d$ will be $k\ln m(1-\alpha)$ for
$\alpha\leq\frac{2}{k}$.

Next, associate each partition of $\beta$ with a character in $\Sigma_{B}$, as
in $P_{\sigma_{1}},\dots,P_{\sigma_{\mathcal{L}}}$. Associate each set within
each partition with an index in $[k]$. Similarly, for each vertex $b\in B$,
associate each incident edge $e=(a,b)$ with an index in $[k]$.

We will construct a Set Cover instance $\mathcal{S}$. The universe will be
$\beta\times B$. We will include a subset $S_{a,\sigma}$ for every vertex
$a\in A$ and every character $\sigma\in\Sigma_{A}$. To construct these
subsets, do the following for each edge $e=(a,b)$ adjacent to $a$: Look at the
index $j_{e}$ associated with that edge by vertex $b$. Then, take the subset
$S_{j_{e}}$ associated with index $j_{e}$ in the partition corresponding to
the character that is the image of $\sigma$ under the projection $\pi_{e}$.
The subset $S_{a,\sigma}$ can then be defined as

$S_{a,\sigma}=\bigcup_{e=(a,b)\text{ for some }b}S_{j_{e}}$

which completes the construction. A diagram of Moshkovitz’s construction can
be seen in Figure 7.2.

Set Cover InstanceUniverse SetSubsetsPartition SystemUniverse
SetPartitionsSets in PartitionsProjection Game for SATBipartition $A$Alphabet
$\Sigma_{A}$Bipartition $B$Alphabet $\Sigma_{B}$Edges $E$Projections $\pi_{i}$
Figure 7.2: A diagram of Moshkovitz’s proof structure.

####  7.2.2 Completeness and Soundness

We seek to prove that this reduction satisfies completeness and soundness.
Completeness is relatively trivial; the statement is as follows:

######  Lemma 7.13 (Completeness).

If all the edges in projection game $\mathcal{G}$ can be satisfied, then
$\mathcal{S}$ has a covering of size $|A|$.

The proof is simple and is obtained by taking the cover corresponding to the
satisfying labeling. The question of soundness is more difficult:

######  Lemma 7.14 (Soundness).

Recall $d=k\ln m(1-\alpha)$. If $\mathcal{G}$ has list-agreement soundness
$(d,\alpha)$, then every covering of $\mathcal{S}$ is strictly larger than
$|A|\ln m(1-2\alpha)$.

###### Proof of Lemma 7.14.

Assume not. Then, there exists a covering $\mathcal{C}$ of size at most
$|A|\ln m(1-2\alpha)$. Define costs $c(a)$ and $c(b)$ for every $a\in A$ and
$b\in B$ as follows:

  * •

For every $a\in A$, let $c(a)$ be the number of sets $S_{a,\sigma}$ in the
covering $\mathcal{C}$. Note that by construction, $\sum_{a\in
A}s_{a}=|\mathcal{C}|$.

  * •

For every $b\in B$, let $c(b)$ be the number of sets in the covering
$\mathcal{C}$ that participate in covering the portion $\beta\times\\{b\\}$.

Observe that

$\sum_{b\in B}s_{b}=D_{A}\sum_{a\in A}s_{a}$

by construction. By the upper bound on the covering size, and the fact that
$D_{A}|A|=D_{B}|B|$ due to bipartiteness, we get

$\sum_{b\in B}s_{b}=D_{A}\sum_{a\in A}s_{a}\leq D_{A}|A|\ln
m(1-2\alpha)=D_{B}|B|\ln m(1-2\alpha)$

This means that, in expectation over all $b\in B$, each universe
$\beta\times\\{b\\}$ is covered by at most $D_{B}\ln m(1-2\alpha)$ sets.
Recall that the minimum set requirement $d$ of the partition system is equal
to $D_{B}\ln m(1-alpha)$. By Markov’s Inequality, at least an $\alpha$
fraction of $b\in B$ have their corresponding universe $\beta\times\\{b\\}$
covered by at most $d$ sets. By the property of the partition system, for
these $b$, each must have two incident edges whose projections agree on some
character in the labelings of the two paired vertices of $A$.

Now, consider the $\ell$-labeling
$\widehat{\phi_{A}}:A\to\binom{\Sigma_{A}}{d}$ where, for every $a\in A$, the
label is made of $d$ symbols $\sigma$ for which $S_{a,\sigma}$ is in
$\mathcal{C}$, with arbitrary symbols added as padding if there are not
enough. Then, for the $\alpha$-fraction of $b$ described above, $A$’s vertices
will not totally list-disagree. Contradiction as $\mathcal{G}$ has list-
agreement soundness $(d,\alpha)$. ∎

To complete the reduction, fix a constant $0<\alpha<1$. Assume that the
Projection Games Conjecture holds for $\varepsilon=\frac{c}{(\log_{2}n)^{4}}$
for some constant $c$ depending only on $\alpha$. This enables us to use
Corollary 7.12 to generate a projection game for SAT with list-agreement
soundness $(d,\alpha)$. Let $N=m|B|$ be the number of elements in the universe
set of the Set Cover instance $\mathcal{S}$. Take $m=\Theta(|B|^{1/\alpha})$;
this may require duplicating elements. Then $\ln N=(1+\alpha)\ln m$ with an
approximation ratio of at least $(1-3\alpha)\ln N$. The entire reduction is
polynomial in $n$. This proves Lemma 7.11.

##  8 Dinur and Steurer, 2014 [5]

The contribution of Dinur and Steurer is a proof of the weaker version of
Conjecture 7.5 necessary to achieve the results of Moshkovitz. In particular,
they prove the following result about the Label Cover problem:

######  Theorem 8.1.

For every constant $c>0$, given a Label Cover instance of size $n$ with
alphabet size at most $n$, it is NP-hard to decide if its value is 1 or at
most $\varepsilon=(\log n)^{-c}$.

This is sufficient to prove Lemma 7.11 without reliance on a conjecture, hence
proving that Set Cover is inapproximable within $(1-\varepsilon)\ln n$ for any
$0<\varepsilon<1$. We therefore arrive at the current result of Theorem 1.3.

## Appendix A: Chronological Timelines

###  I Chronological Timeline with Results as Stated

The following timeline presents approximate order of _initial_ results, with
the years representing the final dates of publication of each paper. The
values given are the new lower bounds on approximability of Set Cover; note
that the main paper presents theorems largely in terms of _upper_ bounds on
_inapproximability_. See Section 1.2 for more.

Lund and Yannakakis, 1994 [12] $\frac{1}{4}\log_{2}(n)$ if
$\text{NP}\nsubseteq\text{DTIME}(n^{\text{polylog }n})$
$\frac{1}{2}\log_{2}(n)$ if $\text{NP}\nsubseteq\text{ZTIME}(n^{\text{polylog
}n})$ Bellare, Goldwasser, Lund and Russell, 1993 [4] $c$ for any constant $c$
if $\text{P}\neq\text{NP}$ $\frac{1}{8}\log_{2}(n)$ if
$\text{NP}\nsubseteq\text{DTIME}(n^{\mathcal{O}(\log\log n)})$ Raz, 1998 [16]
$\frac{1}{4}\log_{2}(n)$ if
$\text{NP}\nsubseteq\text{DTIME}(n^{\mathcal{O}(\log\log n)})$
$\frac{1}{2}\log_{2}(n)$ if
$\text{NP}\nsubseteq\text{ZTIME}(n^{\mathcal{O}(\log\log n)})$ Naor, Schulman,
and Srinivasan, 1995 [15] $\frac{1}{2}\log_{2}(n)$ if
$\text{NP}\nsubseteq\text{DTIME}(n^{\mathcal{O}(\log\log n)})$ Feige, 1998 [6]
$\ln(n)$ if $\text{NP}\nsubseteq\text{DTIME}(n^{\mathcal{O}(\log\log n)})$
Moshkovitz, 2015 [13] $\ln(n)$ if $\text{P}\neq\text{NP}$ and the Projection
Games Conjecture holds Dinur and Steurer, 2014 [5] $\ln(n)$ if
$\text{P}\neq\text{NP}$

###  II Chronological Timeline in Terms of $\ln(n)$

The following timeline again presents approximate order of _initial_ results,
with dates given being actual publication dates. Because logarithms differ
from one another by only a constant factor, it is possible to present all
results of the timeline in terms of $\ln(n)$. This timeline is presented as a
way of clearly observing the improvement in results. Decimals are rounded to
the nearest thousandth.

Lund and Yannakakis, 1994 [12] $0.361\ln(n)$ if
$\text{NP}\nsubseteq\text{DTIME}(n^{\text{polylog }n})$ $0.721\ln(n)$ if
$\text{NP}\nsubseteq\text{ZTIME}(n^{\text{polylog }n})$ Bellare, Goldwasser,
Lund and Russell, 1993 [4] $c$ for any constant $c$ if $\text{P}\neq\text{NP}$
$0.180\ln(n)$ if $\text{NP}\nsubseteq\text{DTIME}(n^{\mathcal{O}(\log\log
n)})$ Raz, 1998 [16] $0.361\ln(n)$ if
$\text{NP}\nsubseteq\text{DTIME}(n^{\mathcal{O}(\log\log n)})$ $0.721\ln(n)$
if $\text{NP}\nsubseteq\text{ZTIME}(n^{\mathcal{O}(\log\log n)})$ Naor,
Schulman, and Srinivasan, 1995 [15] $0.721\ln(n)$ if
$\text{NP}\nsubseteq\text{DTIME}(n^{\mathcal{O}(\log\log n)})$ Feige, 1998 [6]
$\ln(n)$ if $\text{NP}\nsubseteq\text{DTIME}(n^{\mathcal{O}(\log\log n)})$
Moshkovitz, 2015 [13] $\ln(n)$ if $\text{P}\neq\text{NP}$ and the Projection
Games Conjecture holds Dinur and Steurer, 2014 [5] $\ln(n)$ if
$\text{P}\neq\text{NP}$

## References

  * [1] S. Arora.  Probabilistic Checking of Proofs and Hardness of Approximation Problems.  PhD thesis, University of California at Berkeley, USA, 1995.  UMI Order No. GAX95-30468.
  * [2] S. Arora and S. Safra.  Probabilistic checking of proofs: A new characterization of np.  J. ACM, 45(1):70–122, Jan. 1998.
  * [3] L. Babai and S. Moran.  Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes.  J. Comput. Syst. Sci., 36:254–276, 1988.
  * [4] M. Bellare, S. Goldwasser, C. Lund, and A. Russell.  Efficient probabilistically checkable proofs and applications to approximations.  In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’93, page 294–304, New York, NY, USA, 1993. Association for Computing Machinery.
  * [5] I. Dinur and D. Steurer.  Analytical approach to parallel repetition.  In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 624-633, New York, NY, USA, 2014. Association for Computing Machinery.
  * [6] U. Feige.  A threshold of ln n for approximating set cover.  J. ACM, 45(4):634–652, July 1998.
  * [7] U. Feige and L. Lovász.  Two-prover one-round proof systems: Their power and their problems (extended abstract).  In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’92, page 733–744, New York, NY, USA, 1992. Association for Computing Machinery.
  * [8] S. Goldwasser, S. Micali, and C. Rackoff.  The knowledge complexity of interactive proof systems.  SIAM J. Comput., 18(1):186–208, Feb. 1989.
  * [9] D. S. Johnson.  Approximation algorithms for combinatorial problems.  Journal of Computer and System Sciences, 9(3):256–278, 1974.
  * [10] R. M. Karp.  Reducibility among combinatorial problems.  In R. E. Miller, J. W. Thatcher, and J. D. Bohlinger, editors, Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, pages 85–103, Boston, MA, 1972. Springer US.
  * [11] L. Lovász.  On the ratio of optimal integral and fractional covers.  Discrete Mathematics, 13(4):383–390, 1975.
  * [12] C. Lund and M. Yannakakis.  On the hardness of approximating minimization problems.  Journal of the ACM, 41(5):960–981, 1994.
  * [13] D. Moshkovitz.  The projection games conjecture and the np-hardness of ln $n$-approximating set-cover.  Theory of Computing, 11(7):221–235, 2015.
  * [14] D. Moshkovitz and R. Raz.  Two-query pcp with subconstant error.  J. ACM, 57(5), June 2008.
  * [15] M. Naor, L. Schulman, and A. Srinivasan.  Splitters and near-optimal derandomization.  In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 182–191, 1995.
  * [16] R. Raz.  A parallel repetition theorem.  SIAM Journal on Computing, 27(3):763–803, 1998.