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:
| ``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.'' | |
| 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 21 | Time 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 28 | Models of probabilistic computing. BPP and other probabilistic complexity classes. | Chapter 9 in Håstad: ``Complexity Theory'' (see Jan 17). |
| Friday, Feb 4 | Lecture 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 21 | What 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 25 | The 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 3 | More 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) | Posted | Deadline | Comments and partial solutions |
| Homework 1 | Monday, Jan 17 | Wednesday, Jan 26 | Comments 1 |
| Homework 2 | Monday, Jan 24 | Wednesday, Feb 2 | Comments 2 |
| Homework 3 | Tuesday, Feb 1 | Wednesday, Feb 23 | Comments 3 |
| Homework 4 (the last one!) | Monday, Feb 21 | Wednesday, March 8 | Comments 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.