January-March, 2000

Instructor: Olle Häggström, phone 031-772 5311, email

Schedule: The first lecture takes place on Monday, January 17, at 10:00 in room MD9. After that, lectures will take place every Friday, at 15:15 in room MD6, starting January 21 and ending March 3.

NOTE: The lecture on Feb 18 has been moved to Monday, Feb 21, at 10:00 in room S1.

Language: English.

Examination: The course gives 3 credit units. For this, the following is required:

Course content: The course is being developed in ``real time'', and for this reason I cannot accurately summarize its contents before it is over. Here is what I wrote prior to the course:
``Loosely described, the time (resp. space) complexity of an algorithm is the time (resp. amount of memory) needed to run the algorithm for a given input. The (time or space) complexity of a given problem is the minimum complexity over all algorithms that solve the problem (if such algorithms exist at all!). One aim of the course is to give graduate students in mathematics or mathematical statistics, that have little or no background in computer science, an introduction to this kind of complexity, with the hope that they will then want to apply their new knowledge in the somewhat more down-to-earth course on Randomized algorithms (in Swedish). A second aim of the course is to provide an introduction to the concept of Kolmogorov complexity. The Kolomogorov complexity of a function (or number, string, etc) is (again loosely speaking) the length of the shortest program which computes it. This is a fascinating concept, which ties up theoretical computer science with probability, statistics and inforamtion theory.''
Contents of lectures will gradually be posted in the following table.

Day Main content of lecture Recommended reading
Monday, Jan 17 Recursive functions. Models of computing. Turing machines. Universal Turing machines. The halting problem.Chapter 2 in Johan Håstad's notes ``Complexity Theory'', which was handed out at the lecture (also available, with a few of the illustrations missing, at Håstad's homepage).
Friday, Jan 21Time and space complexity of algorithms. Complexity classes such as P, NP and PSPACE. NP-completeness.Version light: The paper ``Complexity theory: basics and some recent progress'' by Håstad, handed out at the lecture (MR 96f:68040).
Version heavy: Chapters 4-7 in Håstad's notes ``Complexity Theory'' (see previous lecture).
Friday, Jan 28Models of probabilistic computing. BPP and other probabilistic complexity classes. Chapter 9 in Håstad: ``Complexity Theory'' (see Jan 17).
Friday, Feb 4Lecture by Devdatt Dubhashi on the problem of whether or not BPP=P. The papers ``Recent advances towards proving P=BPP'' by Clementi, Romlin and Trevisan (MR 99b:68081, postscript file), and ``Simplified derandomization of BPP using a hitting set generator'' by Goldreich, Vadhan and Wigderson (postscript file), handed out at the lecture.
Friday, Feb 11 Kolmogorov complexity. Chapter 7 in ``Elements of Information Theory'' by Cover and Thomas (MR 92g:94001). Copies of the first few sections of the chapter were handed out at the lecture.
Monday, Feb 21What is a random sequence? von Mises-Church randomness, Martin-Löf randomness, and Kolmogorov randomness.The paper ``Algorithms and randomness'' by Kolmogorov and Uspenskii (MR 89d:68035), which was handed out on Feb 11.
Friday, Feb 25The complexity-theoretic approach to pseudo-random number generators. Chapter 10 in Håstad: ``Complexity Theory'' (see Jan 17), and/or the paper ``Pseudorandomness'' by Goldreich (MR), handed out at the lecture.
Friday, March 3More about Martin-Löf and von Mises-Church randomness.The forthcoming paper ``Are these sequences really random? (don't blink)'' by Benjamini, Häggström, Peres and Steif. This paper is not yet ready for circulation, but will hopefully be posted on my homepage within a couple of months.

Homework: Most weeks a piece of homework will be posted here, which you should finish and return within a deadline about a week later. Some general remarks concerning the homework:
1. You are (of course!) allowed to talk to each other, but not to mindlessly copy each other's solutions (everyone should understand, and be ready to defend, his or her solutions).
2. You can also come and talk to me, in case the problems stubbornly resist your attempts at solving them.
3. Some homework problems take the form of a yes/no question. A simple ``yes'' or ``no'' answer does not suffice as a solution. You must show me that you have understood the problem and its solution!
4. Solutions should be handed to me directly, or to my mailbox, no later than the day given by the deadline. Electronic submissions of solutions are not accepted.

Homework (in postscript) PostedDeadline Comments and partial solutions
Homework 1 Monday, Jan 17Wednesday, Jan 26 Comments 1
Homework 2 Monday, Jan 24Wednesday, Feb 2 Comments 2
Homework 3 Tuesday, Feb 1Wednesday, Feb 23Comments 3
Homework 4 (the last one!) Monday, Feb 21Wednesday, March 8Comments 4

Literature consists of various handouts.

Email list: I have an email list for distribution of course information. Please contact me (OH) if you wish to receive course information and are not already on the email list.

Last modified: Wed Mar 15 16:11:55 MET 2000