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 daytoday messages about the course
and problem set submissions are dealt with there.
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.
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 1517 (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
AroraBarak 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 
1012 
Aud 01 
1. 
Intro to complexity theory, course overview, Turing machines, undecidability 
Chs 01, notes 
Thursday 
Feb 8 
1012 
Aud 01 
2. 
Complexity classes, reductions, P, NP, nondeterministic computation 
Chs 12, notes 
Thursday 
Feb 8 
1315 
Aud 01 
3. 
NPcompleteness, CookLevin theorem 
Ch 2, notes 
Tuesday 
Feb 13 
1012 
Aud 01 
4. 
NPreductions, coNP, decision vs. search 
Ch 2, notes 
Thursday 
Feb 15 
1012 
Aud 01 
5. 
EXP vs. NEXP, diagonalization, time hierarchy theorems, Ladner's theorem 
Chs 23, notes 
Thursday 
Feb 15 
1315 
Aud 01 
6. 
Oracle Turing machines, limits of diagonalization 
Ch 3, notes 
Tuesday 
Feb 20 
1012 
Aud 01 
7. 
Space complexity, PSPACE, NPSPACE, PSPACEcompleteness 
Ch4, notes 
Thursday 
Feb 22 
1315 
Aud 01 
8. 
Savitch's theorem, L, NL 
Ch 4, notes 
Tuesday 
Feb 27 
1012 
Aud 01 
9. 
ImmermanSzelepcsényi theorem 
Chs 45, notes 
Thursday 
Feb 29 
1012 
Aud 01 
10. 
Polynomial hierarchy (PH) 
Ch 5, notes 
Thursday 
Feb 29 
1315 
Aud 01 
11. 
Boolean circuits, P/poly, KarpLipton theorems 
Ch 6, notes 
Tuesday 
Mar 5 
1012 
Aud 01 
12. 
Randomized computation, BPP, polynomial identity testing (PIT), RP, coRP, ZPP 
Ch 7, notes 
Thursday 
Mar 7 
1315 
Aud 01 
13. 
Error reduction and applications 
Ch 7, notes 
Tuesday 
Mar 12 
1012 
Aud 01 
14. 
Interactive proofs, IP, IP=PSPACE (but proof of coNP ⊆ IP) 
Ch 8, notes 
Thursday 
Mar 14 
1012 
Aud 01 
15. 
coNP ⊆ IP (cont.), zeroknowledge (ZK) proofs 
Chs 89, notes 
Thursday 
Mar 14 
1315 
Aud 01 
16. 
Boundeddepth circuits, PARITY∉AC^{0}, Håstad's switching lemma 
Ch 14, notes 
Tuesday 
Mar 19 
1012 
Aud 01 
17. 
Håstad's switching lemma (cont.) 
Ch 14, notes 
Thursday 
Mar 21 
1012 
Aud 01 
18. 
Boundeddepth circuits with MODgates, PARITY∉ACC^{0}(3), method of approximations 
Ch 14, notes 
Thursday 
Mar 21 
1315 
Aud 01 
19. 
PARITY∉ACC^{0}(3), method of approximations (cont.) 
Ch 14, notes 
Tuesday 
Apr 2 
1012 
Aud 01 
20. 
Introduction to learning theory 
notes 
Thursday 
Apr 4 
1012 
Aud 01 
21. 
Sample complexity of learning, probably approximately correct (PAC) model 
notes 
Thursday 
Apr 4 
1315 
Aud 01 
22. 
VapnikChervonenkis (VC) dimension; concluding remarks 
notes 
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 coinstructor, helping out with grading of problem sets,
providing feedback, and answering questions at the exercise sessions.
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.

Please submit your solutions
via Absalon
as a PDF file.
State your name and email address
close to the top of the first page.
Solutions should be written in LaTeX or some other mathaware
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.

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.

The intention from the instructor side is to grade and return
submissions after a week.

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

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.

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.

In order to pass the course, you need a passing grade (at least E=02) on all problem sets.

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.

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.
