Bafna, Mitali ;
Vyas, Nikhil
Imperfect Gaps in GapETH and PCPs
Abstract
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 PCP_{c,s}[r,q] subseteq PCP_{1,s'}[r+O(1),q+O(r)] for cs=Omega(1) which in turn implies that one can convert imperfect completeness to perfect in linearsized 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 [Anup Rao, 2011] and pseudorandomness [David Gillman, 1998] and might be of independent interest.
We also investigate the timecomplexity of approximating perfectly satisfiable instances of 3SAT versus those with imperfect completeness. We show that the GapETH conjecture without perfect completeness is equivalent to GapETH with perfect completeness, i.e. MAX 3SAT(1epsilon,1delta), delta > epsilon has 2^{o(n)} algorithms if and only if MAX 3SAT(1,1delta) has 2^{o(n)} algorithms. We also relate the time complexities of these two problems in a more finegrained way to show that T_2(n) <= T_1(n(log log n)^{O(1)}), where T_1(n),T_2(n) denote the randomized timecomplexity of approximating MAX 3SAT with perfect and imperfect completeness respectively.
BibTeX  Entry
@InProceedings{bafna_et_al:LIPIcs:2019:10854,
author = {Mitali Bafna and Nikhil Vyas},
title = {{Imperfect Gaps in GapETH and PCPs}},
booktitle = {34th Computational Complexity Conference (CCC 2019)},
pages = {32:132:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771160},
ISSN = {18688969},
year = {2019},
volume = {137},
editor = {Amir Shpilka},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10854},
URN = {urn:nbn:de:0030drops108545},
doi = {10.4230/LIPIcs.CCC.2019.32},
annote = {Keywords: PCP, GapETH, Hardness of Approximation}
}
2019
Keywords: 

PCP, GapETH, Hardness of Approximation 
Seminar: 

34th Computational Complexity Conference (CCC 2019)

Issue date: 

2019 
Date of publication: 

2019 