## Robust PCPs of Proximity and Shorter PCPs

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

[ ps | gzipped ps | pdf | gzipped pdf ]
Massachusetts Institute of Technology 2004)

``` 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

Bibliograpy
```