In this question, a 3CNF formula means a CNF formula where each clause involves exactly three distinct variables. For a constant 0<s<1, Gap-3SATs is the following promise problem:
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<s<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>0, and 0<s<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<s<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<s<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.
[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