Главная
Study mode:
on
1
Intro
2
DEF: Linear equations (LE)
3
DEF: Error correcting codes (ECC)
4
ECC via balls
5
Closest Vector Problem (CVP)
6
DEF: LE non-perfect solution
7
DEF: LE, approximate solution
8
DEF: Unique-Games
9
DEF: Lattice-Discrete Subgroup
10
Lattice-CVP
11
The World According to Lattices
12
The Importance of being Infeasible
13
Worst-case vs. Average-case
14
Minkowski & in Reverse
15
Reverse Minkowski
16
Open Qi Relating to Classical Problems
17
Open Q: Hardness of Approximating SVP/CVP
18
The Future of Computing?
Description:
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
Add to list