Time-Space Tradeoffs for SAT - Graduate Complexity Lecture at CMU

Time-Space Tradeoffs for SAT - Graduate Complexity Lecture at CMU

Explore time/space tradeoffs for SAT in this graduate-level lecture on Computational Complexity Theory. Delve into key results, technical remarks, proofs, and essential ingredients of the topic. Examine concepts such as padding, complementary speedup, and alternation elimination. Learn from Carnegie Mellon University professor Ryan O'Donnell as he covers material from Arora-Barak Chapter 5.4 in this comprehensive 92-minute session, part of CMU's Fall 2017 Course 15-855.