Seminars

Tuesday, May 13, 2014 Anindya De , Member, School of Mathematics
A central limit theorem for Gaussian polynomials and deterministic approximate counting for polynomial threshold functions
Tuesday, April 29, 2014 Anindya De , Member, School of Mathematics
A central limit theorem for Gaussian polynomials and deterministic approximate counting for polynomial threshold functions
Monday, April 28, 2014 Yuval Peres , Microsoft Research
Search games and Optimal Kakeya Sets
Tuesday, April 22, 2014 Andris Ambainis , University of Latvia; von Neumann Fellow, School of Mathematics
Results and open problems in theory of quantum complexity
Monday, April 21, 2014 Yaoyun Shi , University of Michigan
True Randomness: Its Origin and Expansion
Tuesday, April 15, 2014 Or Meir , Member, School of Mathematics
IP = PSPACE via error correcting codes
Monday, April 14, 2014 Brett Hemenway , University of Pennsylvania
Local Correctability of Expander Codes
Tuesday, April 8, 2014 Andrew Drucker , Member, School of Mathematics
Do NP-Hard Problems Require Exponential Time?
Monday, April 7, 2014 Aravind Srinivasan , University of Maryland, College Park
Progress on algorithmic versions of the Lovasz Local Lemma
Tuesday, April 1, 2014 Valerie King , University of Victoria; Member, School of Mathematics
Byzantine Agreement in Expected Polynomial Time
Monday, March 31, 2014 Rocco Servedio , Columbia University
A polynomial lower bound for monotonicity testing of Boolean functions over hypercube and hypergrid domains
Tuesday, March 25, 2014 Bruce Kapron , University of Victoria; Member, School of Mathematics
Circular Encryption in Formal and Computational Cryptography
Monday, March 24, 2014 Mary Wootters , University of Michigan
List decodability of randomly punctured codes
Tuesday, March 18, 2014 Olga Holtz , University of California, Berkeley; von Neumann Fellow, School of Mathematics
Graph expansion and communication complexity of algorithms
Monday, March 17, 2014 Thomas Rothvoss , University of Washington, Seattle
The matching polytope has exponential extension complexity
Tuesday, March 11, 2014 Ran Raz , Weizmann Institute of Science; Visiting Professor, School of Mathematics
How to Delegate Computations: The Power of No-Signaling
Monday, March 10, 2014 Avishay Tal , Weizmann Institute
Two Structural Results for Low Degree Polynomials and Applications
Tuesday, March 4, 2014 Yuval Filmus , Member, School of Mathematics
Fast matrix multiplication
Monday, March 3, 2014 Yufei Zhao , Massachusetts Institute of Technology
The Green-Tao theorem and a relative Szemeredi theorem
Tuesday, February 25, 2014 Yuval Filmus , Member, School of Mathematics
Fast matrix multiplication
Monday, February 24, 2014 Jonathan Kelner , Massachusetts Institute of Technology
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
Tuesday, February 18, 2014 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Non-commutative arithmetic computation
Monday, February 17, 2014 Joshua Grochow , University of Toronto
Unifying known lower bounds via geometric complexity theory
Tuesday, February 11, 2014 Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Non-commutative arithmetic computation
Monday, February 10, 2014 Julia Chuzhoy , Toyota Technological Institute at Chicago
Polynomial Bounds for the Grid-Minor Theorem
Tuesday, February 4, 2014 Ori Parzanchevski , Member, School of Mathematics
Simplicial complexes as expanders
Monday, February 3, 2014 Brett Hemenway , University of Pennsylvania
Local Correctability of Expander Codes
Tuesday, January 28, 2014 Ori Parzanchevski , Member, School of Mathematics
Simplicial complexes as expanders
Monday, January 27, 2014 Aram Harrow , Massachusetts Institute of Technology
Unique games, the Lasserre hierarchy and monogamy of entanglement
Tuesday, January 21, 2014 Siu Man Chan , Princeton University
Deeper Combinatorial Lower Bounds
Monday, December 16, 2013 Gil Cohen , Weizmann Institute
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball
Tuesday, December 10, 2013 Ori Parzanchevski , Member, School of Mathematics
Simplicial complexes as expanders
Monday, December 9, 2013 Adi Shamir , Weizmann Institute
How Cryptosystems Are REALLY Broken
Tuesday, December 3, 2013 Allison Lewko , Columbia University; Member, School of Mathematics
Multi-party Interactive Coding
Monday, December 2, 2013 Adam Marcus , Yale University
A solution to Weaver's \(KS_2\)
Tuesday, November 26, 2013 Or Meir , Member, School of Mathematics
Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture
Monday, November 25, 2013 Joseph Landsberg , Texas A & M University
Geometry and matrix multiplication
Tuesday, November 19, 2013 Gillat Kol , Member, School of Mathematics
Interactive Channel Capacity
Monday, November 18, 2013 Brendan Juba , Harvard University
Efficient reasoning in PAC semantics
Tuesday, November 12, 2013 Edinah Gnang , Member, School of Mathematics
Hypermatrix Algebra, their spectral decomposition and applications
Monday, November 11, 2013 Toni Pitassi , University of Toronto
Communication Lower Bounds via Block Sensitivity
Tuesday, November 5, 2013 Anindya De , Member, School of Mathematics
Learning from positive examples
Monday, November 4, 2013 Vladimir Braverman , Johns Hopkins University
Approximating large frequency moments with pick-and-drop sampling
Tuesday, October 29, 2013
Monday, October 28, 2013
Tuesday, October 22, 2013 Van Vu , Yale University
Matrix perturbation with random noise and matrix recovery problems
Monday, October 21, 2013 Boaz Slomka , Tel Aviv University; Member, School of Mathematics
Fractional covering numbers, with an application to the Levi-Hadwiger conjecture for convex bodies
Tuesday, October 15, 2013 Noga Alon , Tel Aviv University; Visiting Professor, School of Mathematics
Minimal majority sequences
Monday, October 14, 2013 Yael Tauman-Kalai , Microsoft Research New England
Obfuscating Programs Against Algebraic Attacks
Tuesday, October 8, 2013 Ali Sinop , Member, School of Mathematics
Rounding Moment Based SDP Relaxations by Column Selection
Monday, October 7, 2013 Jacob Fox , Massachusetts Institute of Technology
Stanley-Wilf limits are typically exponential
Tuesday, October 1, 2013 Ali Kemal Sinop , Institute for Advanced Study; Member, School of Mathematics
Small set expander flows
Monday, September 30, 2013 Sanjeev Arora
Some provable bounds for deep learning
Tuesday, September 24, 2013 Mark Lewko , Member, School of Mathematics
Finite Field Restriction Estimates
Monday, September 23, 2013 Michael Krivelevich , Tel Aviv University
Using the DFS Algorithm for Finding Long Paths in Random and Pseudo-Random Graphs