首页    期刊浏览 2024年12月02日 星期一
登录注册

文章基本信息

  • 标题:Revisiting Alphabet Reduction in Dinur's PCP
  • 本地全文:下载
  • 作者:Venkatesan Guruswami ; Jakub Opršal ; Sai Sandeep
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-13
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Dinur's celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the expense of a fixed constant factor loss in the soundness gap). We note that the gap amplification can produce a Label Cover CSP. This allows us to reduce the alphabet size via a direct long-code based reduction from Label Cover to a Boolean CSP. Our composition step thus bypasses the concept of Assignment Testers from Dinur's proof, and we believe it is more intuitive --- it is just a gadget reduction. The analysis also uses only elementary facts (Parseval's identity) about Fourier Transforms over the hypercube.

  • 关键词:CSP ; Discrete Fourier Analysis ; Label Cover ; long code ; PCP Theorem
国家哲学社会科学文献中心版权所有