Date  Title 
Speaker 
Friday, August 26, 2016 Room WB 130 
Frege systems for Quantified Boolean Logic 
Ilario Bonacina KTH Royal Institute of Technology 
Friday, August 12, 2016 Room WB 130 
How Limited Interaction Hinders Real
Communication (and What it Means for Proof and Circuit Complexity) 
Marc Vinyals KTH Royal Institute of Technology 
Friday, June 3, 2016 Room WB 130 
STOC Preview 1. Maximizing Determinants under Partition Constraints, Speaker: Aleksandar Nikolov 2. A Tight Space Bound for Consensus, Speaker: Leqi (Jimmy) Zhu 
Aleksandar Nikolov & Leqi (Jimmy) Zhu University of Toronto 
Tuesday, May 24, 2016 Fields Institute Room 230 Time: 10:30am11:30am 
Annual Avner Magen Memorial Lecture Conceptually simple combinatorial algorithms Website: http://www.fields.utoronto.ca/activities/1516/magenlecture 
Allan Borodin University of Toronto 
Friday, May 13, 2016 Room PT 266 
How to Elect a Leader Faster than a
Tournament 
Rati Gelashvili MIT 
Friday, March 18, 2016 Room WB 119 
How to refute a random CSP  David Witmer CMU 
Friday, February 26, 2016 Room WB 119 
Differentially private release and
learning of threshold functions 
Mark Bun Harvard University 
Friday, February 12, 2016 Room WB 119 
Budget Feasible Mechanisms on Matchings 
Qiang Zhang Institute of Informatics University of Warsaw 
Friday, February 5, 2016 Room WB 119 
How to determine if a random graph with a
fixed degree sequence has a giant component 
Bruce Reed McGill University 
Friday, December 11, 2015 Room GB 221 
Robust Shared Objects for NonVolatile
Main Memory 
Wojciech Golab University of Waterloo 
Friday, December 4, 2015 Room GB 119 
A Polynomial Lower Bound for Testing
Monotonicity 
Eric Blais University of Waterloo 
Friday, November 20, 2015 Room GB 119 
Optimal search trees with 2way
comparisons

Ian Munro University of Waterloo 
Friday, November 13, 2015 Room GB 119 
Improved Cheeger's inequalities 
Lap Chi Lau University of Waterloo 
Wednesday, November 4, 2015 Room GB 221 
Ranking and Optimal Tradeoffs in Ad
Auctions (This is a joint AI/Theory Seminar) 
Ian Kash Microsoft Research Cambridge, UK 
Friday, October 30, 2015 Room GB 119 
Approximate Degree and the Method of Dual Polynomials  Justin Thaler Yahoo Research 
Friday, September 18, 2015 Room GB 119 
Correlation Bounds Against Monotone NC^1  Ben Rossman University of Toronto 
Friday, September 11, 2015 Room GB 119 
Nonclassical polynomials as a barrier to
polynomial lower bounds 
Shachar Lovett UC San Diego 
Friday, August 14, 2015 Room GB 244 
Functional Encryption for Cascade Automata 
Dan Brownstein Ben Gurion University 
Tuesday, June 22, 2015 Room PT 266 
Prioritized Metric Structures and
Embedding 
Arnold Filtser Ben Gurion University 
Thursday, June 18, 2015 Room PT 266 
Axiomatic approach to complexity barriers 
Antonina Kolokolova Memorial University 
Friday, May 29, 2015 Room BA 1170 
Avner Magen Memorial Lecture  Lower
bounds on the size of semidefinite programming relaxations 
James R. Lee University of Washington 
Friday, March 20, 2015 Room GB 221 
Complexity Theory in Bounded Arithmetic 
Jan Pich University of Toronto 
Friday, March 6, 2015 Room GB 221 
Randomized Rounding for the Largest
jSimplex Problem 
Aleksander Nikolov Microsoft Research 
Friday, January 30, 2015 Room GB 221 
Sum of Squares Lower Bounds for the
Planted Clique Problem 
Aaron Potechin MIT 
Friday, January 23, 2015 Room GB 221 
Exact Communication Complexity via
Information Complexity 
Denis Pankratov University of Chicago 
Friday, January 9, 2015 Room GB 221 
Common Law Reasoning 
John Horty University of Maryland 
Thursday, December 18, 2014 
List decoding ReedMuller codes over small
fields 
Shachar Lovett University of California, San Diego 
Friday, December 12, 2014 
How to Verify Computations without
Reexecuting them 
Guy Rothblum Stanford University 
Friday, November 28, 2014 
Algorithmic Challenges in Computational
Advertising 
Morteza Zadimoghaddam Google Research 
Friday, November 21, 2014 
Conditional Independence, Computability,
and Measureability 
Daniel Roy University of Toronto 
Friday, November 14, 214 
Simple Approximation Algorithms for MAX
SAT 
Matthias Ullrich Poloczek Cornell University 
Friday, October 31, 2014 
Majority is not enough: Bitcoin Mining is
Vulnerable 
Eyal Ittay Cornell University 
Friday, September 26, 2014 
Exponential Separation of Information and
Communication 
Gillat Kol / Ran Raz Institute for Advanced Study 
Friday, September 19, 2014 
Graded Multilinear Maps from Lattices 
Sergey Gorbunov M.I.T 
Friday, August 22, 2014 
The StateofAffairs in the
NumberonForehead model (a biased survey) 
Arkadev Chattopadhyay Tata Institute of Fundamental Research, Mumbai 
Friday, August 15, 2014 
Extended formulations for linear
programming 
Noah Fleming & Robert Robere University of Toronto 
Friday, August 1, 2014 
Todai Robot Project: Can an AI get into
the University of Tokyo? 
Noriko Arai & Takuya Matsuzaki National Institute of Informatics (NII) Japan 
Friday, May 16, 2014 
On the Inefficiency of Standard Multiunit
Auction Formats 
Vangelis Markakis Athens University of Economics and Business, Dept. of Informatics 
Friday, May 2, 2014 
Approximate Monotone Complexity of Boolean
Functions 
Robert Robere University of Toronto 
Monday, April 28, 2014 
Price of Anarchy for Auction Revenue
(Location: Bahen 5256 at 2:00pm) 
Darrell Hoy Northwestern University 
Friday, March 28, 2014 
Formulas vs. Circuits for Small Distance
Connectivity 
Benjamin Rossman National Institute of Informatics, Tokyo 
Friday, February 28, 2014 
Hitting Sets for Multilinear ReadOnce
Algebraic Branching Programs, in any Order 
Michael Forbes M.I.T 
Friday, January 10, 2014 
(2+eps) SAT is NPhard 
Per Austrin KTH Royal Institute of Technology Stockholm 
Friday, November 01, 2013 
Backdoors to Satisfaction 
Serge Gaspers University of New South Wales and NICTA, Sydney, Australia 
Friday, October 18, 2013 
On variants of online ray searching 
Spyros Angelopoulos CNRS, France 
Friday, October 11, 2013 
Computing (and life) is all about
tradeoffs: A small sample of some computational tradeoffs 
Allan Borodin University of Toronto 
Friday, September 27, 2013 
The Complexity of Deciding Statistical
Properties of Samplable Distributions 
Tom Watson University of Toronto 
Wednesday, August 14, 2013. 
Certifying Computations 
Kurt Mehlhorn Saarland University 
Tuesday, June 18, 2013. 
Approximation Algorithms for Stochastic
Boolean Function Evaluation and Stochastic Submodular Set
Cover 
Lisa Hellerstein Polytechnic Institute of NYU 
Friday, May 24, 2013. 
Generating safe primes and safe moduli 
Joachim von zur Gathen BonnAachen International Center for Information Technology 
Friday, May 17, 2013. 
A Tight Bound for Set Disjointness in the
MessagePassing Model 
Rotem Oshman University of Toronto 
Friday, May 10, 2013. 
Multiparty Communication Complexity of
Composed Functions 
Anil Ada McGill Unviersity 
Tuesday, May 07, 2013. 
Limits on AlternationTrading Proofs for
TimeSpace Lower Bounds 
Sam Buss University of California 
Tuesday, April 30, 2013. 
MatchingA New Proof for an Ancient
Algorithm 
Vijay Vazirani Georgia Institute of Technology 
Friday, April 26, 2013. 
Direct Products in Communication
Complexity 
Omri Weinstein Princeton University 
Tuesday, March 12, 2013. 
A greedy algorithm for finding a large
2matching on a random cubic graph 
Patrick Bennett Carnegie Mellon University 
Tuesday, February 26, 2013. 
Algorithmic models of wireless
communication 
Magnus Halldorsson Reykjavik University 
Friday, February 22, 2013. 
Submodular cost allocation: applications,
algorithms and hardness results 
Alina Ena University of Illinois 
Friday, February 15, 2013. 
The Computational Complexity of Randomness 
Thomas Watson University of California, Berkeley 
Friday, February 1, 2013. 
Pebble games and computational complexity 
Siu Man Chan University of California, Berkeley 
January 29, 2013. 
Applications of Computing to Energy and
Health 
Shwetak Patel University of Washington 
January 18, 2013. 
Fast, precise and dynamic distance queries 
Moshe Lewenstein BarIlan University 
January 11, 2013. 
Relating Proof Complexity Measures and
Practical Hardness of SAT 
Jakob Nordstrom KTH Royal Institute of Technology 
December 14, 2012. 
Access Graphs Results for LRU versus FIFO
under Relative Worst Order Analysis 
Joan Boyar University of Southern Denmark 
December 7, 2012. 
Information complexity and exact
communication bounds 
Mark Braverman Princeton University 
December 4, 2012. 
Predicate Encryption for Circuits 
Sergey Gorbunov University of Toronto 
November 30, 2012. 
Online Unit Clustering 
Kim S. Larsen University of Southern Denmark 
October 30, 2012. 
Certifiable Quantum Dice 
Umesh Vazirani University of California, Berkeley 
October 12, 2012. 
Who's afraid of an abstract quantum
computer? 
ManDuen Choi University of Toronto 
October 5, 2012. 
Introduction to Geometric Complexity
Theory 
Josh Grochow University of Toronto 
September 21, 2012. 
Open Problems in Dynamic and Wireless
Networks 
Rotem Oshman University of Toronto 
September 14, 2012. 
Constructive Discrepancy Minimization by
Walking on The Edges 
Shachar Lovett University of California, San Diego 
August 28, 2012. 
Spacebounded Communication Complexity 
Periklis Papakonstantinou Tsinghua University 
August 17, 2012. 
Prefix Free Codes in Linear Time 
Jeremy Barbay University of Chile 
August 16, 2012. 
CryptDB: Processing Queries on an
Encrypted Database 
Raluca Ada Popa M.I.T 
August 3, 2012. 
Streaming Cryptography 
Periklis Papakonstantinou Tsinghua University 
July 20, 2012. 
Bounding the Cost of Stability in Games
with Restricted Interaction 
Reshef Meir Hebrew University 
May 28, 2012. 
Active (and Passive) Property Testing 
Avrim Blum Carnegie Mellon University 
May 11, 2012. 
Secret Sharing Based on the Social
Behaviors of Players 
University of Waterloo Mehrdad Nojoumian 
May 8, 2012. 
Time Space Tradeoffs in Proof Complexity 
Chris Beck Princeton University 
April 27, 2012. 
Locality from Circuit Lower Bounds 
Dieter van Melkebeek University of WisconsinMadison 
April 20, 2012. 
Quadratic Span Programs for Succinct NIZKs
without PCPs 
Mariana Raykova Columbia University 
March 9, 2012. 
Improving Christofides' Algorithm for the
st Path TSP 
HyungChan An Cornell University 
March 2, 2012. 
MiST: Guaranteed Secure Transactions on
Compromised Mobile Devices 
Yevgeniy Vahlis AT&T Security Research Center 
March 1, 2012. 
The Curious Case of NonInteractive
Commitment 
Mohammad Mahmoody Cornell University 
February 17, 2012. 
Matrix Lie Algebra Isomorphism and
Geometric Complexity Theory 
Josh Grochow University of Chicago 
February 14, 2012. 
Towards Practical Randomization in
Concurrent Data Structures 
Dan Alistarh Ecole Polytechnique Federale de Lausanne 
February 10, 2012. 
Encryption Schemes for Modern Systems 
Omkant Pandey Microsoft Research 
February 3, 2012. 
The Communication Complexity of
Aggregating Data in Directed Networks 
Rotem Oshman M.I.T. 
February 2, 2012. 
The Power of Local Information in Social
Networks 
Brendan Lucier Microsoft Research, New England 
January 26, 2012. 
Restriction Access 
Avi Wigderson Institute for Advanced Study, Princeton 
December 14, 2011. 
DNF Formulas: Certificates and Learning 
Lisa Hellerstein Polytechnic Institute of New York University 
December 2,2011. 
Tight bounds on computing errorcorrecting
codes by boundeddepth circuits with arbitrary gates 
Michal Koucky University of Toronto 
November 25, 2011. 
Algorithm Design Using Spectral Graph
Theory 
Richard Peng Carnegie Mellon University 
November 18, 2011. 
Inapproximability of NPComplete variants
of Nash equilibrium 
Per Austrin University of Toronto 
November 14, 2011. 
Intractability in Game Theory 
Christos Papadimitriou University of California, Berkeley 
November 11, 2011. 
Computing Blindfolded: New Developments in
Fully Homomorphic Encryption 
Vinod Vaikuntanathan University of Toronto 
November 4, 2011. 
Random Continued Fractions and New Attacks
on Small Exponent RSA 
Ramarathnam Venkatesan Microsoft/University of Toronto 
October 28, 2011. 
A little advice can be very helpful 
Arkadev Chattopadhyay University of Toronto 
October 14, 2011. 
Sparse Spanners via Dense Subgraphs 
Eden Chlamtac Tel Aviv University 
October 11, 2011. 
Hyperbolic dovetailing and inputthrifty
algorithms 
David Kirkpatrick University of British Columbia 
October 7, 2011. 
Computing Blindfolded: New Developments in
Fully Homomorphic Encryption 
Vinod Vaikuntanathan University of Toronto 
September 30, 2011. 
Property testing lower bounds via
communication complexity 
Eric Blais Carnegie Mellon University 
September 9, 2011. 
Conditions for Strong Synchronization in
Concurrent Algorithms 
Dr. Maged Michael IBM Thomas J. Watson Research Center 
September 2, 2011. 
Opportunistic Information Dissemination in
Mobile Adhoc Networks: The Profit of Global Synchrony 
Alessia Milani University of Bordeaux 1 
August 12, 2011. 
Finite Orbits of Language Operations 
Emilie Charlier University of Waterloo 
August 2, 2011. 
ProphetInequality Setting with
Applications to Ad Allocation 
Mohammad T. Hajiaghayi University of Maryland 
July 8, 2011. 
Models and Algorithms for Dynamic Networks 
Desmond J. Higham University of Strathclyde 
June 24, 2011. 
Random graphs without large dense
subgraphs: are they hard to certify? 
Pascal Koiran Ecole Normale Superieure de Lyon 
June 3, 2011. 
Almost Settling the Hardness of
Noncommutative Determinant 
Prahladh Harsha Tata Institute of Fundamental Research, India 
May 27, 2011. 
What is high dimensional combinatorics? 
Nathan Linial Hebrew University of Jerusalem 
May 6, 2011. 
The communication complexity of
nonsignalling distributions 
Marc Kaplan University of Montreal 
April 21, 2011. 
Almost Kwise vs. perfect kwise
independent permutations 
Shachar Lovett Institute of Advanced Study, Princeton 
April 8, 2011. 
Quadratic Time Certificates in Linear
Algebra 
Erich Kaltofen North Carolina State University 
March 11, 2011. 
Lipschitz Continuous Ordinary Differential
Equations are PolynomialSpace Complete 
Akitoshi Kawamura University of Toronto 
January 28, 2011. 
Enumeration complexity: the monomials of a
polynomial 
Yann Strozecki University of Toronto 
January 21, 2011. 
TriangleIntersecting Families of Graphs 
Yuval Filmus University of Toronto 
January 14, 2011. 
Combinatorial Approximation Algorithms for
MaxCut using Random Walks 
C. Seshadhri Sandia National Labs, Livermore 
January 7, 2011. 
On a disparity between relative
cliquewidth and relative NLCwidth 
Haiko Muller University of Leeds 
December 3, 2010. 
Elementary asymptotic extremal graph
theory is nontrivial 
Hamed Hatami McGill University 
November 26, 2010. 
Linear systems over arbitrary moduli 
Arkadev Chattopadhyay University of Toronto 
November 19, 2010. 
Fast Information Spreading in Graphs with
Large Weak Conductance 
Keren CensorHillel MIT 
November 12, 2010. 
Signatures Resilient to Continual Leakage
on Memory and Computation 
Yevgeniy Vahlis Columbia University 
November 5, 2010. 
Simplified Inapproximability for Minimum
Distance of Codes 
Per Austrin University of Toronto 
October 29, 2010. 
Approximating Sparsest Cut in Graphs of
Bounded Treewidth 
Eden Chlamtac University of Toronto 
October 8, 2010. 
Expressing a polynomial as a determinant 
Natacha Portier University of Toronto 
September 17, 2010. 
Rank Bounds for Design Matrices, with
Applications to Combinatorial Geometry and Locally
Correctable Codes 
Avi Wigderson Institute for Advanced Study, Princeton 
September 3, 2010. 
TimeSpecific Encryption 
Elizabeth Quaglia Royal Holloway, University of London 
June 14, 2010. 
On the structure of optimal greedy
computation (for Job Scheduling) 
Periklis Papakonstantinou Tsinghua University 
May 7, 2010. 
Understanding Space in Proof Complexity:
Separations and Tradeoffs via Substitutions 
Jakob Nordstrom Massachusetts Institute of Technology 
April 30, 2010. 
Matching Vector Codes" 
Sergey Yekhanin Microsoft Research 
April 19, 2010. 
Avoiding Simplicity is Complex 
Eric Allender Rutgers University 
April 16, 2010. 
Shallow circuits with highpowered inputs 
Pascal Koiran Ecole Normale Superieure de Lyon 
March 26, 2010. 
Multiarmed bandits in sponsored search
auctions 
Yogeshwer Sharma Cornell University 
March 23, 2010. 
Network Resource Allocation Games 
Thanh Nguyen Cornell University 
March 19, 2010. 
Learning and the average case 
Andrew Wan Columbia University 
March 12, 2010. 
Fairness in Secure Computation 
Dov Gordon University of Maryland 
March 9, 2010. 
Approximation Schemes for Dense Variants
of Feedback Arc Set, Correlation Clustering, and Other
Fragile Min Constraint Satisfaction Problems 
Warren Schudy Brown University 
March 5, 2010. 
Approximation in Multiobjective
Optimization 
Ilias Diakonikolas Columbia University 
February 25, 2010. 
Approximability of NP hard problems in
Learning and CSPs 
Yi Wu Carnegie Mellon University 
February 23, 2010. 
Randomly Supported Independence and
Resistance 
Per Austrin New York University 
February 12, 2010. 
New Approximation Algorithms for Densest
kSubgraph 
Eden Chlamtac Weizmann Institute of Science 
February 9, 2010. 
Communication Complexity and You: A
Winning Combination 
Joshua Brody Dartmouth College 
February 5, 2010. 
I/OEfficient Contour Queries on Terrains 
Bardia Sadri University of Toronto 
January 29, 2010. 
Polynomial Threshold Functions: Structure,
Approximation and Pseudorandomness 
Shachar Lovett Weizmann Institute of Science 
January 29, 2010. 
A linear vertex kernel for the feedback
arc set problem in tournaments and some applications of
modular decomposition in fixed parameter algorithms 
Christophe Paul Universite de Montpellier 
January 28, 2010. 
Algorithmic Phase Transitions in
Constraint Satisfaction Problems 
Dimitris Achlioptas University of California, Santa Cruz 
January 15, 2010. 
Elimination Structures in Graphs 
Yuli Ye University of Toronto 
December 17, 2009. 
Resource Oblivious Sorting on Multicores 
Vijaya Ramachandran University of Texas, Austin 
November 27, 2009. 
Lower bounds on the treewidth of boolean
formulas 
Irenee Briquel Laboratoire de l'Informatique du Parallelisme 
November 26, 2009. 
Chasing robbers on random graphs 
Pawel Pralat West Virginia University 
November 20, 2009. 
Sampling algorithms for L2 regression and
applications 
Rensselaer Polytechnic Institute Petros Drineas 
November 13, 2009. 
Polynomialtime algorithm for the leafage
of chordal graphs 
Juraj Stacho University of Toronto 
October 23, 2009. 
Functional Encryption: Beyond Public Key
Cryptography 
Brent Waters University of Texas, Austin 
October 8, 2009. 
P≠NC without bit operations 
Ketan Mulmuley University of Chicago 
September 11, 2009. 
How hard is it to approximate the best
Nash equilibrium? 
Robert Krauthgamer Weizmann Institute 
July 29, 2009. 
Simple Random Walks on Radio Networks and
HyperGraphs 
Zvi Lotker Ben Gurion University 