← All blueprints
1
The Fundamental Question
1
The Basics
▶
2
A Look at Some Nicely Behaved Codes: Linear Codes
▶
2.3.1 On the Distance of a Linear Code
3
Probability as Fancy Counting and the q-ary Entropy Function
▶
3.1
A Crash Course on Probability
3.2
The Probabilistic Method
3.3
The q-ary Entropy Function
2
The Combinatorics
▶
4
What Can and Cannot Be Done – I
▶
Asymptotically good code families
4.1
Asymptotic Version of the Hamming Bound
4.2
Gilbert-Varshamov Bound
4.3
Singleton Bound
4.4
Plotkin Bound
5
The Greatest Code of Them All: Reed-Solomon Codes
6
What Happens When the Noise is Stochastic: Shannon’s Theorem
7
Bridging the Gap Between Shannon and Hamming: List Decoding
8
What Cannot be Done – II
▶
8.1
Elias-Bassalygo bound
8.2
The linear programming bounds
8.3
A Breather
3
The Codes
▶
9
When Polynomials Save the Day: Polynomial Based Codes
10
From Large to Small Alphabets: Code Concatenation
▶
10.1
Code Concatenation: The Basic Idea
10.2
Zyablov Bound
10.3
Advanced Concatenation and Strongly Explicit Constructions
10.4
Summary of Concatenation
11
When Graphs Come to the Party: Expander Codes
▶
11.1
Graphs
11.2
Expander Graphs
11.3
Basic Expander Codes
11.4
Codes from Weaker Expanders
11.5
Distance Amplification
11.6
Existence of Lossless Expanders
4
The Algorithms
▶
12
Efficient Decoding of Reed-Solomon Codes
▶
12.1
Unique decoding of Reed-Solomon codes
12.2
List Decoding Reed-Solomon Codes
12.3
Extensions
13
Decoding Reed-Muller Codes
▶
13.1
A natural decoding algorithm
13.2
Majority logic decoding
13.3
Decoding by reduction to Reed-Solomon decoding
14
Decoding Concatenated Codes
▶
14.1
A Natural Decoding Algorithm
14.2
Decoding From Errors and Erasures
14.3
Generalized Minimum Distance Decoding
15
Efficiently Achieving the Capacity of the BSC_p
▶
15.1
Achieving Capacity of BSC_p
15.2
Decoding Error Probability
15.3
The Inner Code
15.4
The Outer Code
15.5
Discussion
16
Information Theory Strikes Back: Polar Codes
▶
16.1 Achieving Gap to Capacity
16.2 Reduction to Linear Compression
16.3 The Polarization Phenomenon
16.4 Polar Codes, Encoder and Decoder
16.5 Analysis: Speed of Polarization
16.7 Summary and Additional Information
17
Efficiently Achieving List Decoding Capacity
▶
17.1
Folded Reed-Solomon Codes
17.2
List Decoding Folded Reed-Solomon Codes: I
17.3
List Decoding Folded Reed-Solomon Codes: II
18
Fast Encoding: Linear Time Encodable Codes
▶
18.1
Overview of the construction
18.2
Low-density Error-Reduction Codes
18.3
The error-correcting code: Recursive construction
18.4
Analysis
19
Recovering Very Locally: Locally Recoverable Codes
5
The Applications
▶
20
Cutting Data Down to Size: Hashing
21
Securing Your Fingerprints: Fuzzy Vaults
▶
21.1
Some quick background on fingerprints
21.2
The Fuzzy Vault Problem
21.3
The Final Fuzzy Vault
22
Finding Defectives: Group Testing
▶
22.4.1 Kautz–Singleton Construction
22.5.1 Connection to Group Testing
23
Complexity of Coding Problems
▶
23.1
Nearest Codeword Problem (NCP)
23.2
Decoding with Preprocessing
23.3
Approximate NCP
23.4
Distance bounded decoding
23.5
Minimum distance problem
23.6
Conclusions
24
Giving Computational Complexity a Helping Hand
▶
24.1
Communication Complexity
24.2
Derandomization and Pseudorandomness
24.3
Hardcore Predicates
24.4
Average case complexity
6
Appendices
▶
25
Appendix B. Some Useful Facts
▶
25.1
B.1 Some Useful Inequalities
25.2
B.2 Some Useful Identities and Bounds
26
Appendix C. Background on Asymptotic Notation, Algorithms and Complexity
▶
C.1 Asymptotic Notation
C.2 Bounding Algorithm run time
C.3 Randomized Algorithms
C.4 Efficient Algorithms
C.5 More on intractability
27
Appendix D. Basic Algebraic Algorithms
▶
D.2 Groups, Rings, Fields
D.3 Polynomials
D.4 Vector Spaces
D.5 Finite Fields
D.6 Algorithmic Aspects of Finite Fields
D.7 Algorithmic Aspects of Polynomials
28
Appendix E. Some Information Theory Essentials
Dependency graph
Essential Coding Theory — Blueprint
V. Guruswami, A. Rudra, M. Sudan
1
The Fundamental Question
1
The Basics
2
A Look at Some Nicely Behaved Codes: Linear Codes
2.3.1 On the Distance of a Linear Code
3
Probability as Fancy Counting and the q-ary Entropy Function
3.1
A Crash Course on Probability
3.2
The Probabilistic Method
3.3
The q-ary Entropy Function
2
The Combinatorics
4
What Can and Cannot Be Done – I
Asymptotically good code families
4.1
Asymptotic Version of the Hamming Bound
4.2
Gilbert-Varshamov Bound
4.3
Singleton Bound
4.4
Plotkin Bound
5
The Greatest Code of Them All: Reed-Solomon Codes
6
What Happens When the Noise is Stochastic: Shannon’s Theorem
7
Bridging the Gap Between Shannon and Hamming: List Decoding
8
What Cannot be Done – II
8.1
Elias-Bassalygo bound
8.2
The linear programming bounds
8.3
A Breather
3
The Codes
9
When Polynomials Save the Day: Polynomial Based Codes
10
From Large to Small Alphabets: Code Concatenation
10.1
Code Concatenation: The Basic Idea
10.2
Zyablov Bound
10.3
Advanced Concatenation and Strongly Explicit Constructions
10.4
Summary of Concatenation
11
When Graphs Come to the Party: Expander Codes
11.1
Graphs
11.2
Expander Graphs
11.3
Basic Expander Codes
11.4
Codes from Weaker Expanders
11.5
Distance Amplification
11.6
Existence of Lossless Expanders
4
The Algorithms
12
Efficient Decoding of Reed-Solomon Codes
12.1
Unique decoding of Reed-Solomon codes
12.2
List Decoding Reed-Solomon Codes
12.3
Extensions
13
Decoding Reed-Muller Codes
13.1
A natural decoding algorithm
13.2
Majority logic decoding
13.3
Decoding by reduction to Reed-Solomon decoding
14
Decoding Concatenated Codes
14.1
A Natural Decoding Algorithm
14.2
Decoding From Errors and Erasures
14.3
Generalized Minimum Distance Decoding
15
Efficiently Achieving the Capacity of the BSC_p
15.1
Achieving Capacity of BSC_p
15.2
Decoding Error Probability
15.3
The Inner Code
15.4
The Outer Code
15.5
Discussion
16
Information Theory Strikes Back: Polar Codes
16.1 Achieving Gap to Capacity
16.2 Reduction to Linear Compression
16.3 The Polarization Phenomenon
16.4 Polar Codes, Encoder and Decoder
16.5 Analysis: Speed of Polarization
16.7 Summary and Additional Information
17
Efficiently Achieving List Decoding Capacity
17.1
Folded Reed-Solomon Codes
17.2
List Decoding Folded Reed-Solomon Codes: I
17.3
List Decoding Folded Reed-Solomon Codes: II
18
Fast Encoding: Linear Time Encodable Codes
18.1
Overview of the construction
18.2
Low-density Error-Reduction Codes
18.3
The error-correcting code: Recursive construction
18.4
Analysis
19
Recovering Very Locally: Locally Recoverable Codes
5
The Applications
20
Cutting Data Down to Size: Hashing
21
Securing Your Fingerprints: Fuzzy Vaults
21.1
Some quick background on fingerprints
21.2
The Fuzzy Vault Problem
21.3
The Final Fuzzy Vault
22
Finding Defectives: Group Testing
22.4.1 Kautz–Singleton Construction
22.5.1 Connection to Group Testing
23
Complexity of Coding Problems
23.1
Nearest Codeword Problem (NCP)
23.2
Decoding with Preprocessing
23.3
Approximate NCP
23.4
Distance bounded decoding
23.5
Minimum distance problem
23.6
Conclusions
24
Giving Computational Complexity a Helping Hand
24.1
Communication Complexity
24.2
Derandomization and Pseudorandomness
24.3
Hardcore Predicates
24.4
Average case complexity
6
Appendices
25
Appendix B. Some Useful Facts
25.1
B.1 Some Useful Inequalities
25.2
B.2 Some Useful Identities and Bounds
26
Appendix C. Background on Asymptotic Notation, Algorithms and Complexity
C.1 Asymptotic Notation
C.2 Bounding Algorithm run time
C.3 Randomized Algorithms
C.4 Efficient Algorithms
C.5 More on intractability
27
Appendix D. Basic Algebraic Algorithms
D.2 Groups, Rings, Fields
D.3 Polynomials
D.4 Vector Spaces
D.5 Finite Fields
D.6 Algorithmic Aspects of Finite Fields
D.7 Algorithmic Aspects of Polynomials
28
Appendix E. Some Information Theory Essentials