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

Computability and Complexity (CoCo) 2023

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?

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 will probably 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 2023. It has a total of 20 lectures, with 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 schedule below actually means 10:15 am et cetera. Auditorium 06 is located Universitetsparken 5 (HCØ), and Auditorium A is at Universitetsparken 15B.

Chapter numbers in the course planning below refer to the Arora-Barak textbook. The general idea behind the course is to first 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 (especially since this is the first time this kind of modern complexity theory course is given at the University of Copenhagen).

 Weekday Date Time Room #  Plan of lectures References
 Tuesday Feb 7 10-12 Aud A 1. Intro to complexity theory, course overview, Turing machines, undecidability Chs 0-1, notes
 Thursday Feb 9 13-15 Aud 06 2. Complexity classes, reductions, P, NP, nondeterministic computation Chs 1-2, notes
 Tuesday Feb 14 10-12 Aud A 3. NP-completeness, Cook-Levin theorem, decision vs. search Ch 2, notes
 Thursday Feb 16 10-12 Aud A 4. NP-reductions, coNP, EXP, NEXP Ch 2, notes
 Thursday Feb 16 13-15 Aud 06 5. Diagonalization, time hierarchy theorems, Ladner's theorem Ch 3, notes
 Tuesday Feb 21 10-12 Aud A 6. Oracle TMs, limits of diagonalization, space complexity Chs 3-4, notes
 Thursday Feb 23 10-12 Aud A 7. PSPACE, NPSPACE, PSPACE-completeness Chs 3-4, notes
 Thursday Feb 23 13-15 Aud 06 8. Savitch's theorem, L, NL, Immerman-Szelepcsényi theorem Ch 4, notes
 Tuesday Feb 28 10-12 Aud A 9. Immerman-Szelepcsényi theorem (cont.) Chs 4-5, notes
 Thursday Mar 2 10-12 Aud A 10. Polynomial hierarchy (PH), Boolean circuits, P/poly Chs 5-6, notes
 Thursday Mar 2 13-15 Aud 06 11. Karp-Lipton theorem, Meyer's theorem, Shannon's lower bound Ch 6, notes
 Tuesday Mar 7 10-12 Aud A 12. NC, AC, parallel algorithms, P-completeness; randomized computation, BPP Chs 6-7, notes
 Thursday Mar 9 10-12 Aud A 13. Polynomial identity testing, RP, coRP, ZPP, randomized reductions Ch 7, notes
 Thursday Mar 9 13-15 Aud 06 14. Interactive proofs, IP, IP=PSPACE (but proof of coNP ⊆ IP) Ch 8, notes
 Tuesday Mar 14 10-12 Zoom 15. coNP ⊆ IP (cont.), MIP, PCP Chs 8-9, notes
 Thursday Mar 16 13-15 Zoom 16. Monotone circuits, clique lower bound Ch 14, notes
 Tuesday Mar 21 8-10 Zoom 17. Clique lower bound for monotone circuits (cont.) Ch 14, notes
 Thursday Mar 23 15-17 Zoom 18. Proof complexity, resolution, interpolation, clique-colouring lower bound [Pud97], scribe notes
 Tuesday Mar 28 8-10 Zoom 19. Clique-colouring lower bound for resolution (cont.) [Pud97], notes
 Thursday Mar 30 15-17 Zoom 20. Pigeonhole principle lower bound for resolution [Hak85], [Pud00], scribe notes, notes

Instructors

The main instructor on the course is Jakob Nordström, who is responsible for all aspects of the course.

Shuo Pang will be co-instructor, helping out with grading of problem sets, providing feedback and answering questions, and giving a few lectures.

Course Material

Textbook

We will mostly be following the book

except for towards the end of the course.

Research Articles

In a course like this, the intention is that some lectures will be partly based on research articles. In this installment of the course, we make use of the following articles:

The lectures will cover the material in the articles that we need, so students are not required to read these papers—the references are provided for completeness and for students interested in further reading. However, for students interested in learning more, it should be noted that many of the proofs given in class are actually not those found in the papers, and more recent survey papers of an area are likely to be better reads than the original research articles. Please do not hesitate to contact the instructor if you are interested in specific references for some specific area.

Problem Sets

There will be 4 problem sets on this course. It is compulsory to pass all problem sets to be able to take the exam. 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 on February 19, 2023): Deadline Tuesday February 21.
  • Problem set 2 (last updated on February 19, 2023): Deadline Tuesday March 7.
  • Problem set 3 (last updated on March 19, 2023): Deadline Tuesday March 28.
  • Problem set 4 (last updated on March 28, 2023): Deadline Monday April 3.

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. Make sure to 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 threshold for grading is stated on the first page of the problem set, and any adjustment of this threshold will be communicated on Absalon. (The threshold can only be adjusted downwards and never upwards.)
  5. Students who do not pass a problem set can make a resubmission. 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. This date will be communicated clearly for each pset.
  7. It is a requirement to pass all problem sets to be allowed to sit the exam. Students who fail a resubmission, or do a blank submission will need special permission from the main instructor on the course to be allowed to take the exam. Of course, there are all kinds of personal circumstances, and at the end of the day we want all of you to pass the course. But just bad planning will not be a sufficient condition to get a waiver. If you would need a time extension due to special circumstances, do make sure to contact the main instructor well in advance to check whether these circumstances are sufficient.
  8. No copying of text, code, or similar is allowed. Although you are encouraged to discuss with other students, you have to write your own solution from scratch, and understand all details of it fully.
Published by: Jakob Nordström <jn~at-sign~di~dot~ku~dot~dk>
Updated 2023-03-29