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

Offered By: Ryan O'Donnell via YouTube

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

理论计算机科学基础 | Introduction to Theoretical Computer Science
Peking University via edX 算法设计与分析(高级) | Advanced Design and Analysis of Algorithms
Peking University via edX The Introduction to Quantum Computing
Saint Petersburg State University via Coursera Computational Complexity Theory
Indian Institute of Technology Kanpur via Swayam Computational Complexity
IIT Hyderabad via Swayam