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

Sidansvarig: <johanh@nada.kth.se>

Senast ändrad 5 juli 2005

Tekniskt stöd: <webmaster@nada.kth.se>