Mathematics of Computation Through the Lens of Linear Equations and Lattices

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.

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?