What Can and What Cannot Be Done by LP and SDP (An Incomplete Overview)

on YouTube ↗51m

" summary

Gives a calculation-free proof of MRRW by projecting Krawtchouk polynomials to a degree-k space, forming a tridiagonal (Jacobi) operator and bounding its Perron eigenvalue to obtain |C| ≤ f(0)/f_0; derives Levenshtein by changing the measure to absorb 1−x, and links both to the Cohn‑Elkies sphere‑packing framework. Exhibits a polynomial proof of kissing number 12 with exact rational coefficients that tolerates few controlled violations. Notes exact few‑distance code sizes (two‑distance: 1 + C(n,2)), universal optimality of E8/Leech, and that SDP on triples does not beat LP asymptotically.

AI-written summary · about

" chapters (6)

1. 0:00Introduction
2. 1:05LP and SDP overview
3. 13:35Delsarte’s linear bound
4. 27:13Kissing numbers
5. 37:25LP and SDP limits
6. 46:16Q&A

" related talks

• 01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a SurveyHuck Bennett · Quantum and Lattices Joint Reunion Workshop
• 37mPPP-completeness with connections to CryptographyAikaterini Sotiraki​​​​ · Lattices: Geometry, Algorithms and Hardness 2020
• 34mHigh-entropy dual functions and locally decodable codesFarrokh Labib, Jop Briet · ITCS 2021
• 01h 13mA Zero-Knowledge PCP TheoremNicholas Spooner · Proofs (Simons Institute)
• 01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional ExpandersMax Hopkins · Beyond the Boolean Cube 2023
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 06mAlgorithms for the k-List ProblemsElena Kirshanova · Lattices: Geometry, Algorithms and Hardness 2020
• 01h 03mComplexity of Lattice ProblemsNoah Stephens-Davidowitz · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020