Advanced Theoretical Computer Science

At the heart of theoretical computer science are questions of both philosophical and practical importance. What does it mean for a problem to be solvable by computer? What are the limits of computability? Which types of problems can be solved efficiently? What are our options in the face of intractability? This subject covers such questions in the content of a wide-ranging exploration of the nexus between logic, complexity and algorithms, and examines many important (and sometimes surprising) results about the nature of computing.

• 1Design, manipulate, and reason about Turing machines
• 2Account for the inherent complexity of many computational problems of practical importance
• 3Conduct formal reasoning about machines, circuits, problems and algorithms, including reduction-based proof
• 4Design approximation algorithms for intractable problems
• 5Apply complexity arguments to related fundamental computational problems, such as randomized computations, interactive proof systems and cryptographic pseudorandom generators