ESP Biography
JEFFREY WU, MIT junior studying math and computer science
Major: Mathematics College/Employer: MIT Year of Graduation: 2012 

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 ChurchTuring 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. BigO notation. P. The strong ChurchTuring thesis. Examples of problems in P.
5. Nondeterministic computation. NP. Examples of problems in NP. Discuss P's relationship with NP. Space analogue: PSPACE = NPSPACE.
6. NPCompleteness. CookLevin Theorem. TQBF and PSPACEcompleteness.
7. Cookreductions. More NPcomplete problems.
8. IP. Interactive protocols. Zeroknowledge. IP = PSPACE.
H1971: TEATEATEATEATEA in Splash! 2008 (Nov. 22  23, 2008)
Come learn about the awesomeness of Tea! It helps me survive and it can help you too! Try new kinds of tea, tea with milk, tea with boba, tea with scones, tea with sandwiches, tea with cake, tea with dim sum, tea with math... the possibilities are endless!
