<p>I think the best known result is that the blow-up can be quasi-linear (the new instance has size $n\cdot(\log n)^{O(1)}$). This is given in <a href="http://www.cs.toronto.edu/~toni/Courses/PCP/handouts/pcp-dinur.pdf" rel="nofollow noreferrer">Dinur's 2007 paper</a> (Thm 8.1), which is also cited by the Moshkovitz-Raz paper mentioned by Yuval Filmus. </p>

<p>As far as I know it is still open if the blow-up can be brought down to linear. Some people call this the Linear PCP conjecture, see e.g. the <a href="https://arxiv.org/abs/1601.04935" rel="nofollow noreferrer">recent paper</a> by Bonnet, Egri and Marx</p>

CC BY-SA 3.0
2017-02-07T13:55:11.650Z
Assuming such hypothesis can we prove that Approximating Exact-set cover is ETH-hard? http://cstheory.stackexchange.com/questions/37461/is-approximating-exact-set-cover-np-hard-for-constant-approximation-factor-eth
xyz
CC BY-SA 3.0
2017-02-07T13:47:19.230Z
2017-02-07T13:47:19.230Z
Michael Lampis
<p>The PCP theorem can be stated like this : </p>

<p>There is a polynomial time reduction from SAT to  $Gap\text-MAX\text-3SAT_{c}$ i.e. there is a reduction that maps an instance $\phi$ of SAT to an instance $\psi$ of  $Gap\text-MAX\text-3SAT_{c}$ such that </p>

<ul>
<li>If $\phi$ is satisfiable, so is $\psi$.</li>
<li>If $\phi$ is unsatisfiable, then $OPT(\psi) \leq c$, i.e., there is no assignment to the variables of $\psi$ that satisfies more than a fraction $c$ of the  clauses.</li>
</ul>

<p>What is the blow-up of this reduction? That is, what are the parameters of the instanceof  $Gap\text-MAX\text-3SAT_{c}$ in terms of parameter of the given instance of SAT. Is the blow-up linear?</p>

CC BY-SA 3.0
2017-02-07T13:23:06.577Z
[Moshkovitz-Raz](http://www.wisdom.weizmann.ac.il/~ranraz/publications/Ptwo-prover.pdf) appears to give a "quasiquadratic" blow-up, $O(n^{2+o(1)})$.
Yuval Filmus
CC BY-SA 4.0
2018-05-11T04:10:58.333Z
@YuvalFilmus Does the blow-up not depend on the choice of $c$? Intuitively, I would guess that as $c$ gets closer to 7/8, the blow-up gets larger. Is this not correct?
Mike Battaglia
CC BY-SA 4.0
2018-05-11T06:26:56.100Z
This indeed sounds likely.
Yuval Filmus
<cc.complexity-theory><reference-request><np-hardness><np-complete><p-vs-np>
ETH-Hardness of $Gap\text-MAX\text-3SAT_{c}$
xyz
# ETH-Hardness of $Gap\text-MAX\text-3SAT_{c}$

(Asked by: username_0 on 2017-02-07)

The PCP theorem can be stated like this :

There is a polynomial time reduction from SAT to $Gap\text-MAX\text-3SAT\_{c}$ i.e. there is a reduction that maps an instance $\phi$ of SAT to an instance $\psi$ of $Gap\text-MAX\text-3SAT\_{c}$ such that

* If $\phi$ is satisfiable, so is $\psi$.
* If $\phi$ is unsatisfiable, then $OPT(\psi) \leq c$, i.e., there is no assignment to the variables of $\psi$ that satisfies more than a fraction $c$ of the clauses.

What is the blow-up of this reduction? That is, what are the parameters of the instanceof $Gap\text-MAX\text-3SAT\_{c}$ in terms of parameter of the given instance of SAT. Is the blow-up linear?

**Tags:** cc.complexity-theory, reference-request, np-hardness, np-complete, p-vs-np
> **Comments:**
> **username_1**: [Moshkovitz-Raz](http://www.wisdom.weizmann.ac.il/~ranraz/publications/Ptwo-prover.pdf) appears to give a "quasiquadratic" blow-up, $O(n^{2+o(1)})$.  
> **username_2**: @YuvalFilmus Does the blow-up not depend on the choice of $c$? Intuitively, I would guess that as $c$ gets closer to 7/8, the blow-up gets larger. Is this not correct?  
> **username_1**: This indeed sounds likely.  

---

## 1 answers

### Answer by username_3 on 2017-02-07. Score: 4 | Accepted answer

I think the best known result is that the blow-up can be quasi-linear (the new instance has size $n\cdot(\log n)^{O(1)}$). This is given in [Dinur's 2007 paper](http://www.cs.toronto.edu/~toni/Courses/PCP/handouts/pcp-dinur.pdf) (Thm 8.1), which is also cited by the Moshkovitz-Raz paper mentioned by Yuval Filmus.

As far as I know it is still open if the blow-up can be brought down to linear. Some people call this the Linear PCP conjecture, see e.g. the [recent paper](https://arxiv.org/abs/1601.04935) by Bonnet, Egri and Marx

> **Comments:**
> **username_0**: Assuming such hypothesis can we prove that Approximating Exact-set cover is ETH-hard? http://cstheory.stackexchange.com/questions/37461/is-approximating-exact-set-cover-np-hard-for-constant-approximation-factor-eth  

---

