Theory Reading Group

A classic is something that
everybody wants to have read
and nobody wants to read.
Mark Twain

Time and place (Fall 2013): 2pm on Fridays at the seminar room.

There are many beautiful papers which we never get around to reading: always there is something more relevant and recent that demands our attention here and now. And often we don't even know which papers are the classics outside of our narrow fields (especially when we are just starting our research carreer). This reading group is intended to give us an excuse to do both: read and present classic (even though not necessarily very recent) papers in our field and listen to presentations of what our friends and collegues consider classics. If you would like to be added to the seminar mailing list, please send an email to Antonina Kolokolova (kol) , as usual at

Some Recommendations for topics

Future talks

Date Speaker Topic
8/11/2013 Renesa Nizamee TBA

Past talks

Date Speaker Topic
1/11/2013 Brad Sheppard String reconstruction using k-spectrum
18/10/2013 Miklos Bartha Graph reconstruction conjecture
11/10/2013 Antonina Kolokolova Natural proofs

Previous years

In Fall 2011 Robert Robere is doing a series of talks on space-bounded computation (see here for the webpage with notes and dates). It is a great chance to learn about a major part of complexity theory in much more detail than just from a single talk. It starts slow, but gets exciting right away. Everybody is welcome!
Date Speaker Topic
15/3/2011 Antonina Kolokolova "Compression without a common prior: an information-theoretic justification for ambiguity in language".
14/2/2011 Renesa Nizamee The Knapsack Problem
8/2/2011 Todd Wareham A Change for the Better?: Assessing the Computational Cost of Re-representation
1/2/2011 Robert Robere Natural Proofs
25/1/2011 Antonina Kolokolova Ryan Williams' Non-Uniform ACC Circuit Lower Bounds
2/11/2010 Robert Robere Bounded width branching programs.
6/4/2010 Seven Normore Kolmogorov complexity.
30/3/2010 Renesa Nizamee Superconcentrators.
09/3/2010 Grant Strong Survey propagation-based SAT solver on a GPU.
16/2/2010 Miklos Bartha Turing automata and graph machines.
26/1/2010 Todd Wareham The Complexity of Finding Locally Optimal Solutions
12/1/2010 Steven Normore Immerman-Szelecsenyi theorem
17/11/2009 Caoan Wang On Hamiltonian Paths In Tetrahedralizations Of Convex Polyhedra.
03/11/2009 Manrique Mata-Montero Hennie's One-tape online turing machine computations and Hartmanis and Lewis's hierarchies of memory limited computations
27/10/2009 Scott McCarthy Schaefer's dichotomy theorem
29/09/2009 Antonina Kolokolova A gentle introduction to Probabilistically Checkable Proofs