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)