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
Bibliograpy
Free gsview and ghostview
viewers for postscript.
Free Adobe PDF Reader
