Theory of computing reading group

Theory of computing reading group: 2009-2010 season

Thursdays 12.00-1:00pm in the quantum meeting room - MVB 3.44 (a.k.a 304). To join the mailing list, write to Leon.
An iCal file with an up to date list of talks and times can be found here. You may find it easier to 'subscribe' to that URL rather than 'import' the file (terminology may be different in your calendar software) to make sure that the file gets updated automatically.
Topics beginning with "~" are tentative titles or general areas.

Upcoming Talks (closest first)

Date	Who	Topic (links to abstracts)
10 Jun	Toby Cubitt	A proof "from the book": Moser's constructive Lovasz Local Lemma (Part 2)

Possible topics (any suggestions welcome)
Below is a selection of recent or notable suggested topics for the group (the full list is here)

Fast Dimension Reduction
Faster Sorting in the RAM model (1,2)
Uniform Hashing in Constant Time and Optimal Space
Fast subset convolution
Core Sets as Grids
Sketching, Streaming and Sub-linear Space Algorithms (any that seem interesting)
Beyond Worst-Case Analysis

Past Talks (most recent first)

Date	Who	Topic (links to abstracts)
25 Mar	Raphaël Clifford	Amortised Communication Complexity
11 Mar	Ashley Montanaro	Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities
04 Mar	Benjamin Sach	Maintaining Order
11 Dec	Tom Hinton	FRACTRAN
4 Dec	Alex Popa	Colouring 3-Colourable Graphs Using SDP
18 Nov	Ashley Montanaro	Computational Complexity of Financial Derivatives
6 Nov	Tom Hinton	A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing
29 Oct	Markus Jalsenius	Counting and Sampling Graph Colourings
22 Oct	Leon Atkins	Speed Scaling with Sleep States
15 Oct	Alex Popa	Online Algorithms

Complexity courses Sudan (general), Trevisan (coding theory) and Vadhan (derandomization).

Complexity books Goldreich and Arora-Barak.