Computability and Complexity (CoCo) 2026
This webpage provides all documentation and information about the Computability and Complexity (CoCo) course (except for some formalities covered on the official course webpage). There is no additional information on the Absalon pages except that day-to-day messages about the course as well as problem set submissions are dealt with there.
Short Overview of CourseComputers are everywhere today—at work, in our cars, in our living rooms, and in our pockets—and have changed the world beyond our wildest imagination. Yet these marvellous devices are, at the core, amazingly simple and stupid: all they can do is to mechanically shuffle zeros and ones around. What is the true potential of such automated computational devices? And what are the limits of what can be done by mechanical calculations? Computational complexity theory gives these deep and fascinating philosophical questions a crisp mathematical meaning. A computational problem is any task that is in principle amenable to being solved by a computer—i.e., it can be solved by mechanical application of mathematical steps. Complexity theory focuses on classifying computational problems according to their inherent difficulty, and on relating those classes of problems to each other. The goal is to understand the power of computers but also—and above all—the limitations of what problems can be solved by them, or more broadly by any type of automated computational process. A problem is regarded as inherently difficult if its solution requires unreasonably large resources regardless of which approach is used to solve it (i.e., no matter which algorithm is employed). Complexity theory formalizes this notion by introducing mathematical models of computation and quantifying the amount of resources needed to solve the problems, such as running time, memory usage, parallelism, communication, et cetera. This course will give an introduction to computational complexity theory, survey some of the major research results, and present some of the open problems that are the focus of current research. While the intention is to give a fairly broad coverage, there might be a slight bias towards areas where the Algorithms and Complexity Section at DIKU has made significant contributions to the state of the art.
Schedule and Course ContentsThis course is given in the first half of the spring semester (block 3) of 2026. It has a total of 21 lectures, with ca 2.5 lectures per week on average. In accordance with the academic quarter tradition, all times are stated cum tempore, so 10 am in the lecture schedule below actually means 10:15 am et cetera. The lectures will be in Auditorium 09 upstairs in the H.C. Ørsted building at Universitetsparken 5 In addition to the lectures, there are exercise classes all Thursdays 15-17 (except week 13) also in Auditorium 09 at HCØ. Chapter numbers in the course planning below refer to the Arora-Barak textbook. The general idea behind the course is to go over (most of) the first 9 chapters in the textbook, getting a fairly good general overview of computational complexity theory, and then spend roughly the last third of the course on a selection of more "advanced" topics, where the textbook is followed less closely. Please note that the information below about what will be covered in future lectures is a bit tentative, since the planning might be slightly revised as we go along. In particular, we have not yet decided on this year's selection of advanced topics towards the end of the course (but will make sure to cover some exciting material).
InstructorsThe main instructor on the course is Jakob Nordström, who will be giving the lectures together with Amir Yehudayoff. Lianna Hambardzumyan and (later in the course) Varun Ramanathan will be co-instructors, helping out with grading of problem sets, providing feedback, answering questions at the exercise sessions, and potentially giving some of the later lectures.
Course MaterialTextbookWe will mostly be following the book
Problem SetsThe course examination will be by a total of 4 problem sets. You have to pass all problem sets to pass the course. Problem sets will be posted on Absalon and below as the course proceeds, at least one week before the submission deadline. Links to the problem sets will appear as they are being posted. Please note that the dates given below for future problem sets are still somewhat tentative. The actual deadlines are somewhat configurable, and can be discussed in class. The important thing is that we all agree on the deadlines beforehand, and that once they are set we stick to them without exceptions.
Problem Set InstructionsThe following instructions apply for all problem sets.
Note that, as stated above, solutions to the problem sets should be handed in strictly by the deadlines. Being able to work towards a deadline and deliver the best possible result within a given time frame (rather than a 100% polished product that arrives too late) is an important skill, and is something that you will have the opportunity to practise during the course. Having said that, exceptional circumstances, such as severe illness, can be accepted as an excuse for late problem set solutions. It should be emphasized, however, that lack of time due to work outside the university or due to many parallel courses is not considered as a legitimate reason for handing in problem set solutions late. If you feel that you have a good reason to hand in your solutions late, make sure to contact the main instructor as soon as possible. |