| Title: |
Imperfect gaps in Gap-ETH and PCPs |
| Authors: |
Vyas, Nikhil(Electrical engineer and computer scientist)Massachusetts Institute of Technology. |
| Contributors: |
Richard Ryan Williams.; Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.; Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| Publisher Information: |
Massachusetts Institute of Technology |
| Publication Year: |
2019 |
| Collection: |
DSpace@MIT (Massachusetts Institute of Technology) |
| Subject Terms: |
Electrical Engineering and Computer Science |
| Description: |
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019 ; Cataloged from PDF version of thesis. ; Includes bibliographical references (pages 45-47). ; In this thesis we study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a new way to transform a PCP with imperfect completeness to a PCP with perfect completeness, when the initial gap is a constant. In particular, we show that PCP[subscript c,s][r, q] [mathematical symbol] PCP[subscript 1,s'][r + 0(1), q+ 0 (r)] for c - s = [omega](1) which in turn implies that one can convert imperfect completeness to perfect in linear-sized PCPs for NTIME[0(n)] with a 0(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 imperfect), analogous to questions studied in parallel repetition [21] and pseudorandomness [141. 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; that is, MAX 3SAT(1 - [epsilon], 1 - [delta]) for [delta] > [epsilon] has 2⁰([superscript n])-time algorithms if and only if MAX 3SAT(1, 1 - [delta]) has 2⁰([superscript n])-time algorithms. We also relate the time complexities of these two problems in a more fine-grained way, to show that T₂ (n) |
| Document Type: |
thesis |
| File Description: |
47 pages; application/pdf |
| Language: |
English |
| Relation: |
https://hdl.handle.net/1721.1/122771 |
| Availability: |
https://hdl.handle.net/1721.1/122771 |
| Rights: |
MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission. ; http://dspace.mit.edu/handle/1721.1/7582 |
| Accession Number: |
edsbas.9F2AB6B0 |
| Database: |
BASE |