Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average? In this question, a 3CNF formula means a CNF formula where each clause involves exactly three distinct variables.  For a constant 0&lt;s&lt;1, Gap-3SATs is the following promise problem:

Gap-3SATs
Instance: A 3CNF formula φ.
Yes-promise: φ is satisfiable.
No-promise: No truth assignments satisfy more than s fraction of the clauses of φ.

One of the equivalent ways to state the celebrated PCP theorem [AS98, ALMSS98] is that there exists a constant 0&lt;s&lt;1 such that Gap-3SATs is NP-complete.

We say that a 3CNF formula is pairwise B-bounded if every pair of distinct variables appears in at most B clauses.  For example, a 3CNF formula (x1∨x2∨x4)∧(￢x1∨￢x3∨x4)∧(x1∨x3∨￢x5) is pairwise 2-bounded but not pairwise 1-bounded because e.g. the pair (x1, x4) appears in more than one clause.


  Question.  Do there exist constants B∈ℕ, a&gt;0, and 0&lt;s&lt;1 such that Gap-3SATs is NP-complete even for a 3CNF formula which is pairwise B-bounded and consists of at least an2 clauses, where n is the number of variables?


The pairwise boundedness clearly implies that there are only O(n2) clauses.  Together with the quadratic lower bound on the number of clauses, it roughly says that no pair of distinct variables appears in significantly more clauses than the average.

For Gap-3SAT, it is known that the sparse case is hard: there exists a constant 0&lt;s&lt;1 such that Gap-3SATs is NP-complete even for a 3CNF formula where each variable occurs exactly five times [Fei98].  On the other hand, the dense case is easy: Max-3SAT admits a PTAS for a 3CNF formula with Ω(n3) distinct clauses [AKK99], and therefore Gap-3SATs in this case is in P for every constant 0&lt;s&lt;1.  The question asks about the middle of these two cases.

The above question arose originally in a study of quantum computational complexity, more specifically two-prover one-round interactive proof systems with entangled provers (MIP*(2,1) systems).  But I think that the question may be interesting in its own right.

References

[AKK99] Sanjeev Arora, David Karger, and Marek Karpinski.  Polynomial time approximation schemes for dense instance of NP-hard problems.  Journal of Computer and System Sciences, 58(1):193–210, Feb. 1999.  http://dx.doi.org/10.1006/jcss.1998.1605

[ALMSS98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and the hardness of approximation problems.  Journal of the ACM, 45(3):501–555, May 1998.  http://doi.acm.org/10.1145/278298.278306

[AS98] Sanjeev Arora and Shmuel Safra.  Probabilistic checking of proofs: A new characterization of NP.  Journal of the ACM, 45(1):70–122, Jan. 1998.  http://doi.acm.org/10.1145/273865.273901

[Fei98] Uriel Feige.  A threshold of ln n for approximating set cover.  Journal of the ACM, 45(4):634–652, July 1998.  http://doi.acm.org/10.1145/285055.285059
Not a full answer, but hopefully close. This is very close to Luca's comments above. I believe the answer is that at least there do exist constants B∈ℕ, a&gt;0, and 0&lt;s&lt;1 such that Gap-3SATs is NP-complete even for a 3CNF formula which is pairwise B-bounded and consists of at least $an^{2-\epsilon}$ clauses, for any constant $\epsilon$.

The proof is as follows. Consider a GAP-3SAT$_s$ instance $\phi$ on $N$ variables in which each variable appears at most 5 times. This is NP-complete, as you say in the question.

Now we create a new instance $\Phi$ as follows:


For every variable $x_i$ in $\phi$, $\Phi$ has $n$ variables $y_{ij}$.
For every set of indices $i$, $a$ and $b$ with $a\neq b$, $\Phi$ has a pair of clauses $y_{ia}∨￢y_{ib}∨￢y_{ib}$, and $y_{ib}∨￢y_{ia}∨￢y_{ia}$. I'll refer to these as comparison clauses since they ensure that $y_{ia} = y_{ib}$ if they are satisfied. 
For every clause in $\phi$ acting on variables $x_i$, $x_j$ and $x_k$, for every $a$ and $b$, $\Phi$ contains an equivalent clause, where $x_i$ is replaced by $y_{ia}$, $x_j$ is replaced by $y_{jb}$ and $x_k$ is replaced by $y_{k(a+b)}$  (here addition is done modulo $n$). I'll refer to these as inherited clauses.


The total number of variables is then $m = nN$. Note $\Phi$ has $2Nn^2$ comparison clauses and $\frac{5}{3}Nn^2$ inherited clauses, for a total of $\frac{11}{3}Nn^2$ clauses. Taking $n = N^k$ we have $m = N^{k+1}$ and the total number of clauses $C = \frac{11}{3}N^{2k+1} = \frac{11}{3}m^{2-\frac{1}{k+1}}$. We take $k = \epsilon^{-1} - 1$, so $C \propto m^{2-\epsilon}$.

Next, $\Phi$ is pairwise 8-bounded (max of 2 from the comparison clauses and 6 from the inherited clauses).

Finally, if $\phi$ is unsatisfiable, then at least $(1-s)N$ clauses are unsatisfied. Now, if $y_{ia} \neq y_{ib}$ for any $a,b$ then at least $n-1$ clauses are unsatisfied. Note that in order to satisfy the $(1-s)N$ unsatisfied clauses in a set of inherited clauses for fixed $a,b$ then the assignment of variables $y_{:a}$, $y_{:b}$ and $y_{:(a+b)}$ must differ at at least $\frac{1-s}{5}N$ positions, leaving at least $\frac{1-s}{5}N(n-1)$ comparison unsatisfiable clauses. This must hold for every choice of $a$ and $b$, so at least $\approx \frac{1-s}{5}Nn^2 = \frac{3(1-s)}{11}C$ comparison clauses must remain unsatisfied in total for enough inherited clauses to be satisfied.  If however you look at the other extreme where all comparison clauses are satisfied, then $(1-s)Nn^2 = (1-s)m^{\frac{2k+1}{k+1}} = (1-s)C$ clauses are unsatisfiable. Hence a gap remains (although reduced) with $s&#39; = \frac{4+s}{5}$.

The constants probably need to be double checked.