1
Boolean Analysis — Core Definitions
▶
1.1
Overview
1.2
The Boolean hypercube and functions
1.3
Uniform measure and expectation
1.4
Walsh–Fourier characters
1.5
Fourier coefficients
1.6
Walsh expansion
1.7
Orthonormality and Parseval’s identity
1.8
Coordinate influence
1.9
Noise operator
1.10
Notable Boolean functions
1.11
Sensitivity
1.12
Properties for Arrow’s theorem
2
Arrow’s Impossibility Theorem
▶
2.1
Overview
2.2
Social choice definitions
2.3
Voter ordering model
2.4
Key correlation lemmas
2.5
Fourier formula for the cycle correlation
2.6
Acyclicity implies degree-1 structure
2.7
Degree-1 implies dictatorship
2.8
Arrow’s Impossibility Theorem
3
Error-Correcting Codes — Core Definitions
▶
3.1
Overview
3.2
Basic objects: codewords and codes
3.3
Distance, weight, and rate
3.4
Basic lemma: distance vs. block length
4
Singleton Bound
▶
4.1
Overview
4.2
Main result
5
Hamming Bound
▶
5.1
Overview
5.2
Volume formula
5.3
Disjointness of decoding balls
5.4
Hamming bound
6
Entropy and Asymptotic Bounds
▶
6.1
Overview
6.2
Asymptotic upper bound on ball size
6.3
Entropy algebra lemmas
6.4
Analytic helpers
6.5
Stirling-based binomial lower bound
6.6
Positivity of \(q\)-ary entropy
7
Linear Codes and the Uniformity Lemma
▶
7.1
Overview
7.2
Distance equals minimum weight in linear codes
7.3
Uniform distributions and random matrices
7.4
Uniformity lemma
8
Gilbert–Varshamov Bound
▶
8.1
Overview
8.2
Probabilistic bound on low-weight outputs
8.3
Union bound over bad matrices
8.4
Gilbert–Varshamov bound
9
List Decoding
▶
9.1
Overview
9.2
List-decodable codes
9.3
Counting lemmas
9.4
List-decoding capacity
10
Johnson Bound
▶
10.1
Overview
10.2
Basic definitions
10.3
Embedding and inner-product bounds
10.4
Rankin bound
10.5
Johnson bound
11
CSS Codes (Not Yet Formalized)
▶
11.1
Overview
11.2
Symplectic vector space
11.3
CSS construction
11.4
CSS code parameters
12
Quantum Hamming Bound
▶
12.1
Overview
12.2
Pauli strings
12.3
\(n\)-qubit Hilbert space
12.4
Knill–Laflamme conditions
12.5
Error sphere and sphere-packing
12.6
Quantum Hamming bound
13
Quantum Singleton Bound
▶
13.1
Overview
13.2
Symplectic vector space
13.3
Support, weight, and isotropic subspaces
13.4
Code parameters and erasure correctability
13.5
Key lemma: two disjoint correctable sets
13.6
Quantum Singleton bound
Dependency graph
TCSLib
1
Boolean Analysis — Core Definitions
1.1
Overview
1.2
The Boolean hypercube and functions
1.3
Uniform measure and expectation
1.4
Walsh–Fourier characters
1.5
Fourier coefficients
1.6
Walsh expansion
1.7
Orthonormality and Parseval’s identity
1.8
Coordinate influence
1.9
Noise operator
1.10
Notable Boolean functions
1.11
Sensitivity
1.12
Properties for Arrow’s theorem
2
Arrow’s Impossibility Theorem
2.1
Overview
2.2
Social choice definitions
2.3
Voter ordering model
2.4
Key correlation lemmas
2.5
Fourier formula for the cycle correlation
2.6
Acyclicity implies degree-1 structure
2.7
Degree-1 implies dictatorship
2.8
Arrow’s Impossibility Theorem
3
Error-Correcting Codes — Core Definitions
3.1
Overview
3.2
Basic objects: codewords and codes
3.3
Distance, weight, and rate
3.4
Basic lemma: distance vs. block length
4
Singleton Bound
4.1
Overview
4.2
Main result
5
Hamming Bound
5.1
Overview
5.2
Volume formula
5.3
Disjointness of decoding balls
5.4
Hamming bound
6
Entropy and Asymptotic Bounds
6.1
Overview
6.2
Asymptotic upper bound on ball size
6.3
Entropy algebra lemmas
6.4
Analytic helpers
6.5
Stirling-based binomial lower bound
6.6
Positivity of \(q\)-ary entropy
7
Linear Codes and the Uniformity Lemma
7.1
Overview
7.2
Distance equals minimum weight in linear codes
7.3
Uniform distributions and random matrices
7.4
Uniformity lemma
8
Gilbert–Varshamov Bound
8.1
Overview
8.2
Probabilistic bound on low-weight outputs
8.3
Union bound over bad matrices
8.4
Gilbert–Varshamov bound
9
List Decoding
9.1
Overview
9.2
List-decodable codes
9.3
Counting lemmas
9.4
List-decoding capacity
10
Johnson Bound
10.1
Overview
10.2
Basic definitions
10.3
Embedding and inner-product bounds
10.4
Rankin bound
10.5
Johnson bound
11
CSS Codes (Not Yet Formalized)
11.1
Overview
11.2
Symplectic vector space
11.3
CSS construction
11.4
CSS code parameters
12
Quantum Hamming Bound
12.1
Overview
12.2
Pauli strings
12.3
\(n\)-qubit Hilbert space
12.4
Knill–Laflamme conditions
12.5
Error sphere and sphere-packing
12.6
Quantum Hamming bound
13
Quantum Singleton Bound
13.1
Overview
13.2
Symplectic vector space
13.3
Support, weight, and isotropic subspaces
13.4
Code parameters and erasure correctability
13.5
Key lemma: two disjoint correctable sets
13.6
Quantum Singleton bound