Wednesday, August 30, 2017

Day 5

Finished proof of Cook's theorem. Talked about potential NP-incomplete problems such as Graph Isomorphism, recently shown in quasipolynomial time by Laszlo Babai.

Monday, August 28, 2017

Friday, August 25, 2017

Day 3

Reducibility and NP-Completeness


Wednesday, August 23, 2017

Day 2

More introduction to computation, Turing Machines and time complexity. Defined P and briefly NP.

Papers mentioned:
Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem
Where he defines the Turing machine. Section 9 is worth reading where he basically defends his thesis that this model defines computability.
Juris Hartmanis and Richard Stearns, On the Computational Complexity of Algorithms
This paper started the field of computational complexity. It's major insight was to consider resources like time and memory as a function of the input size.
Jack Edmonds, Paths, Trees and Flowers
This paper gives a polynomial-time algorithm for graph matching and argues that polynomial-time is a reasonable stand in for efficient computation.
Alan Cobham, The Intrinsic Computational Difficulty of Functions
Cobham gave a similar argument for polynomial time.

Monday, August 21, 2017

Day 1

Guest lecture by Venkat.

Covered basics of Turing Machines, Complexity Classes and Polynomial Time.

Reminder that Assignment 0 is due Friday. Download and submit on T-Square.

Assignment 0

A short assignment is posted on T-Square and due on Friday.