YoVDO

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

Offered By: Ryan O'Donnell via YouTube

Tags

Computational Complexity Theory Courses Algorithm Analysis Courses

Course Description

Overview

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.

Syllabus

Introduction
Results
Technical Remarks
Proofs
Ingredients
Padding
Remarks
No Complimentary Speedup
Proof
Recap
Alternation Elimination
Alternation Trading


Taught by

Ryan O'Donnell

Related Courses

Algorithms, Part II
Princeton University via Coursera Intro to Algorithms
Udacity Analysis of Algorithms
Princeton University via Coursera 算法设计与分析 Design and Analysis of Algorithms
Peking University via Coursera Design and Analysis of Algorithms
Chennai Mathematical Institute via Swayam