Explore the mathematics of computation through the lens of linear equations and lattices in this 45-minute lecture by Muli Safra. Delve into topics such as error-correcting codes, the Closest Vector Problem, and unique games. Examine lattices as discrete subgroups and their role in computational problems. Investigate the relationship between worst-case and average-case scenarios, and learn about Minkowski's theorem and its reverse. Discover open questions related to classical problems and the hardness of approximating SVP/CVP. Gain insights into the potential future of computing while exploring the intricate connections between linear algebra, geometry, and computational complexity.
Mathematics of Computation Through the Lens of Linear Equations and Lattices
International Mathematical Union via YouTube
Overview
Syllabus
Intro
DEF: Linear equations (LE)
DEF: Error correcting codes (ECC)
ECC via balls
Closest Vector Problem (CVP)
DEF: LE non-perfect solution
DEF: LE, approximate solution
DEF: Unique-Games
DEF: Lattice-Discrete Subgroup
Lattice-CVP
The World According to Lattices
The Importance of being Infeasible
Worst-case vs. Average-case
Minkowski & in Reverse
Reverse Minkowski
Open Qi Relating to Classical Problems
Open Q: Hardness of Approximating SVP/CVP
The Future of Computing?
Taught by
International Mathematical Union
