learn about computational complexity theory (P vs. NP etc.)

[Owain Evans]

Hi,

I'm a visiting PhD student, working on philosophy and cognitive science. I'm going to be learning some topics in computational complexity theory from the textbook by Barak and Arora (draft copy is free). In particular, randomized algorithms and BPP, interactive proofs, and average-case complexity. If anyone would like to join me, we can arrange a time to meet up, discuss the text and go through some of the problems in the book. I can start now or at the end of term.

How much background is needed? The topics are fairly accessible. Reading the first couple of chapters of the book should suffice as background. Also, if you are interested in other topics in computational complexity or in other areas of theoretical CS (programming language semantics, algorithms or Kolmogorov complexity), then maybe we can plan to cover some other topics also.

Owain Evans

ow...@mit.edu

http://www.mit.edu/~owain/

[Alex Flint]

I would love to do this! - I'm just not sure if I'll have time with
writing up my thesis at the moment. Let me know when you plan to meet
and I'll try to read along with the group.

[Ben Hoskin]

Keep me posted - would like to, time dependant.

[Owain Evans]

hey alex,

i'm planning to start this soon. a couple of people are interested, but i'd like to get more people involved (if possible). are there any CS grad mailing lists that you could forward this to?

(i'm planning to come to GWWC event, though i may be a bit late, and so i'll see you later).

best

owain

[Alex Flint]

Hey owain, good idea, I'll forward your original email around the
various lists that I have access to, with your email address at the
bottom. Will see you this evening - it's going to be a set of fairly
basic heuristics and biases experiments followed by discussion and
pizza. We'll be in the stapeldon room, and the porter should be able
to direct you if we're already gone in by the time that you arrive.

Alex