Jakob Nordström / Teaching / Computability and Complexity (CoCo) 2024

Computability and Complexity (CoCo) 2024

This webpage provides all documentation and information about the course. There is no additional information in the Absalon system, but day-to-day messages about the course and problem set submissions are dealt with there.

Short Overview of Course

Computers 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 Contents

This course is given in the first half of the spring semester (block 3) of 2024. It has a total of 22 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 01 in the August Krogh Building at Universitetsparken 13. In addition to the lectures, there are exercise classes all Thursdays 15-17 (except week 13) in 2.0.G.064/070 in the Niels Bohr Building at Jagtvej 155.

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.

 Weekday Date Time Room #  Plan of lectures References
 Tuesday Feb 6 10-12 Aud 01 1. Intro to complexity theory, course overview, Turing machines, undecidability Chs 0-1, notes
 Thursday Feb 8 10-12 Aud 01 2. Complexity classes, reductions, P, NP, nondeterministic computation Chs 1-2, notes
 Thursday Feb 8 13-15 Aud 01 3. NP-completeness, Cook-Levin theorem Ch 2, notes
 Tuesday Feb 13 10-12 Aud 01 4. NP-reductions, coNP, decision vs. search Ch 2, notes
 Thursday Feb 15 10-12 Aud 01 5. EXP vs. NEXP, diagonalization, time hierarchy theorems, Ladner's theorem Chs 2-3, notes
 Thursday Feb 15 13-15 Aud 01 6. Oracle Turing machines, limits of diagonalization Ch 3, notes
 Tuesday Feb 20 10-12 Aud 01 7. Space complexity, PSPACE, NPSPACE, PSPACE-completeness Ch4, notes
 Thursday Feb 22 13-15 Aud 01 8. Savitch's theorem, L, NL Ch 4, notes
 Tuesday Feb 27 10-12 Aud 01 9. Immerman-Szelepcsényi theorem Chs 4-5, notes
 Thursday Feb 29 10-12 Aud 01 10. Polynomial hierarchy (PH) Ch 5, notes
 Thursday Feb 29 13-15 Aud 01 11. Boolean circuits, P/poly, Karp-Lipton theorems Ch 6, notes
 Tuesday Mar 5 10-12 Aud 01 12. Randomized computation, BPP, polynomial identity testing (PIT), RP, coRP, ZPP Ch 7, notes
 Thursday Mar 7 13-15 Aud 01 13. Error reduction and applications Ch 7, notes
 Tuesday Mar 12 10-12 Aud 01 14. Interactive proofs, IP, IP=PSPACE (but proof of coNP ⊆ IP) Ch 8, notes
 Thursday Mar 14 10-12 Aud 01 15. coNP ⊆ IP (cont.), zero-knowledge (ZK) proofs Chs 8-9, notes
 Thursday Mar 14 13-15 Aud 01 16. Bounded-depth circuits, PARITY∉AC0, Håstad's switching lemma Ch 14, notes
 Tuesday Mar 19 10-12 Aud 01 17. Håstad's switching lemma (cont.) Ch 14, notes
 Thursday Mar 21 10-12 Aud 01 18. Bounded-depth circuits with MOD-gates, PARITY∉ACC0(3), method of approximations Ch 14, notes
 Thursday Mar 21 13-15 Aud 01 19. PARITY∉ACC0(3), method of approximations (cont.) Ch 14, notes
 Tuesday Apr 2 10-12 Aud 01 20. Introduction to learning theory notes
 Thursday Apr 4 10-12 Aud 01 21. Sample complexity of learning, probably approximately correct (PAC) model notes
 Thursday Apr 4 13-15 Aud 01 22. Vapnik-Chervonenkis (VC) dimension; concluding remarks notes

Instructors

The main instructor on the course is Jakob Nordström, who will be giving the lectures together with Srikanth Srinivasan and Amir Yehudayoff.

Shuo Pang will be co-instructor, helping out with grading of problem sets, providing feedback, and answering questions at the exercise sessions.

Course Material

Textbook

We will mostly be following the book

except for towards the end of the course.

Problem Sets

The 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.

  • Problem set 1 (last updated February 10, 2024): Deadline Thursday February 29.
  • Problem set 2 (last updated March 11, 2024): Deadline Friday March 15.
  • Problem set 3 (last updated April 4, 2024): Deadline Sunday April 7.
  • Problem set 4 (last updated April 3, 2024): Deadline Friday April 12.

Problem Set Instructions

The following instructions apply for all problem sets.

  1. Please submit your solutions via Absalon as a PDF file. State your name and e-mail address close to the top of the first page. Solutions should be written in LaTeX or some other math-aware typesetting system with reasonable margins on all sides (at least 2.5 cm). Please try to be precise and to the point in your solutions and refrain from vague statements. Never just state an an answer, but make sure to also explain your reasoning. Write so that a fellow student of yours can read, understand, and verify your solutions.
  2. Submissions must be done on time. Blank submissions are not acceptable and imply an automatic failure on the course. Note, however, that the submission deadline only specifies the date, and not the time zone. You are free to submit according to whatever time zone on earth you like, as long as the date in that time zone is correct.
  3. The intention from the instructor side is to grade and return submissions after a week.
  4. The thresholds for grading are stated on the first page of the problem set, and any adjustment of these thresholds will be communicated on Absalon. (The thresholds can only be adjusted downwards and never upwards.)
  5. Students who get a grade D=4 or lower on a problem set can make a resubmission in order to try to improve the grade, or to reach a passing grade. Note that you can only resubmit solutions to problems on the problem set that you actually worked on before. That is, a resubmission can revise and correct a previously submitted solution for a problem, but cannot compensate for an initial blank submission for this problem.
  6. The resubmission deadline is one week after the students have received their graded problem sets back, unless communicated otherwise. Resubmissions can only get grades in the lower half of the grading scale, i.e., up to C=7.
  7. In order to pass the course, you need a passing grade (at least E=02) on all problem sets.
  8. In principle, the final grade will be the mean of the grades for all the problem sets. That is, think of A=12, B=10, C=7, D=4, and E=02 as {5,4,3,2,1}, sum up, and divide by the number of psets. If this mean is not integral, later psets will affect the rounding more than earlier psets.
  9. Although you are encouraged to discuss the problem sets with other students, you have to write your own solution from scratch, and understand all details of them fully. It is not allowed to compose draft solutions together and then continue editing individually, or to share any text, formulas, or pseudocode. Also, no such material may be downloaded from or generated via the internet to be used in draft or final solutions.

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.

Published by: Jakob Nordström <jn~at-sign~di~dot~ku~dot~dk>
Updated 2024-04-04