Explore the intricacies of lattice problems in this comprehensive lecture from the Lattices: Algorithms, Complexity, and Cryptography Boot Camp. Delve into the Shortest Vector Problem and its simple reduction, examining the hardness of approximation and dream results. Investigate the hardness of STP, the Canons embedding trick, and ideal solutions. Learn about sparse applications and open problems in the field. Analyze hardness approximation, looping questions, and upper bounds. Gain valuable insights into the complexity of lattice problems and their implications for cryptography and algorithms.
Overview
Syllabus
Introduction
Shortest Vector Problem
Simple Reduction
Hardness of approximation
Dream result
Hardness of STP
Canons embedding trick
Ideal solution
Sparse application
Open problems
Hardness approximation
Looping questions
Upper bounds
Open problem
Taught by
Simons Institute
Related Courses
-
Algorithms for Lattice Problems
-
Undergrad Complexity at CMU - Hardness within P
-
Inapproximability of Clustering in Lp Metrics
-
Hardness Magnification for All Sparse NP Languages
-
Lattice Problems and Their Complexity - Crypto 2023 Session 2
-
Parameterized Inapproximability of the Minimum Distance Problem over All Fields
