Theory Student Seminar

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

Time for this term: starting February 2008, TSS will be on Thursdays, 5pm at the Theory Lab (SF4302).

Effective this term the graphgoup has been merged with tss.

The Theory Student Seminar (TSS) has been running in our department on and off for many years. Currently we meet once a week, Thursday 5-6pm in the Theory Lab. The main purpose of TSS is to save theory grad students time and effort in reading "classic" papers: instead of reading them all on our own, we take turns presenting them to the rest of the group. Another source of topics for us is Schoning and Prium's book "Gems of theoretical computer science". Some of the most successful presentations were tutorials on related topics, from model theory to Chernoff bounds. TSS is also an appropriate place for practice talks or presentations of the current research. Though TSS is mainly for graduate students in complexity theory, interested postdocs, students from other areas, and even undergraduates are also welcome. If you would like to be added to the seminar mailing list, please send an email to tss-request @ cs.toronto.edu

Possible topics

Future talks

Date Topic Presented by
10/09/2008 TBA Yevgeniy Vahlis
17/09/2008 TBA Akitoshi Kawamura

Recent topics

Date Topic Presented by
19/06/2008 Near Optimal Dimensionality Reductions that Preserve Volumes Anastasios Zouzias
01/05/2008 Bounded Timestamping Systems Marek Janicki
24/04/2008 The complexity of simulating Brownian Motion Mark Braverman
10/04/2008 PQ-trees and applications Steve Chaplick
03/04/2008 Superpolynomial monotone circuits lower bounds for CLIQUE Periklis Papakonstantinou
27/03/2008 Randomized Matrix Computations Anastasios Zouzias
20/03/2008 Computability and Complexity of Real Functions Akitoshi Kawamura
13/03/2008 Discovering Community in Social Networks Alvin Chin
06/03/2008 Sparse graphs: metrics and random models Hamed Hatami
28/02/2008 Selected Results in Additive Combinatorics Siu Man Chan
14/02/2008 Lower Bounds for Selection in Randomly Ordered Streams Matei David
07/02/2008 Derandomizing shallow circuits Siavosh Benabbas
29/11/2007 Survey Propagation Eric Hsu
22/11/2007 On the non-existence of dimension reduction in \ell_2^2 Mohammad Moharrami
15/11/2007 Brower fixed point and Borsuk-Ulam theorem: combinatorial proofs Massimo Lauria
08/11/2007 Graph norms and Sidorenko's conjecture Hamed Hatami
01/11/2007 Edmonds' bipartite matching algorithm James Kwon
25/10/2007 On non-deterministic auxiliary pushdown automata Periklis Papakonstantinou
18/10/2007 Black box separation of public key encryption from one way functions   Yevgeniy Vahlis
11/10/2007 Introduction to expanders Mark Braverman
04/10/2007 Noisy Sorting Mark Braverman
12/04/2007 Affinity Propagation Delbert Dueck
29/03/2007 "Dinur's Combinatorial Proof of the PCP Theorem" II Siavosh Benabbas
22/03/2007 "Dinur's Combinatorial Proof of the PCP Theorem" I Siavosh Benabbas
01/03/2007 A new lower bound for the Lovasz-Schrijver SDP matrix-cut operator Costis Georgiou
15/02/2007 "The small world phenomen: An algorithm perspective" by Kleinberg Marek Janicki
08/02/2007 Kazhdan property and expanders Hamed Hatami
01/02/2007Cut-free tree-like and dag-like proof systems Phuong Nguyen
25/01/2007 KKL Theorem and the Discrete Fourier transform Ilya Sutskever
07/12/2006 Applications of limits of graph sequences II Siu Man Chan and Siu On Chan
30/11/2006 Applications of limits of graph sequences I Siu Man Chan and Siu On Chan
09/11/2006 Asymptotic behaviour of the Mafia game Mark Braverman
26/10/2006 Lower bounds on bounded timestamps Marek Janicki
19/10/2006 Sorting Signed Permutations Paul Medvedev
12/10/2006 Computing the number of spanning trees mod p Mark Braverman
05/10/2006 Lower bounds for the Lovasz-Schrijver hierachy - II Costis Georgiou
28/09/2006 Lower bounds for the Lovasz-Schrijver hierachy Costis Georgiou
21/09/2006 Pebbling Game is PSPACE complete Philipp Hertel
03/04/2006 Spectra of Graphs Periklis Papakonstantinou
28/03/2006 PSPACE-completeness Philipp Hertel
20/03/2006 Monadic Second-order Logic captures regular languages (over strings) Anthony Widjaja To
13/03/2006 Counting accepting paths in NL machines, and the Determinant problem Mark Braverman
07/03/2006 Introduction to Bounded Arithmetic Phuong Nguyen
20/02/2006 Comparing Encrypted Numbers Vladimir Kolesnikov
13/02/2006 Key Exchange Using Passwords and Long Keys Vladimir Kolesnikov
06/02/2006 "Hard-Core Distributions for Somewhat Hard Problems" by Russell Impagliazzo Mark Braverman
30/01/2006 Proof of Toda's Theorem - II Philipp Hertel
23/01/2006 Introduction to proof of Toda's Theorem Philipp Hertel
16/01/2006 Proving integrality gaps without knowing the linear program Periklis Papakonstantinou
28/11/2005 Introduction to discharging Marc Tedder
21/11/2005 Secure Function Evaluation Vladimir Kolesnikov
14/11/2005 Approximation results for the Minimum Vertex Cover problem Costis Georgiou
07/11/2005 Lower bounds for resolution proof system Philipp Hertel
31/10/2005 Prover/Delayer games for tree resolution Alex Hertel
17/10/2005 Introduction to VC theory Ilya Sutskever
03/10/2005 A tutorial on Fourier transforms and applications Periklis Papakonstantinou
26/09/2005 Introduction to probabilistic computation Mark Braverman
19/05/2005 A proof system for logical contingencies Alex Hertel, Philipp Hertel
03/05/2005 Pebble games Phuong Nguyen
19/04/2005 "Pseudorandom generators for space bounded computation" by N. Nisan Mark Braverman
12/04/2005 Expander graphs Paul McCabe
05/04/2005 Nonautomatizability of resolution Daniel Ivan
22/03/2005
29/03/2005 		Finite Metric Embeddings and Applications Periklis Papakonstantinou
08/03/2005 Program Checkability Paul McCabe
01/03/2005 IP = PSPACE Mark Braverman
22/02/2005 Switching lemma II: applications to lower bounds on AC0 Philipp Hertel
08/02/2005 Switching lemma I Philipp Hertel
01/02/2005 A generalization of the infinite Ramsey theorem Nazanin Mirmohammadi
09/12/2004 Razborov-Smolensky's lower bounds for AC0[2] Mark Braverman
02/12/2004 Product-Free Lambek Calculus Periklis Papakonstantinou
25/11/2004 Intro to Game Theory Periklis Papakonstantinou
18/11/2004 Strong Conditional Oblivious Transfer and Computing on Intervals. Vladimir Kolesnikov
11/11/2004 "Graph Ramsey Theory and the Polynomial Hierarchy", by Marcus Schaefer Phuong The Nguyen
28/10/2004
04/11/2004		 Communication Complexity Mark Braverman
21/10/2004 The Static Optimality Theorem Travis Gagie
14/10/2004 Kolmogorov Complexity Nazanin Mirmohammadi
07/10/2004 Size-Depth Trade-offs for Boolean Formulae, by Bonet and Buss Alan Skelley
30/09/2004 "A factor 2 approximation algorithm for the generalized Steiner network problem", by Kamal Jain Lap Chi Lau
23/09/2004 Complete characterizations and complexity results for greedy algorithms admitting optimal inputs. Periklis Papakonstantinou
09/09/2004 "Game Based Notions of Locality over Finite Models" Pablo Barcelo
24/06/2004 "Pseudorandom generators for space-bounded computation" by N. Nisan. Paul McCabe
17/06/2004 AKS sorting networks Shlomo Hoory
10/06/2004Approximate range searching in higher dimensions Avner Magen
3/06/2004 Monotone Circuits without the Monotony. Josh Buresh-Oppenheim
11/05/2004 Sorting Low-Entropy Sequences. Travis Gagie
04/05/2004 On The Computability of Julia Sets Mark Braverman
27/04/2004 "NP is as easy as detecting unique solutions." by Valiant and Vazirani Josh Buresh-Oppenheim
20/04/2004 "On truth-table reducibility to SAT" by Buss and Hay Tsuyoshi Morioka
29/03/2004 DNFs are not Properly PAC learnable Mark Braverman
23/03/2004 Fixed-point logics. Antonina Kolokolova
16/03/2004 Parameterized Complexity Phuong The Nguyen
09/03/2004 Two millionaires problem. Vladimir Kolesnikov
01/03/2004 Implicit proofs. Tsuyoshi Morioka
24/02/2004 Fun with Lempel-Ziv. Travis Gagie
10/02/2004 SAT(2) is LOGSPACE-complete. Mark Braverman
27/01/2004 Golomb Rulers Periklis Papakonstantinou
15/12/2003 Priority algorithms Periklis Papakonstantinou
08/12/2003
01/12/2003 		A brief history of permutation branching programs Alex Brodsky
17/11/2003 The Hypergraph Transversal Problem Philipp Hertel
10/11/2003 Real sets computability and complexity Mark Braverman
03/11/2003 Recognizing GHorn formulas is NL complete. Phuong The Nguyen
27/10/2003 More on Barnette's Conjecture and Computability and complexity of real numbers Mark Braverman
20/10/2003 Strengthening Barnette's Conjecture Alex Hertel
06/10/2003 "Relative to a Random Oracle A, P^A \not= NP^A \not= coNP^A with probability 1" by Bennett and Gill. Alan Skelley
29/09/2003 Complexity of deciding equivalence of regular expressions. Tsuyoshi Morioka
22/09/2003 ``Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size'', by R.Raz. Josh Buresh-Oppenheim
15/09/2003 Segerlind, Buss and Impagliazzo's switching lemma for k-DNF resolution. Daniel Ivan
07/08/2003 Schaefer's dichotomy theorem. Antonina Kolokolova
31/07/2003 Introduction to Posets. Richard Krueger
24/07/2003 "Lower Bounds on Nullstellensatz Proofs via Designs" by Sam Buss. Tsuyoshi Morioka
17/07/2003 "Communication Complexity: A new Approach to Circuit Depth", from Karchmer's PhD. Periklis Papakonstantinou
10/07/2003 Sequence Maxima Trees. Travis Gagie
26/06/2003 Real-time interval scheduling. Travis Gagie
05/06/2003
12/06/2003
19/06/2003		 Introduction to model theory. Neil Thapen
29/05/2003 Interval selection: Applications, algorithms, and lower bounds by T. Erlebach and F.C.R Spieksma. Stephanie Horn
15/05/2003 Primes is in P. Periklis Papakonstantinou
8/05/2003 Mutual exclusion for message passing models. Kleoni Ioannidou
1/05/2003 Formula isomorphism problem. Tsuyoshi Morioka
24/04/2003 Data compression: Burrows-Wheeler Transform Travis Gagie
10/04/2003 Intro to bounded arithmetic and RSUV isomorphism Alan Skelley
27/03/2003 "Symmetric Logspace is closed under complement" by Nisan and Ta-Shma. Antonina Kolokolova
20/03/2003 "Hard core distributions for somewhat hard problems" by R. Impagliazzo Mark Braverman
13/03/2003 Fussy closeness Vladimir Kolesnikov
6/03/2003 Chernoff bounds Mark Braverman
27/02/2003 "Two-tape simulation of multitape Turing machines" by F. C. Hennie & R.E. Stearns Phuong The Nguyen
12/02/2003 "Searching constant width mazes captures the AC0 hierarchy" by Barrington, Lu, Miltersen, Skyum Tsuyoshi Morioka
5/02/2003 "Natural proofs" by Razborov and Rudich Josh Buresh-Oppenheim
28/01/2003 Profit Cover and parameterized complexity Philipp Hertel
12/01/2003 "The Berman-Hartmanis conjecture" from Schoning's book Antonina Kolokolova
14/01/2003 Pursuit and evasion: Modeling a changing problem Kevin Brewer
3/12/2002
10/12/2002		 Secure Multiparty Computation Vladimir Kolesnikov
19/11/2002 A direct connection between PLS and G_1 Alan Skelley
12/11/2002 Bounded-depth Frege lower bounds for weaker pigeonhole principles Josh Buresh-Oppenheim
29/10/2002 Restructuring trees (by Evans and Kirkpatrick) Travis Gagie
29/10/2002 "The complexity of acyclic conjunctive queries" by Gottlob, Leone and Scarcello Antonina Kolokolova
17/10/2002 Approximability of local search Pixing Zhang
10/10/2002 P^{#P} \subseteq IP Steve Myers
3/10/2002 Different (and yet equivalent) ways to ask NP queries Tsuyoshi Morioka
24/09/2002 Transformations of Self-Stabilizing Algorithms Kleoni Ioannidou
10/09/2002 Randomness and Computation Valentine Kabanets