Date Title
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:30am-11:30am
Annual Avner Magen Memorial Lecture

Conceptually simple combinatorial algorithms

Allan Borodin
University of Toronto
Friday, May 13, 2016
Room PT 266
How to Elect a Leader Faster than a Tournament
Rati Gelashvili
Friday, March 18, 2016
Room WB 119
How to refute a random CSP David Witmer
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 Non-Volatile 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 2-way 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 j-Simplex Problem
Aleksander Nikolov
Microsoft Research
Friday, January 30, 2015
Room GB 221
Sum of Squares Lower Bounds for the Planted Clique Problem
Aaron Potechin
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 Reed-Muller codes over small fields
Shachar Lovett
University of California, San Diego
Friday, December 12, 2014
How to Verify Computations without Re-executing 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
Friday, August 22, 2014
The State-of-Affairs in the Number-on-Forehead 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)
Friday, May 16, 2014
On the Inefficiency of Standard Multi-unit 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 Read-Once Algebraic Branching Programs, in any Order
Michael Forbes
Friday, January 10, 2014
(2+eps) -SAT is NP-hard
Per Austrin
KTH Royal Institute of Technology
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
Bonn-Aachen International Center for Information Technology
Friday, May 17, 2013.
A Tight Bound for Set Disjointness in the Message-Passing 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 Alternation-Trading Proofs for Time-Space Lower Bounds
Sam Buss
University of California
Tuesday, April 30, 2013.
Matching-A 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 2-matching 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
Bar-Ilan 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?
Man-Duen 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.
Space-bounded 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
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 Wisconsin-Madison
April 20, 2012.
Quadratic Span Programs for Succinct NIZKs without PCPs
Mariana Raykova
Columbia University
March 9, 2012.
Improving Christofides' Algorithm for the s-t Path TSP
Hyung-Chan 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 Non-Interactive 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
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 error-correcting codes by bounded-depth 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 NP-Complete 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 input-thrifty 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 Ad-hoc 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.
Prophet-Inequality 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 non-signalling distributions
Marc Kaplan
University of Montreal
April 21, 2011.
Almost K-wise vs. perfect k-wise 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 Polynomial-Space Complete
Akitoshi Kawamura
University of Toronto
January 28, 2011.
Enumeration complexity: the monomials of a polynomial
Yann Strozecki
University of Toronto
January 21, 2011.
Triangle-Intersecting 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 NLC-width
Haiko Muller
University of Leeds
December 3, 2010.
Elementary asymptotic extremal graph theory is non-trivial
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 Censor-Hillel
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.
Time-Specific 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 Trade-offs 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 high-powered inputs
Pascal Koiran
Ecole Normale Superieure de Lyon
March 26, 2010.
Multi-armed 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 k-Subgraph
Eden Chlamtac
Weizmann Institute of Science
February 9, 2010.
Communication Complexity and You: A Winning Combination
Joshua Brody
Dartmouth College
February 5, 2010.
I/O-Efficient 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 tree-width 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.
Polynomial-time 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 Hyper-Graphs
Zvi Lotker
Ben Gurion University