# Seminars

 Wednesday, April 22, 2015 The Correlation of Multiplicative Characters with Polynomials over Finite Fields Swastik Kopparty (Member, School of Mathematics) Wednesday, April 22, 2015 Random Walks in Linear Groups Peter Varju (Princeton University) Monday, April 13, 2015 A new approach to the sensitivity conjecture Michael Saks (Rutgers University) Tuesday, April 7, 2015 Interleaved products in special linear groups: mixing and communication complexity Emanuele Viola (Northeastern University) Monday, April 6, 2015 Natural algorithms for flow problems Nisheeth Vishnoi (École polytechnique fédérale de Lausanne) Tuesday, March 31, 2015 Kolmogorov width of discrete linear spaces: an approach to matrix rigidity Sergey Yekhanin (Microsoft Research) Monday, March 30, 2015 Intelligent learning: similarity control and knowledge transfer Vladimir Vapnik (Columbia University) Tuesday, March 24, 2015 Tractability as compressibility Dimitris Achlioptas (University of California, Santa Cruz) Monday, March 23, 2015 Random walks that find perfect objects and the Lovász local lemma Dimitris Achlioptas (University of California, Santa Cruz) Tuesday, March 17, 2015 Average-case lower bounds for formula size Ran Raz (Weizmann Institute of Science; Visiting Professor, School of Mathematics) Monday, March 16, 2015 Tight hardness of the non-commutative Grothendieck problem Oded Regev (New York University) Tuesday, March 10, 2015 Chernoff bounds for expander walks Christopher Beck (Member, School of Mathematics) Monday, March 9, 2015 Strong contraction and influences in tail spaces Elchanan Mossel (University of Pennsylvania) Tuesday, March 3, 2015 Whitney numbers via measure concentration in representation varieties Karim Adiprasito (Member, School of Mathematics) Monday, March 2, 2015 Effective-resistance-reducing flows, spectrally thin trees and asymmetric TSP Shayan Oveis Gharan (University of California, Berkeley) Tuesday, February 24, 2015 Computing inverses Louis Rowen (Bar Ilan University) Monday, February 23, 2015 Lower bounds for clique vs. independent set Mika Göös (University of Toronto) Tuesday, February 17, 2015 The log-concavity conjecture and the tropical Laplacian June Huh (Princeton University; Veblen Fellow, School of Mathematics) Monday, February 16, 2015 2-Server PIR with sub-polynomial communication Sivakanth Gopi (Princeton University) Tuesday, February 10, 2015 How to round subspaces: a new spectral clustering algorithm Ali Kemal Sinop (Simons Institute for the Theory of Computing, Berkeley) Monday, February 9, 2015 Quantum computing with noninteracting particles Alex Arkhipov (Massachusetts Institute of Technology) Tuesday, February 3, 2015 Dimension expanders via rank condensers Michael Forbes (Member, School of Mathematics) Monday, February 2, 2015 On monotonicity testing and boolean isoperimetric type theorems Subhash Khot (New York University) Tuesday, January 27, 2015 Storm - no seminar Storm - no seminar () Monday, January 26, 2015 Publicly-verifiable non-interactive arguments for delegating computation Guy Rothblum (Stanford University) Tuesday, January 20, 2015 Small value parallel repetition for general games Ankit Garg (Princeton University) Tuesday, December 9, 2014 More on sum-of-squares proofs for planted clique Avi Wigderson (Herbert H. Maass Professor, School of Mathematics) Monday, December 8, 2014 Area Laws and the complexity of quantum states Umesh Vazirani (University of California, Berkeley) Tuesday, December 2, 2014 Taming the hydra: the Word Problem, Dehn functions, and extreme integer compression Timothy Riley (Cornell University; Member, School of Mathematics) Monday, December 1, 2014 Parallel Repetition From Fortification Dana Moshkovitz (Massachusetts Institute of Technology) Tuesday, November 25, 2014 Sum-of-squares lower bounds for the planted clique problem Avi Wigderson (Herbert H. Maass Professor, School of Mathematics) Monday, November 24, 2014 Computational fair division Ariel Procaccia (Carnegie Mellon University) Tuesday, November 18, 2014 Toric origami manifolds and origami templates Tara Holm (Cornell University; von Neumann Fellow, School of Mathematics) Monday, November 17, 2014 Mutation as a computational event Adi Livnat (Virginia Tech) Tuesday, November 11, 2014 Asymptotic expansions of the central limit theorem and its applications Anindya De (Center for Discrete Mathematics and Theoretical Computer Science; Visitor, School of Mathematics) Monday, November 10, 2014 Talagrand's convolution conjecture and geometry via coupling James Lee (University of Washington) Tuesday, November 4, 2014 Sign rank, spectral gap and VC dimension Noga Alon (Tel Aviv University; Visiting Professor, School of Mathematics) Monday, November 3, 2014 Information percolation for the Ising model Eyal Lubetzky (New York University) Tuesday, October 28, 2014 Exponential separation of information and communication Gillat Kol (Member, School of Mathematics) Monday, October 27, 2014 Discretization and quantitative differentiation Assaf Naor (Princeton University) Tuesday, October 21, 2014 FOCS - no seminar FOCS - no seminar () Monday, October 20, 2014 FOCS - no seminar FOCS - no seminar () Tuesday, October 14, 2014 Sampling-based proof of the quasipolynomial Bogolyubov-Ruzsa theorem and algorithmic applications Noga Ron-Zewi (Member, School of Mathematics) Monday, October 13, 2014 Cool with a Gaussian: an $O^*(n^3)$ volume algorithm Santosh Vempala (Georgia Institute of Technology) Tuesday, October 7, 2014 Monotone submodular maximization over a matroid Yuval Filmus (Member, School of Mathematics) Monday, October 6, 2014 The communication complexity of distributed subgraph detection Rotem Oshman (Tel Aviv University) Tuesday, September 30, 2014 Uniform words are primitive (cont'd) Doron Puder (Member, School of Mathematics) Monday, September 29, 2014 Breaking $e^n$ barrier for deterministic poly-time approximation of the permanent and settling Friedland's conjecture on the Monomer-Dimer Entropy Leonid Gurvits (City University of New York) Tuesday, September 23, 2014 Uniform words are primitive Doron Puder (Member, School of Mathematics) Monday, September 22, 2014 Colouring graphs with no odd holes Paul Seymour (Princeton University)