Theory of Computer Science

Code Bounds: A (Crude) Course

• Code Bounds 00: Overview
• Code Bounds 01: Background on Boolean Fourier Analysis
• Code Bounds 02: Delsarte's LP vs Theta' SDP - Part 1
• Code Bounds 02: Delsarte's LP vs Theta' SDP - Part 2
• Code Bounds 03: The original MRRW Proof of the First LP Bound
• Code Bounds 04: A Modern Fourier Analytic Proof of the First LP Bound
• Code Bounds 05: A Recent Interpretation of the First LP Bound
• Code Bounds 06: Perturbed Identity Matrices - Part 1
• Code Bounds 06: Perturbed Identity Matrices - Part 2
• Code Bounds 07: Sum-of-Squares Hierarchy for Independent Set - Part 1
• Code Bounds 07: Sum-of-Squares Hierarchy for Independent Set - Part 2
• Code Bounds 08: A New Complete LP Hierarchy for Linear Codes - Part 1
• Code Bounds 08: A New Complete LP Hierarchy for Linear Codes - Part 2

Topics

• High-dimensional Expanders (HDX)

• Coding Theory

• Sum-of-Squares (SOS)

• Probabilistically Checkable Proofs (PCPs)

External Speaker Series

• Swati Padmanabhan presented "A Faster Interior-Point Method for Semidefinite Programming" on 12/03 at 4:00pm
• Amey Bhangale presented "Rigid Matrices From Rectangular PCPs" on 12/07 at 4:00pm
• Kuikui Liu presented "High-dimensional Expanders in Discrete Sampling" on 12/10 at 4:00pm
• Nicolas Resch presented "LDPC Codes Achieve List Decoding Capacity" on 12/14 at noon (unusual time)
• Max Hopkins presented "High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games" on 01/14 at 4:15pm
• Tom Gur presented "On relaxed LDCs and their Applications" on 01/20 at 10:00am (unusual day and time)
• Ray Li presented "Improved List-Decodability of Reed--Solomon Codes via Tree Packings" on 01/28 at 4:15pm
• Ainesh Bakshi presented "Robustly Clustering Mixtures of Gaussians" on 02/01 at 4:00pm

Reading Group: Coding Theory

Coding Theory Brief Intro and Some Open Problems

Aaron Potechin exposition of "Expander Random Walks: A Fourier-Analytic Approach"
by Cohen, Peri and Ta-Shma

Reading Group: High-dimensional Expanders

High-Dimensional Expanders imply Agreement Expanders Part 1

High-Dimensional Expanders imply Agreement Expanders Part 2

Boolean Function Analysis on HDX

List Decoding Direct Product Codes with Double Samplers

Kaufman-Oppenheim's HDX Construction

Some Notes from the HDX-Codes Cluster

Oppenheim's Trickling-Down Theorem

Simplified Expansion Analysis of Kaufman-Oppenheim's HDX

Expander Graphs - Both Local and Global

Local Analysis of Higher-Order Random Walks and Applications

Some Open Problems