# 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