Many computational problems (such as multiplying two numbers, or sorting a list of numbers) are known to be "easy" in the sense that we have efficient algorithms for them. Unfortunately, many other computational problems of great practical importance (such as factoring large numbers, or finding the shortest tour that passes through all the cities on a map) seem to be difficult, in the sense that no efficient algorithms are known. Are these problems really inherently difficult -- do no efficient algorithms exist? -- or do we just need to come up with cleverer algorithms that can solve these problems efficiently?
Questions
such as these lie at the heart of computational complexity, which
is the study of the inherent abilities and limitations of efficient
computation. Computational complexity is one of the most fundamental and important topics in computer science; indeed, the core question of computational
complexity theory ("does P equal NP?") is one
of the most famous and important open questions in all of computer
science and mathematics.
Instructor: Rocco Servedio
Instruction modality: On campus, in Mudd 524. Throughout the semester lectures will be recorded and recordings will be made available to all enrolled students through Courseworks. That said, you are strongly encouraged to come to class in person (there is a strong historical correlation between coming to class in person and doing well in the course).
Time: Mon/Wed 8:40am-9:55am Eastern Time
Course email (for administrative issues; use Ed Discussion for subject matter questions): coms4236columbiaS23 at gmail dot com
This is a preliminary list of core topics. Other topics may be covered depending on how the semester progresses. Most topics will take several lectures. For more information, click on the "Lectures" tab above.