Are we aging well?
Talkat 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing · 2021-02-11..05-13
summary
Field argues it's aging brilliantly but uneasy; core technical claim is that a noncommutative/quantum variant of polynomial identity testing (PIT) admits a deterministic polynomial-time algorithm for PIT using a matrix-group gradient‑descent procedure. That algorithm turns into concrete tools: polynomial‑time tests for nullcone membership, families of analytic inequalities, and improved algorithms in statistics and operator theory. The approach formalizes geodesic convex optimization* on symmetry groups and suggests algorithms can yield lower bounds via derandomization and reductions.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 0:56Context
- 3:49Questions
- 16:58Is it possible
- 19:02A recent breakthrough
- 19:59Low bounds through algorithms
- 23:57The pid problem
- 29:04Proof identities and inequalities
- 32:12Problems
- 36:28Algorithms
- 39:11Conclusion
- 42:11QA
- 45:52State of ignorance
- 47:01Question time
- 50:24Theory in the center
- 56:28Theory of computation
- 57:22Summary