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:30am-11:30am |
Annual Avner Magen Memorial Lecture Conceptually simple combinatorial algorithms Website: http://www.fields.utoronto.ca/activities/15-16/magen-lecture |
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 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 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 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 M.I.T |
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) Japan |
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 M.I.T |
Friday, January 10, 2014 |
(2+eps) -SAT is NP-hard |
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 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 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 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 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 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 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. |
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 |