Imperfect Gaps in Gap-ETH and PCPs.

We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a way to transform a PCP with imperfect completeness to one with perfect completeness, when the initial gap is a constant. We show that PCPc,s[r, q] ⊆ PCP1,s'[r + O(1), q + O(r)] for c --- s = Ω(1) which in turn implies that one can convert imperfect completeness to perfect in linear-sized PCPs for NP with a O(log n) additive loss in the query complexity q. We show our result by constructing a "robust circuit" using threshold gates. These results are a gap amplification procedure for PCPs, (when completeness is not 1) analogous to questions studied in parallel repetition [22] and pseudorandomness [15] and might be of independent interest.We also investigate the time-complexity of approximating perfectly satisfiable instances of 3SAT versus those with imperfect completeness. We show that the Gap-ETH conjecture without perfect completeness is equivalent to Gap-ETH with perfect completeness, i.e. MAX 3SAT(1 --- ∈, 1 --- δ), δ > ∈ has 2o(n) algorithms if and only if MAX 3SAT(1, 1 --- δ) has 2o(n) algorithms. We also relate the time complexities of these two problems in a more fine-grained way to show that T2(n) ≤ T1(n(log log n)O(1)), where T1(n),T2(n) denote the randomized time-complexity of approximating MAX 3SAT with perfect and imperfect completeness respectively.