Robust PCPs of Proximity and Shorter PCPs

My PhD Thesis was done under the supervision of Prof. Madhu Sudan at MIT in 2004.

Download: [ pdf ]

(© Massachusetts Institute of Technology 2004)

Table of Contents

• 1 Introduction
  • 1.1 Complexity Theory via Proofs
  • 1.2 Probabilistically Checkable Proofs
  • 1.3 Contributions of Thesis
  • 1.4 Structure of this Thesis
• 2 PCPs and variants
  • 2.1 Standard PCPs
  • 2.2 PCPs of Proximity
  • 2.3 Robust Soundness
  • 2.4 Various observations and transformations
• 3 Composition of Robust PCPs of Proximity
  • 3.1 Why composition?
  • 3.2 Composition Theorem
  • 3.3 Building block for composition
  • 3.4 Relation to Assignment Testers of Dinur and Reingold
• 4 A constant-query, exponential-sized PCP of proximity
  • 4.1 Constant query PCP of proximity
• Part I: Proof of the PCP Theorem
• 5 Proof of the PCP Theorem
  • 5.1 Introduction
  • 5.2 Composing the Main Construct
  • 5.3 Robust PCPPs for Two Problems
  • 5.4 A robust PCPP for Circuit Value
• Part II: Short PCPs
• 6 Introduction
  • 6.1 Introduction - Main Construct
  • 6.2 Saving on Randomness
  • 6.3 Overview of Main Construct
• 7 A randomness-efficient PCP
  • 7.1 Introduction
  • 7.2 Well-structured Boolean circuits
  • 7.3 Arithmetization
  • 7.4 The PCP verifier
  • 7.5 Analysis of the PCP verifier
• 8 A randomness-efficient PCP of proximity
  • 8.1 Introduction
  • 8.2 Proof of Theorem 8.1.1
• 9 A randomness-efficient robust PCP of proximity
  • 9.1 Introduction
  • 9.2 Robustness of individual tests
  • 9.3 Bundling
  • 9.4 Robustness over the binary alphabet
  • 9.5 Linearity of encoding
• 10 Putting them together: Very short PCPs with very few queries
  • 10.1 Main Construct - Recalled
  • 10.2 Composing the Main Construct
• Part III: Coding Theory Applications
• 11 Introduction
  • 11.1 Coding Theory
  • 11.2 Sublinear time algorithms
  • 11.3 Locally Testable Codes
  • 11.4 Locally Decodable Codes
• 12 Locally Testable Codes
  • 12.1 Definitions
  • 12.2 Constructions
• 13 Relaxed Locally Decodable codes
  • 13.1 Definitions
  • 13.2 Constructions
• Appendix
• A Low Degree Test
  • A.1 The Line-Point Test
  • A.2 Randomness-efficient low-degree tests and the sampling lemma
• Bibliography