Nada

Teoretikerns verktygslåda, 4 poäng
period 3 04/05

News

The course is now over.

Lecturer

Johan Håstad, is responsible for all aspects of this course. The plan is to lecture in Swedish but given interest from several non-Swedish speakers this might change.

Handouts

Slides of lecture by Hans on deterministic primality testing.

Notes on Markov chains and approximation of the permanant taken by Gunnar after a lecture by Per.

Notes on twoprover games by Mårten. Also as pdf. A related paper on inapproximability written by Johan, pdf.

Notes on eigenvalues and expanders by Douglas. Also as pdf.

Notes on expanders in general by Per. Also as pdf.

Notes on uses of Fourier analysis by Jonas on his own lecture. Also as pdf.

Notes on property testing by Jakob after a lecture by Douglas. Also as pdf.

Fifth set of lecture notes by Gunnar on the marvel of polynomials. Also as pdf.

Fourth set of lecture notes by Mårten on construction of almost k-wise independent variables. Also as pdf.

Third set of lecture notes by Douglas on examples of the probabilistic method. Also as pdf.

Second set of lecture notes by Gustav on examples of probabilistic method. Also as pdf.

First set of lecture notes by Hans on clique and independent set.

Homework

This course will be graded by homeworks and possible by having student lecture on selected topics and/or taking notes.

Course material

Sanjeev Arora has agreed to let us borrow some material from his version of the course but for new topics and topics covered differently we will produce a set of lecture notes.

Lectures

Will be decided together with the topics.

Schedule

We decided on one lecture a week. We might expand this to two lectures once we leave period 3 and/or the student lectures start. Course logo
Sidansvarig: <johanh@nada.kth.se>
Senast ändrad 5 juli 2005
Tekniskt stöd: <webmaster@nada.kth.se>