A classic is something that
everybody wants to have read
and nobody wants to read.
Mark Twain
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
| 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 |
| 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/2007 | Cut-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/2004 | Approximate 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 |
| Number of Talks | Speaker |
|---|---|
| 21 | Mark Braverman |
| 20 | Periklis Papakonstantinou |
| 9.5 | Philipp Hertel |
| 9 | Anastasios Zouzias |
| 8 | Siavosh Benabbas |