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 mun.ca.

Some Recommendations for topics

Any survey from the Computational Complexity Column
Any other result that you would consider a classic or even just interesting.
Short introduction to a subfield of Computer Science or Mathematics. Although, given the time constraint you might want to cherry pick neat results and techniques as opposed to a textbook exposition.
Schoning and Prium's book "Gems of theoretical computer science". (Although, it is a bit out of date.)

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