Robust PCPs of Proximity and Shorter PCPs

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

You can download it any of the following formats:
[ ps | gzipped ps | pdf | gzipped pdf ]
Massachusetts Institute of Technology 2004)

Massachusetts Institute of Technology

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 

 A Low Degree Test	
	 A.1 The Line-Point Test 
	 A.2 Randomness-efficient low-degree tests and the sampling lemma


Prahladh Harsha
Valid HTML 4.01! Valid CSS!