ESP Biography


Major: Mathematics

College/Employer: MIT

Year of Graduation: 2014

Picture of Travis Hance

Brief Biographical Sketch:

Not Available.

Past Classes

  (Clicking a class title will bring you to the course's section of the corresponding course catalog)

M4480: Introduction to Computability and Complexity Theory in HSSP Spring 2011 (Feb. 19, 2011)
A gentle introduction to the theory of computation. Nowadays, in the real world, we use computers to solve essentially all the problems we need to solve. But what are the limits of computation, if they exist? We will discuss this question in great detail, on the way discovering many wonderful concepts and a surprisingly elegant theory. Syllabus 1. Intro. What is complexity/computability theory and why do we care? Languages. The Turing Machine. The Church-Turing thesis. 2. Decidability. Examples of decidable problems. ATM and the diagonal argument 3. Reductions. Other undecidable problems. The Halting problem and the busy beaver function. 4. Big-O notation. P. The strong Church-Turing thesis. Examples of problems in P. 5. Non-deterministic computation. NP. Examples of problems in NP. Discuss P's relationship with NP. Space analogue: PSPACE = NPSPACE. 6. NP-Completeness. Cook-Levin Theorem. TQBF and PSPACE-completeness. 7. Cook-reductions. More NP-complete problems. 8. IP. Interactive protocols. Zero-knowledge. IP = PSPACE.