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 fundamental 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 1127; note though that (as with all Spring 2022 courses) the first two weeks of class will be online-only (you can access the lectures through the Zoom link on the Courseworks page). Note also that throughout the semester lectures will be recorded and recordings will be made available to all enrolled students through Courseworks.
Time: Tu/Th 8:40am-9:55am Eastern Time
Course email (for administrative issues; use Ed Discussion for subject matter questions): coms4236columbias22 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.