Computationally Efficient Error-Correcting Codes and Holographic Proofs

Table of Contents

   1 Introduction
       1.1 Error-correcting codes
       1.2 The purpose of proofs
       1.3 Structure of this thesis
       1.4 An introduction to error-correcting codes
           1.4.1 Linear codes
           1.4.2 Asymptotic bounds
       1.5 The complexity of coding
   2 Expander codes
       2.1 Introduction to expander graphs
           2.1.1 The expansion of random graphs
       2.2 Expander codes
       2.3 A simple example
           2.3.1 Sequential decoding
           2.3.2 Necessity of Expansion
           2.3.3 Parallel decoding
       2.4 Explicit constructions of expander graphs
           2.4.1 Expander graphs of every size
       2.5 Explicit constructions of expander codes
           2.5.1 A generalization
       2.6 Notes on implementation and experimental results
           2.6.1 Some experiments
   3 Linear-time encodable and decodable error-correcting codes
       3.1 Motivating the construction
       3.2 Error-reducing codes
       3.3 Error-correcting codes
       3.4 Explicit Constructions
       3.5 Some thoughts on implementation and future work
   4 Holographic Proofs
           4.0.1 Outline of Chapter
       4.1 Checkable and verifiable codes
       4.2 Bi and Trivariate codes
           4.2.1 The First Step
           4.2.2 Resultants
           4.2.3 Presentation checking theorems
           4.2.4 Using Bezout's Theorem 
           4.2.5 Sub-presentations and verification 
       4.3 A simple holographic proof system 
           4.3.1 Choosing a key problem 
           4.3.2 Algebraically simple graphs 
           4.3.3 Arithmetizing the graph coloring problem 
           4.3.4 A Holographic Proof 
       4.4 Recursion 
           4.4.1 Encoded inputs 
           4.4.2 Using the Fast Fourier Transform 
       4.5 Efficient proof checkers 
       4.6 The coloring problem of Babai, Fortnow, Levin, and Szegedy 
   5 Connections 
       5.1 Are checkable codes necessary for holographic proofs? 
  Bibliography 
  Index