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 Jan. 2012, TSS will be on Thursdays, 4pm at the Theory Lab (SF4302).

The Theory Student Seminar (TSS) has been running in our department on and off for many years. Currently we meet once a week, Mondays 4-5pm in the Theory Lab. The main purpose of TSS is to save theory grad students time and effort in reading "classic" papers and letting other students know what you are working on or what you find interesting. 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 theory, interested postdocs, students from other areas, and even undergraduates are welcome. If you would like to be added to the seminar mailing list, please send an email to tss -dash- request -at- cs -dot- toronto -dot- edu

Some Recommendations for topics

Future talks

Date Topic Presented by
26/01/2011 TBA Anastasios Zouzias
02/02/2011 TBA Yuval Filmus
09/02/2011 TBA Yuval Filmus
16/02/2011 TBA Dai Le
23/02/2011 TBA Robert Robere
01/03/2011 TBA Kaveh Ghasemloo
08/03/2011 TBA TBA
15/03/2011 TBA TBA
22/03/2011 TBA TBA
29/03/2011 TBA Serge Gorbunov
05/04/2011 TBA Yu Wu
12/04/2011 TBA Justin Ward

Recent topics

Date Topic Presented by
19/01/2011 Cheeger’s Inequality and its higher order extension. Part II Yu Wu
05/12/2011 Cheeger’s Inequality and its higher order extension. Part I Yu Wu
28/11/2011 Lower Bounds for Bounded Timestamping Marek Janicki
21/11/2011 The search for local one-way functions Wesley George
16/11/2011 Von Neumann's minimax theorem and some applications Lila Fontes
07/11/2011 Pipage Rounding [Ageev-Sviridenko, '04] Justin Ward
24/10/2011 A Threshold For Clusters in Real-World Random Graphs Arron Norwell
17/10/2011 Some recent results on The Steiner Tree Problem II Siavosh Benabbas
03/10/2011 Some recent results on The Steiner Tree Problem I Siavosh Benabbas
26/09/2011 Approximate mechanism design without money Joel Oren
19/04/2011 A matrix hyperbolic cosine algorithm and applications Anastasios Zouzias
12/04/2011 Algebraic Topology and Distributed Computing: A Primer (Herlihy and Rajsbaum'95) Marek Janicki
05/04/2011 Kolmogorov complexity and games Lei Huang
22/03/2011 Quantum Proofs of Classic Results Per Austrin
15/03/2011 Current Barriers in Boolean Circuit Complexity Anil Ada
08/03/2011 Online Stochastic Matching Joel Oren
22/02/2011 Generalizations of Matroids for Approximation Algorithms Justin Ward
15/02/2011 Balanced graph partition problems (Andreev/Räcke) Arron Norwell
08/02/2011 Secure physical computation in person (Izmalkov/Micali/Lepinsky) Wesley George
01/02/2011 Probabilistic Automata (Group Exercise) Lila Fontes
25/01/2011 Introduction to Proof Complexity, Uniform and Nonuniform Kaveh Ghasemloo
18/01/2011 Approximation Algorithm for Balanced Separator [ARV'04] Eden Chlamtáč
11/01/2011 Exponential lower bounds for constant-depth proofs of the pigeonhole principle Yuval Filmus
16/12/2010 Probabilistic Reasoning in Bounded Arithmetic: A Pigeon's Perspective Dai Le
9/12/2010 Szemerédi's Theorem for length 3 progressions (Roth's Theorem) Anil Ada
2/12/2010 Dueling Algorithms Brendan Lucier
25/11/2010 Approximation Algorithm for Balanced Separator and Its Applications [ARV'04] Yu Wu
18/11/2010 The PCP Theorem Anastasios Zouzias
11/11/2010 Strategy Iteration is strongly polynomial for two player games with constant discount (Zwick, Miltersen, and Hansen) Lei Huang
4/11/2010 Maximizing non-monotone submodular functions (Feige, Mirrokni, and Vondrak'07) Justin Ward
28/10/2010 Constructing pseudorandom generators from one-way functions Wesley George
21/10/2010 Faster Hamiltonicity Testing Per Austrin
14/10/2010 Unprovability of Lower Bounds on the Circuit Size for SAT in S^2_2(\alpha) Kaveh Ghasemloo
7/10/2010 The Power of Graph Searching Steve Chaplick
30/09/2010 Privacy and Communication Complexity Lila Fontes
23/09/2010 A "simple" proof of Alon-Roichman's Theorem Anastasios Zouzias
16/09/2010 Using Polynomials to Prove PARITY not in AC^0 Yuval Filmus
14/04/2010 "Maximizing The Spread of Influence Through a Social Network" by Kempe, Kleinberg, and Tardos Joel Oren
07/04/2010 "Local Search Heuristics for k-Median and Facility Location Problems" by Arya et. al Justin Ward
31/03/2010 "On basing one-way functions on NP-Hardness" by Akavia, Goldreich, Goldwasser and Moshkovitz Wesley George
24/03/2010 Bayesian Algorithmic Mechanism Design Brenden Lucier
17/03/2010 Computational Game Theory Lila Fontes
10/03/2010 Matrix-Valued Chernoff bounds and applications Anastasios Zouzias
03/03/2010 Complexity Theory for Operators in Analysis Akitoshi Kawamura
24/02/2010 An asymptotically tight bound on the adaptable chromatic number Giovanna Thron
10/02/2010 Computability and Complexity over Real Numbers and Uncountable Structures Kaveh Ghasemloo
03/02/2010 Connections between Complexity, SAT-solvers and Cryptography Periklis Papakonstantinou
27/01/2010 Depth and rank considerations in the Polynomial Identity Testing problem Bruno Grenet
20/01/2010 Two proofs of the Centeral Limit Theorem Yuval Filmus
13/01/2010 The Isolation Lemma Dai Le
09/12/2009 The Myth of the Folk Theorem Brendan Lucier
02/12/2009 Lipschitz ODEs are PSPACE-complete Akitoshi Kawamura
25/11/2009 Modern Factorization Methods Yuval Filmus
18/11/2009 Clique Trees and Chordal Families of Graphs Steve Chaplick
11/11/2009 An Introduction to Kolmogorov Complexity Lila Fontes
04/11/2009 "A Constructive Proof of the Lovasz Local Lemma", by Robin Moser Justin Ward
28/10/2009 AM[k] is in AM[2] Marek Janicki
21/10/2009 Recent efforts in cryptography to model and deal with physical side-channel attacks Yevgeniy Vahlis
14/10/2009 Ultraproducts and approximation of circuit bounds Kaveh Ghasemloo
07/10/2009 "Private Coins versus Public Coins in Interactive Proof Systems", by Goldwasser and Sipser '86 Wesley George
30/09/2009 The Goldreich-Levin Theorem Periklis Papakonstantinou
23/09/2009 Introduction to game theory and how to play large games using simple strategies Anastasios Zouzias
16/09/2009 Seven trees in one Yuval Filmus
17/08/2009 On the Structure of the Optimal Greedy Computation Periklis Papakonstantinou
21/05/2009 Disproving Borsuk's Conjecture (Kahn-Kalai '93) Siavosh Benabbas
23/04/2009 Formal Theories for Logspace Counting Lila Fontes
16/04/2009 Cryptography in NC^0 [AIK04] Periklis Papakonstantinou
09/04/2009 Time-Space Lower Bounds and Diagonalization Kaveh Ghasemloo
02/04/2009 Uncertainty Principles, Extractors and Explicit embeddings of \ell_2 into \ell_1 Anastasios Zouzias
26/03/2009 Distance Trisectors and Zone Diagrams Akitoshi Kawamura
19/03/2009 Tango trees and the dynamic optimality problem Brendan Lucier
12/03/2009 How NOT to solve Vertex Cover using Semidefinite Programming Costis Georgiou
05/03/2009 Collaborative Filtering Marek Janicki
26/02/2009 Levels of detail in terrains Giovanna Thron
19/02/2009 A Black Box Separation of One-Wayness From Correlated One-Wayness in Trapdoor Permutations Yevgeniy Vahlis
12/02/2009 A little bit of Coding Theory (LP bounds on the size of Codes) II Siavosh Benabbas
05/02/2009 A little bit of Coding Theory (LP bounds on the size of Codes) I Siavosh Benabbas
22/01/2009 "Determinism versus non-determinism and related problems" by Pippenger et. al Wesley George
15/01/2009 Price of Anarchy for Combinatorial Auction Mechanisms Brendan Lucier
18/12/2008 New directions in derandomization II Periklis Papakonstantinou
10/12/2008 New directions in derandomization I Periklis Papakonstantinou
03/12/2008 Lift and Project systems as potential algorithms and their limitations II Costis Georgiou
26/11/2008 Lift and Project systems as potential algorithms and their limitations I Costis Georgiou
19/11/2008 Parity not in AC^0 Lila Fontes
12/11/2008 Introduction to compressed sensing (Basis Pursuit) Anastasios Zouzias
05/11/2008 On Distributing Symmetric Streaming Computations Anastasios Sidiropoulos
29/10/2008 Open Problems Session Paul Medvedev
17/10/2008 A Survey of Gower's Norm Shachar Lovett
15/10/2008 Intersection Graphs of Paths in a Tree (a paper of Monma and Wei) Steve Chaplick
01/10/2008 Regret bounds for online convex programming Ilya Sutskever
24/09/2008 Provable total functions of $I\exists+$ Kaveh Ghasemloo
17/09/2008 The Ogiwara-Watanabe Theorem Akitoshi Kawamura
10/09/2008 On The Impossibility of Basing Identity Based Encryption on Trapdoor Permutations Yevgeniy Vahlis
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
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.
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

Statistics

If my regular expression and grep skills are to be trusted as of Nov 14th, 2011 there have been 234 TSS talks, 88 of which have been in my tenure. The top 5 speakers are listed in the table below.

Number of Talks Speaker
21 Mark Braverman
20 Periklis Papakonstantinou
9.5 Philipp Hertel
9 Anastasios Zouzias
8 Siavosh Benabbas