Undergrad Complexity at CMU - Lecture 1: Course Overview

Undergraduate Computational Complexity Theory
Lecture 1: Course overview and beginning the formal definition of computation

Carnegie Mellon Course 15-455, Spring 2017

Taught by Ryan O'Donnell

Suggested reading: Sipser, Chapter 0.2

[yousify]

Thank you Ryan, I am watching your lectures over and over in order to understand about some notions including to the textbook of Sipser, Papdimitriou and Goldreich.

[AkhyarKamili]

This is awesome! Never thought I'd find it on Youtube.

[sagarmalhotra]

Is it possible to somehow access the accompanying assignments ?

[jordankuzmanovik]

Link to panopto? Because i can't fint the lectures there

[Thien--Nguyen]

Can one encode (5, 2) in unary (with one string)?

[quTANum]

Great lecture, but the frame rate is killing me.

[misam]

Watch on at least 1.5 speed for the screens to line up.

[kxxwz]

It's so funny when one student guesses the answer is "P vs NP".