Tuesday, December 12, 2017  Amir Shpilka , Tel Aviv University
A PSPACE construction of a hitting set for the closure of small algebraic circuits 

Monday, December 11, 2017  Richard Zemel , University of Toronto; Visitor, School of Mathematics
Learning with little data 

Monday, December 11, 2017  Daniel Kane , University of California, San Diego
Recent advances in high dimensional robust statistics 

Tuesday, December 5, 2017  Ian Mertz , University of Toronto
Short proofs are hard to find (joint work w/ Toni Pitassi and Hao Wei) 

Monday, December 4, 2017  Madhu Sudan , Harvard University
General strong polarization 

Tuesday, November 28, 2017  Greta Panova , University of Pennsylvania; von Neumann Fellow, School of Mathematics
Geometric complexity theory from a combinatorial viewpoint 

Monday, November 27, 2017  Sanjeev Arora , Princeton University; Visiting Professor, School of Mathematics
Everything you wanted to know about machine learning but didn't know whom to ask 

Monday, November 27, 2017  Holden Lee , Princeton University
Beyond logconcavity: provable guarantees for sampling multimodal distributions using simulated tempering Langevin Monte Carlo 

Monday, November 27, 2017  Shubhangi Saraf , Rutgers University
Locally testable and locally correctable codes approaching the GilbertVarshamov bound 

Tuesday, November 21, 2017  Richard Zemel , University of Toronto; Visitor, School of Mathematics
A practical guide to deep learning 

Monday, November 20, 2017  No seminar today
No seminar today 

Tuesday, November 14, 2017  Russell Impagliazzo , University of California, San Diego
Learning models: connections between boosting, hardcore distributions, dense models, GAN, and regularity II 

Monday, November 13, 2017  Maithra Raghu , Cornell University
Towards a better understanding of neural networks: learning dynamics, interpretability and RL generalization 

Monday, November 13, 2017  Russell Impagliazzo , University of California, San Diego
Learning models: connections between boosting, hardcore distributions, dense models, GAN, and regularity I 

Tuesday, November 7, 2017  Eshan Chattopadhyay , Member, School of Mathematics
Pseudorandom generators for unordered branching programs 

Monday, November 6, 2017  Sida Wang , Visitor, School of Mathematics
Naturalizing a programming language 

Monday, November 6, 2017  Barna Saha , University of Massachusetts, Amherst
Language edit distance, $(\min,+)$matrix multiplication & beyond 

Tuesday, October 31, 2017  Zeev Dvir , Princeton University; von Neumann Fellow, School of Mathematics
Capsets in $(F_q)^n$ and related problems 

Monday, October 30, 2017  Rocco Servedio , Columbia University
Fooling intersections of lowweight halfspaces 

Tuesday, October 24, 2017  Shay Moran , University of California, San Diego; Member, School of Mathematics
On the strength of comparison queries 

Monday, October 23, 2017  Mark Bun , Princeton University
A nearly optimal lower bound on the approximate degree of AC$^0$ 

Tuesday, October 17, 2017  No seminar: FOCS
No seminar: FOCS 

Monday, October 16, 2017  Nevena Lazic , Google
Keeping IT cool: machine learning for data center cooling 

Monday, October 16, 2017  No seminar: FOCS
No seminar: FOCS 

Tuesday, October 10, 2017  Ankit Garg , Microsoft Research
Structural aspects of the nullcone problem in invariant theory 

Monday, October 9, 2017  Rafael Oliveira , University of Toronto
Barriers for rank methods in arithmetic complexity 

Tuesday, October 3, 2017  Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Elementary open problems in Algebra (with consequences in computational complexity) 

Monday, October 2, 2017  Elad Hazan , Princeton University
Hyperparameter optimization: a spectral approach 

Monday, October 2, 2017  Omri Weinstein , Columbia University
Crossing the logarithmic barrier for dynamic boolean data structure lower bounds 

Tuesday, September 26, 2017  Toniann Pitassi , University of Toronto; Visiting Professor, School of Mathematics
Lifting theorems in communication complexity and applications 

Monday, September 18, 2017  Umesh Vazirani , University of California, Berkeley
Rigorous RG: a provably efficient and possibly practical algorithm for simulating 1D quantum systems 

Tuesday, April 18, 2017  Adam Marcus , Princeton University; von Neumann Fellow, School of Mathematics
Bounds on roots of polynomials (and applications) 

Monday, April 17, 2017  Yannai Gonczarowski , Hebrew University of Jerusalem and Microsoft Research
Efficient empirical revenue maximization in singleparameter auction environments 

Tuesday, April 11, 2017  Adam Marcus , Princeton University; von Neumann Fellow, School of Mathematics
Noncommutative probability for computer scientists 

Monday, April 10, 2017  Allison Bishop , Columbia University
In pursuit of obfuscation 

Tuesday, April 4, 2017  Mark Braverman , Princeton University; von Neumann Fellow, School of Mathematics
Computability and complexity in analysis and dynamics 

Monday, April 3, 2017  Ran Raz , Princeton University
A timespace lower bound for a large class of learning problems 

Tuesday, March 28, 2017  Robert Robere , University of Toronto
Applications of monotone constraint satisfaction 

Monday, March 27, 2017  Orit Raz , Member, School of Mathematics
Extremal problems in combinatorial geometry 

Monday, March 27, 2017  Robert Robere , University of Toronto
Applications of monotone constraint satisfaction 

Monday, March 20, 2017  Ankur Moitra , Massachusetts Institute of Technology
Approximate counting and the Lovasz local lemma 

Monday, March 13, 2017  Nir Bitansky , Massachusetts Institute of Technology
Indistinguishability obfuscation from 5linear maps: a reduction from flying pigs to jumping pigs 

Monday, March 13, 2017  Nir Bitansky , Massachusetts Institute of Technology
On the cryptographic hardness of finding a Nash equilibrium 

Tuesday, March 7, 2017  Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Some basic problems and results from Invariant Theory 

Monday, March 6, 2017  Yael Kalai , Microsoft Research
Interactive coding with nearly optimal round and communication blowup 

Tuesday, February 28, 2017  Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Structural and computational aspects of BrascampLieb inequalities 

Monday, February 27, 2017  Eric Allender , Rutgers University
New insights on the (non)hardness of circuit minimization and related problems 

Tuesday, February 21, 2017  Omer Paneth , Massachusetts Institute of Technology
Program obfuscation: outside the black box 

Tuesday, February 14, 2017  Matt Weinberg , Princeton University
A unified dualitybased approach to Bayesian mechanism design 

Monday, February 13, 2017  Ilya Razenshteyn , Massachusetts Institute of Technology
Nearest neighbor search for general symmetric norms via embeddings into product spaces 

Tuesday, February 7, 2017  Amir Ali Ahmadi , Princeton University
Optimization in dynamical systems 

Monday, February 6, 2017  Prasad Raghavendra , University of California, Berkeley
Strongly Refuting Random CSPs below the spectral threshold 

Tuesday, January 31, 2017  Alex Andoni , Columbia University
Sketching and embedding are equivalent for norms 

Monday, January 30, 2017  Aaron Roth , University of Pennsylvania
Quantifying tradeoffs between fairness and accuracy in online learning 

Tuesday, January 24, 2017  Shachar Lovett , University of California, San Diego
Robust sensitivity 

Monday, January 23, 2017  Shachar Lovett , University of California, San Diego
Active learning with "simple" membership queries 

Tuesday, January 17, 2017  Jordan Ellenberg , University of Wisconsin
The polynomial method: more results and open questions 

Tuesday, January 17, 2017  Jordan Ellenberg , University of Wisconsin
The polynomial method and the cap set problem 

Tuesday, December 13, 2016  Pravesh Kothari , Member, School of Mathematics
Sum of squares lower bounds for refuting any CSP 

Monday, December 12, 2016  Ronen Eldan , Weizmann Institute of Science
On gradient complexity of measures on the discrete cube 

Tuesday, December 6, 2016  Pravesh Kothari , Member, School of Mathematics
Approximate constraint satisfaction requires subexponential size linear programs 

Monday, December 5, 2016  Shubhangi Saraf , Rutgers University
On the number of ordinary lines determined by sets in complex space 

Tuesday, November 29, 2016  Orit Raz , Member, School of Mathematics
Combinatorial rigidity of graphs embedded in $\mathbb{R}^2$ 

Monday, November 28, 2016  Emmanuel Abbe , Princeton University
Stochastic block models and probabilistic reductions 

Tuesday, November 22, 2016  Zeyuan AllenZhu , Member, School of Mathematics
Theory of accelerated methods 

Monday, November 21, 2016  Uri Feige , Weizmann Institute of Science
On the effect of randomness on planted 3coloring models 

Tuesday, November 15, 2016  Eshan Chattopadhyay , Member, School of Mathematics
Nonmalleable extractors for constant depth circuits, and affine functions 

Monday, November 14, 2016  Bernard Chazelle , Princeton University
The mathematics of natural algorithms 

Tuesday, November 8, 2016  Aaron Potechin , Member, School of Mathematics
Exact tensor completion via sum of squares 

Monday, November 7, 2016  Amit Singer , Princeton University
Nonunique games over compact groups and orientation estimation in cryoEM 

Tuesday, November 1, 2016  Aviad Rubinstein , University of California, Berkeley
Settling the complexity of computing approximate twoplayer Nash equilibria 

Monday, October 31, 2016  Aviad Rubinstein , University of California, Berkeley
Communication complexity of approximate Nash equilibria 

Tuesday, October 25, 2016  David Steurer , Cornell University; Member, School of Mathematics
Sum of squares, quantum entanglement, and log rank 

Monday, October 24, 2016  Xi Chen , Columbia University
On the query complexity of Boolean monotonicity testing 

Tuesday, October 18, 2016  Adam Marcus , Princeton University; von Neumann Fellow, School of Mathematics
Real rooted polynomials and multivariate extensions 

Monday, October 17, 2016  Harm Derksen , University of Michigan
Matrix invariants and algebraic complexity theory 

Tuesday, October 11, 2016  No seminar today: FOCS
No seminar today: FOCS 

Monday, October 10, 2016  No seminar today: FOCS
No seminar today: FOCS 

Tuesday, October 4, 2016  No seminar today
No seminar today 

Monday, October 3, 2016  No seminar today
No seminar today 

Tuesday, September 27, 2016  No seminar today: postdoctoral talks
No seminar today: postdoctoral talks 

Monday, September 26, 2016  Allan Sly , Princeton University
Counting solutions to random constraint satisfaction problems 

Tuesday, September 20, 2016  Gil Cohen , Princeton University
Algebraic geometric codes and their applications 

Tuesday, May 3, 2016  Avishay Tal , Member, School of Mathematics
Fourier tails for Boolean functions and their applications 

Tuesday, April 26, 2016  Amir Shpilka , Tel Aviv University
ReedMuller codes for random erasures and errors 

Tuesday, April 19, 2016  Pooya Hatami , Member, School of Mathematics
A characterization of functions with vanishing averages over products of disjoint sets 

Tuesday, April 5, 2016  LiYang Tan , Toyota Technological Institute, Chicago
An averagecase depth hierarchy theorem for Boolean circuits II 

Monday, April 4, 2016  LiYang Tan , Toyota Technological Institute, Chicago
An averagecase depth hierarchy theorem for Boolean circuits I 

Monday, March 28, 2016  Swastik Kopparty , Rutgers University
A local central limit theorem for triangles in a random graph 

Tuesday, March 22, 2016  Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
The Resolution proof system 

Monday, March 21, 2016  Tengyu Ma , Princeton University
Polynomialtime tensor decompositions via sumofsquares 

Tuesday, March 15, 2016  Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Proof complexity  an introduction 

Monday, March 14, 2016  Mrinal Kumar , Rutgers University
Lower bounds for homogeneous depth5 arithmetic circuits over finite fields 

Tuesday, March 8, 2016  Ran Raz , Weizmann Institute of Science; Visiting Professor, School of Mathematics
Fast learning requires good memory: a timespace lower bound for parity learning 

Monday, March 7, 2016  Pravesh Kothari , University of Texas, Austin
Almost optimal sum of squares lower bound for planted clique 

Tuesday, March 1, 2016  László Babai , University of Chicago
Graph isomorphism in quasipolynomial time II 

Monday, February 29, 2016  László Babai , University of Chicago
Graph isomorphism in quasipolynomial time I 

Tuesday, February 23, 2016  Karim Adiprasito , Member, School of Mathematics
Minkowski sums, mixed faces and combinatorial isoperimetry 

Monday, February 22, 2016  Omri Weinstein , New York University
The deterministic communication complexity of approximate fixed point 

Tuesday, February 16, 2016  Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
The singularity of symbolic matrices 

Tuesday, February 9, 2016  Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
The singularity of symbolic matrices 

Monday, February 8, 2016  Stephen Fenner , University of South Carolina
Bipartite perfect matching is in quasiNC 

Tuesday, February 2, 2016  Ron Rothblum , Massachusetts Institute of Technology
Constantround interactiveproofs for delegating computations (continued) 

Monday, February 1, 2016  Ron Rothblum , Massachusetts Institute of Technology
Constantround interactiveproofs for delegating computations 

Tuesday, January 26, 2016  Seminar cancelled on account of snow.
Seminar cancelled on account of snow. 

Monday, January 25, 2016  Seminar cancelled on account of snow.
Seminar cancelled on account of snow. 

Tuesday, January 19, 2016  Michael Forbes , Visitor, School of Mathematics
Proof Complexity Lower Bounds from Algebraic Circuit Complexity 

Tuesday, January 12, 2016  Hoi Nguyen , Ohio State University; von Neumann Fellow, School of Mathematics
Anticoncentration: results and applications 

Monday, December 14, 2015  Or Meir , University of Haifa
Toward the KRW conjecture: cubic lower bounds via communication complexity 

Tuesday, December 8, 2015  Doron Puder , Member, School of Mathematics
Ramanujan coverings of graphs 

Monday, December 7, 2015  Abhishek Bhowmick , University of Texas at Austin
Bias vs low rank of polynomials with applications to list decoding and effective algebraic geometry 

Thursday, December 3, 2015  Avi Wigderson , School of Mathematics, Institute for Advanced Study
Randomness Extractors 
video 
Thursday, December 3, 2015  Russell Impagliazzo , University of California at San Diego and Member, School of Mathematics
When Do Sparse Sets Have Dense Models? 
video 
Thursday, December 3, 2015  Jean Bourgain , School of Mathematics, Institute for Advanced Study
Exponential Sums, Equidistribution and PseudoRandomness 
video 
Tuesday, December 1, 2015  Avishay Tal , Member, School of Mathematics
Rigidity of random Toeplitz matrices with an application to depth three circuits 

Monday, November 30, 2015  David Steurer , Cornell University
Lower bounds on the size of semidefinite programming relaxations 

Tuesday, November 24, 2015  Pooya Hatami , Member, School of Mathematics
General systems of linear forms: equidistribution and true complexity 

Monday, November 23, 2015  Jacob Fox , Stanford University
Advances on Ramsey numbers 

Tuesday, November 17, 2015  Alex Lubotzky , Hebrew University of Jerusalem
Cohomology for computer science 

Monday, November 16, 2015  Vadym Kliuchnikov , Microsoft Research
How quaternion algebras over number fields are useful for creating compiler for a quantum computer? 

Tuesday, November 10, 2015  Gillat Kol , Member, School of Mathematics
Exponential separation of communication and external information 

Monday, November 9, 2015  Yin Tat Lee , Massachusetts Institute of Technology
Cutting plane method: A faster algorithm for many (combinatorial) optimization problems 

Tuesday, November 3, 2015  Gil Cohen , California Institute of Technology
Twosource dispersers for polylogarithmic entropy and improved Ramsey graphs II 

Monday, November 2, 2015  Gil Cohen , California Institute of Technology
Twosource dispersers for polylogarithmic entropy and improved Ramsey graphs I 

Tuesday, October 27, 2015  Jan Vondrák , IBM Almaden Research Center; Member, School of Mathematics
Algorithmic proof of the Lovasz Local Lemma via resampling oracles 

Monday, October 26, 2015  John Wright , Carnegie Mellon University
Random words, longest increasing subsequences, and quantum PCA 

Tuesday, October 20, 2015  No seminar today: FOCS
No seminar today: FOCS 

Monday, October 19, 2015  No seminar today: FOCS
No seminar today: FOCS 

Tuesday, October 13, 2015  Noga Alon , Tel Aviv University; Visiting Professor, School of Mathematics
Nonconstructive combinatorics 

Monday, October 12, 2015  Rafael Oliveira , Princeton University
Factors of polynomials of low individual degree 

Tuesday, October 6, 2015  Chaim Even Zohar , Hebrew University of Jerusalem
Invariants of random knots 

Monday, October 5, 2015  Elad Hazan , Princeton University
Is optimization computationally equivalent to online learning? 

Tuesday, September 29, 2015  No talk today
No talk today 

Monday, September 28, 2015  Choongbum Lee , Massachusetts Institute of Technology
Ramsey numbers of degenerate graphs 

Tuesday, September 22, 2015  Eshan Chattopadhyay , University of Texas at Austin
Explicit twosource extractors and resilient functions II 

Monday, September 21, 2015  Eshan Chattopadhyay , University of Texas at Austin
Explicit twosource extractors and resilient functions I 

Wednesday, April 22, 2015  Swastik Kopparty , Member, School of Mathematics
The Correlation of Multiplicative Characters with Polynomials over Finite Fields 

Wednesday, April 22, 2015  Peter Varju , Princeton University
Random Walks in Linear Groups 

Monday, April 13, 2015  Michael Saks , Rutgers University
A new approach to the sensitivity conjecture 

Tuesday, April 7, 2015  Emanuele Viola , Northeastern University
Interleaved products in special linear groups: mixing and communication complexity 

Monday, April 6, 2015  Nisheeth Vishnoi , Ă‰cole polytechnique fĂ©dĂ©rale de Lausanne
Natural algorithms for flow problems 

Tuesday, March 31, 2015  Sergey Yekhanin , Microsoft Research
Kolmogorov width of discrete linear spaces: an approach to matrix rigidity 

Monday, March 30, 2015  Vladimir Vapnik , Columbia University
Intelligent learning: similarity control and knowledge transfer 

Tuesday, March 24, 2015  Dimitris Achlioptas , University of California, Santa Cruz
Tractability as compressibility 

Monday, March 23, 2015  Dimitris Achlioptas , University of California, Santa Cruz
Random walks that find perfect objects and the LovĂˇsz local lemma 

Tuesday, March 17, 2015  Ran Raz , Weizmann Institute of Science; Visiting Professor, School of Mathematics
Averagecase lower bounds for formula size 

Monday, March 16, 2015  Oded Regev , New York University
Tight hardness of the noncommutative Grothendieck problem 

Tuesday, March 10, 2015  Christopher Beck , Member, School of Mathematics
Chernoff bounds for expander walks 

Monday, March 9, 2015  Elchanan Mossel , University of Pennsylvania
Strong contraction and influences in tail spaces 

Tuesday, March 3, 2015  Karim Adiprasito , Member, School of Mathematics
Whitney numbers via measure concentration in representation varieties 

Monday, March 2, 2015  Shayan Oveis Gharan , University of California, Berkeley
Effectiveresistancereducing flows, spectrally thin trees and asymmetric TSP 

Tuesday, February 24, 2015  Louis Rowen , Bar Ilan University
Computing inverses 

Monday, February 23, 2015  Mika Göös , University of Toronto
Lower bounds for clique vs. independent set 

Tuesday, February 17, 2015  June Huh , Princeton University; Veblen Fellow, School of Mathematics
The logconcavity conjecture and the tropical Laplacian 

Monday, February 16, 2015  Sivakanth Gopi , Princeton University
2Server PIR with subpolynomial communication 

Tuesday, February 10, 2015  Ali Kemal Sinop , Simons Institute for the Theory of Computing, Berkeley
How to round subspaces: a new spectral clustering algorithm 

Monday, February 9, 2015  Alex Arkhipov , Massachusetts Institute of Technology
Quantum computing with noninteracting particles 

Tuesday, February 3, 2015  Michael Forbes , Member, School of Mathematics
Dimension expanders via rank condensers 

Monday, February 2, 2015  Subhash Khot , New York University
On monotonicity testing and boolean isoperimetric type theorems 

Tuesday, January 27, 2015  Storm  no seminar
Storm  no seminar 

Monday, January 26, 2015  Guy Rothblum , Stanford University
Publiclyverifiable noninteractive arguments for delegating computation 

Tuesday, January 20, 2015  Ankit Garg , Princeton University
Small value parallel repetition for general games 

Tuesday, December 9, 2014  Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
More on sumofsquares proofs for planted clique 

Monday, December 8, 2014  Umesh Vazirani , University of California, Berkeley
Area Laws and the complexity of quantum states 

Tuesday, December 2, 2014  Timothy Riley , Cornell University; Member, School of Mathematics
Taming the hydra: the Word Problem, Dehn functions, and extreme integer compression 

Monday, December 1, 2014  Dana Moshkovitz , Massachusetts Institute of Technology
Parallel Repetition From Fortification 

Tuesday, November 25, 2014  Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
Sumofsquares lower bounds for the planted clique problem 

Monday, November 24, 2014  Ariel Procaccia , Carnegie Mellon University
Computational fair division 

Tuesday, November 18, 2014  Tara Holm , Cornell University; von Neumann Fellow, School of Mathematics
Toric origami manifolds and origami templates 

Monday, November 17, 2014  Adi Livnat , Virginia Tech
Mutation as a computational event 

Tuesday, November 11, 2014  Anindya De , Center for Discrete Mathematics and Theoretical Computer Science; Visitor, School of Mathematics
Asymptotic expansions of the central limit theorem and its applications 

Monday, November 10, 2014  James Lee , University of Washington
Talagrand's convolution conjecture and geometry via coupling 

Tuesday, November 4, 2014  Noga Alon , Tel Aviv University; Visiting Professor, School of Mathematics
Sign rank, spectral gap and VC dimension 

Monday, November 3, 2014  Eyal Lubetzky , New York University
Information percolation for the Ising model 

Tuesday, October 28, 2014  Gillat Kol , Member, School of Mathematics
Exponential separation of information and communication 

Monday, October 27, 2014  Assaf Naor , Princeton University
Discretization and quantitative differentiation 

Tuesday, October 21, 2014  FOCS  no seminar
FOCS  no seminar 

Monday, October 20, 2014  FOCS  no seminar
FOCS  no seminar 

Tuesday, October 14, 2014  Noga RonZewi , Member, School of Mathematics
Samplingbased proof of the quasipolynomial BogolyubovRuzsa theorem and algorithmic applications 

Monday, October 13, 2014  Santosh Vempala , Georgia Institute of Technology
Cool with a Gaussian: an \(O^*(n^3)\) volume algorithm 

Tuesday, October 7, 2014  Yuval Filmus , Member, School of Mathematics
Monotone submodular maximization over a matroid 

Monday, October 6, 2014  Rotem Oshman , Tel Aviv University
The communication complexity of distributed subgraph detection 

Tuesday, September 30, 2014  Doron Puder , Member, School of Mathematics
Uniform words are primitive (cont'd) 

Monday, September 29, 2014  Leonid Gurvits , City University of New York
Breaking \(e^n\) barrier for deterministic polytime approximation of the permanent and settling Friedland's conjecture on the MonomerDimer Entropy 

Tuesday, September 23, 2014  Doron Puder , Member, School of Mathematics
Uniform words are primitive 

Monday, September 22, 2014  Paul Seymour , Princeton University
Colouring graphs with no odd holes 

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 NPHard 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 NoSignaling 

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 GreenTao 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 AlmostLinearTime 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
Noncommutative 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
Noncommutative arithmetic computation 

Monday, February 10, 2014  Julia Chuzhoy , Toyota Technological Institute at Chicago
Polynomial Bounds for the GridMinor 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
BiLipschitz 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
Multiparty 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 pickanddrop 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 LeviHadwiger 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 TaumanKalai , 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
StanleyWilf 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 PseudoRandom Graphs 

Tuesday, May 14, 2013  No Seminar Talk


Monday, May 13, 2013  Raghu Meka , DIMACS (Rutgers); Member, School of Mathematics
Association Schemes, NonCommutative Polynomials and Lasserre Lower Bounds for Planted Clique 

Monday, May 13, 2013  Andrew Drucker , Member, School of Mathematics
Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers 

Tuesday, May 7, 2013  No Seminar Talk


Monday, May 6, 2013  Rotem Oshman , University of Toronto
Tight Bounds for Set Disjointness in the MessagePassing Model 

Tuesday, April 30, 2013  Michal Feldman , Hebrew University of Jerusalem
Combinatorial Walrasian Equilibrium 

Monday, April 29, 2013  Michael Rabin , Harvard University and Columbia University
Cryptography and Preventing Collusion in Second Price (Vickery) Auctions 

Tuesday, April 23, 2013  Klim Efremenko , TelAviv University; Member, School of Mathematics
Uncertainty Principle 

Monday, April 22, 2013  Daniel Kane , Stanford University
Diffuse Decompositions of Polynomials 

Tuesday, April 16, 2013  No Seminar Talk


Monday, April 15, 2013  Irit Dinur , Weizmann Institute; Radcliffe institute
Analytical Approach to Parallel Repetition 

Tuesday, April 9, 2013  Jozsef Beck , Rutgers, The State University of New Jersey
"What is Geometric Entropy, and Does it Really Increase?" 

Monday, April 8, 2013  No Seminar Talk


Tuesday, April 2, 2013  Sushant Sachdeva , Princeton University
An Arithmetic Analogue of Fox's Improved Triangle Removal Lemma 

Monday, April 1, 2013  Thomas Vidick , Massachusetts Institute of Technology
Device Independence: A New Paradigm for Randomness Manipulation? 

Tuesday, March 26, 2013  No Seminar Talk


Monday, March 25, 2013  Madhu Sudan , Microsoft Research
New Locally Decodable Codes from Lifting 

Tuesday, March 19, 2013  Hao Huang , University of California, Los Angeles; Member, School of Mathematics
Sensitivity Versus Block Sensitivity, II 

Monday, March 18, 2013  Eli BenSasson , Technion; Massachusetts Institute of Technology
Constant Rate PCPs for CircuitSAT with Sublinear Query Complexity 

Tuesday, March 12, 2013  Hao Huang , University of California, Los Angeles; Member, School of Mathematics
Sensitivity Versus Block Sensitivity, I 

Monday, March 11, 2013  Tim Roughgarden , Stanford University
Intractability in Algorithmic Game Theory 

Tuesday, March 5, 2013  Avi Wigderson , School of Mathematics, IAS
Derandomization of Probabilistic Logspace (The Nisan Variations) 

Monday, March 4, 2013  Dhruv Mubayi , University of Illinois at Chicago
Quasirandom Hypergraphs 

Tuesday, February 26, 2013  Avi Wigderson , School of Mathematics, IAS
Derandomizing BPL? 

Monday, February 25, 2013  Emmanuel Abbe , Princeton University
Polar Codes and Randomness Extraction for Structured Sources 

Tuesday, February 19, 2013  Shubhangi Saraf , Rutgers, The State University of New Jersey
The Chasm at Depth 3 

Monday, February 18, 2013  Penny Haxell , University of Waterloo
Connectedness, Sperner's Lemma and Combinatorial Problems 

Tuesday, February 12, 2013  Alex Lubotzky , Hebrew University
High Dimensional Expanders and Ramanujan Complexes 

Monday, February 11, 2013  Liu Yang , School of Computer Science, Carnegie Mellon University
Mathematical Theories of Interaction with Oracles: Active Property Testing and New Models for Learning Boolean Functions 

Tuesday, February 5, 2013  Manor Mendel , The Open University of Israel; Member, School of Mathematics
Ramsey Theory for Metric Spaces 

Monday, February 4, 2013  Gil Kalai , Hebrew University; Yale University
Influences, Traces, Tribes, and Perhaps Also Thresholds 

Tuesday, January 29, 2013  Manor Mendel , The Open University of Israel; Member, School of Mathematics
The Ribe Program 

Monday, January 28, 2013  Xin Li , University of Washington
New Independent Source Extractors with Exponential Improvement 

Tuesday, January 22, 2013  Jelani Nelson , Member, School of Mathematics
Sparsity Lower Bounds for Dimensionality Reducing Maps 

Monday, January 21, 2013  Sebastien Bubeck , Princeton University
Clique Number of Random Geometric Graphs in High Dimension 

Tuesday, January 15, 2013  Jelani Nelson , Member, School of Mathematics
OSNAP: Faster Numerical Linear Algebra Algorithms Via Sparser Subspace Embeddings 

Monday, January 14, 2013  Pavel Hrubes , University of Washington
On Bilinear Complexity 

Tuesday, December 18, 2012  (1) Raghu Meka and (2) Avi Wigderson , (1) DIMACS; (2) IAS
The SOS (aka Lassere/Positivestellensatz/SumofSquares) System 

Monday, December 17, 2012  No Seminar


Tuesday, December 11, 2012  Or Meir , Stanford University; Member, School of Mathematics
Combinatorial PCPs with Short Proofs 

Monday, December 10, 2012  Vijay Vazirani , Georgia Institute of Technology
Matching: A New Proof for an Ancient Algorithm 

Tuesday, December 4, 2012  Ran Raz , Weizmann Institute; Member, School of Mathematics
Delegation for Bounded Space 

Monday, December 3, 2012  Mark Braverman , Princeton University
Information Complexity and Exact Communication Bounds 

Tuesday, November 27, 2012  Jing Chen , Massachusetts Institute of Technology; Member, School of Mathematics
Computational Complexity in Mechanism Design 

Monday, November 26, 2012  Michael Forbes , Massachusetts Institute of Technology
Polynomial Identity Testing of ReadOnce Oblivious Algebraic Branching Progress 

Tuesday, November 20, 2012  Joseph Landsberg , Texas A&M University
On the Complexity of Matrix Multiplication and Other Tensors 

Monday, November 19, 2012  JinYi Cai , University of Wisconsin
A Complete Dichotomy Rises from the Capture of Vanishing Signatures 

Tuesday, November 13, 2012  No Seminar (Oberwolfach)


Monday, November 12, 2012  No Seminar (Oberwolfach)


Tuesday, November 6, 2012  Jing Chen , Massachusetts Institute of Technology; Member, School of Mathematics
Games, Solution Concepts, and Mechanism Design: A Very Short Introduction 

Monday, November 5, 2012  Ben Rossman , Tokyo Institute of Technology
Query Complexity of BlackBox Search 

Monday, October 29, 2012  Michal Feldman , Hebrew University and Harvard University
Combinatorial Walrasian Equilibrium 

Tuesday, October 23, 2012  No Seminar (FOCS Meeting)


Monday, October 22, 2012  No Seminar (FOCS Meeting)


Tuesday, October 16, 2012  Andrew Drucker , Massachusetts Institute of Technology; Member, School of Mathematics
On the AND and ORConjectures: Limits to Efficient Preprocessing 

Monday, October 15, 2012  Tsuyoshi Ito , NEC Laboratories America, Inc.
A MultiProver Interactive proof for NEXP Sound Against Entangled Provers 

Tuesday, October 9, 2012  Hao Huang , University of California, Los Angeles; Member, School of Mathematics
On the Conjectures of Nonnegative $k$Sum and Hypergraph Matching 

Monday, October 8, 2012  Amir Shpilka , Technion
Identity Testing of Tensors, Low Rank Recovery and Compressed Sensing 

Tuesday, October 2, 2012  Alex Russell , University of Connecticut
Plug your ears! Graph isomorphism, siren of the algebraic seas, calls to your quantum helmsman. 

Monday, October 1, 2012  Cris Moore , Santa Fe Institute
Random Vectors, Random Matrices, Permuted Products, Permanents, and Diagrammatic Fun 

Tuesday, September 25, 2012  Greg Kuperberg , University of California, Davis
Koiran + Geometric Topology implies "Knottedness is in NP" 

Monday, September 24, 2012  Greg Kuperberg , University of California, Davis
The Computational Complexity of Geometric Topology Problems 

Tuesday, May 22, 2012  No seminar today (STOC Conference)


Monday, May 21, 2012  No seminar today (STOC Conference)


Tuesday, May 15, 2012  Klim Efremenko , Tel Aviv University
From Irreducible Representations to Locally Decodable Codes 

Monday, May 14, 2012  Nisheeth Vishnoi , Microsoft Research, Bangalore
Are Lattice Based Cryptosystems Secure Enough? 

Tuesday, May 8, 2012  Raghu Meka , Member, School of Mathematics
Pseudorandomness from Shrinkage 

Monday, May 7, 2012  Pooya Hatami , University of Chicago
Topology of Norms Defined by Systems of Linear forms 

Tuesday, May 1, 2012  Abhishek Bhowmick , University of Texas at Austin
Lower Bounds for Matching Vector Codes 

Monday, April 30, 2012  Mario Szegedy , Rutgers, The State University of New Jersey
Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis 

Tuesday, April 24, 2012  Srikanth Srinivasan , DIMACS
Pseudorandom Generators for ReadOnce ACC^0 

Monday, April 23, 2012  Salil Vadhan , Harvard University; Visiting Researcher Microsoft Research SVC; Visiting Scholar Stanford University
Computational Entropy 

Tuesday, April 17, 2012  Laszlo Lovasz , Eotvos Lorand University, Budapest; Member, School of Mathematics
Nondeterministic Property Testing 

Monday, April 16, 2012  Sushant Sachdeva , Princeton University
NearLinear Time Approximation Algorithm for Balanced Separator 

Tuesday, April 10, 2012  Swastik Kopparty , Rutgers University
ListDecoding Multiplicity Codes 

Monday, April 9, 2012  Endre Csoka , Eotvos Lorand University, Budapest, Hungary
Random Local Algorithms 

Tuesday, April 3, 2012  Parikshit Gopalan , Microsoft Research Silicon Valley, Mountain View, CA
Better Pseudorandom Generators from Milder Pseudorandom Restrictions 

Monday, April 2, 2012  Pablo Azar , Massachusetts Institute of Technology
Rational Proofs 

Tuesday, March 27, 2012  Luca Trevisan , Stanford University
HigherOrder Cheeger Inequalities 

Monday, March 26, 2012  Jan Vondrak , IBM Almaden
Hardness of Randomized Truthful Mechanisms for Combinatorial Auctions 

Tuesday, March 20, 2012  Miklos Abert , Alfred Renyi Institute of Mathematics, Budapest
Graph Convergence, Parameter Testing and Group Actions 

Tuesday, March 20, 2012  Shachar Lovett , Member, School of Mathematics
The QuasiPolynomial FreimanRuzsa Theorem of Sanders 

Monday, March 19, 2012  Gregory Valiant , University of California, Berkeley
Optimal Estimators for Entropy, Support Size, and Related Properties 

Tuesday, March 13, 2012  Jelani Nelson , Member, School of Mathematics
Applications of FTMollification II 

Monday, March 12, 2012  Mina Teicher , BarIlan University; Member, School of Mathematics
Computational Aspects in the Braid Group and Applications to Cryptography 

Tuesday, March 6, 2012  Jelani Nelson , Member, School of Mathematics
Applications of FTMollification 

Monday, March 5, 2012  Emanuele Viola , Northeastern University
The Complexity of Distributions 

Tuesday, February 28, 2012  Christos Papadimitriou , University of California at Berkeley
Complexity, Approximability, and Mechanism Design 

Monday, February 27, 2012  Noga Zewi , Technion
An Additive Combinatorics Approach to the LogRank Conjecture in Communication Complexity 

Thursday, February 23, 2012  Amir Yehudayoff , TechnionIsrael Institute of Technology
Building Expanders in Three Steps 

Thursday, February 23, 2012  Boaz Barak , Microsoft Research New England
Zero Knowledge Proofs and Nuclear Disarmament 

Tuesday, February 21, 2012  Joel Spencer , Courant Institute, NYU
Finding Needles in Exponential Haystacks 

Monday, February 20, 2012  Venkat Guruswami , Carnegie Mellon University
Lasserre Hierarchy, Higher Eigenvalues, and Graph Partitioning 

Tuesday, February 14, 2012  Benjamin Matschke , Member, School of Mathematics
On the Colored Tverberg Problem 

Monday, February 13, 2012  Andrew Drucker , Massachusetts Institute of Technology
HighConfidence Predictions under Adversarial Uncertainty 

Tuesday, February 7, 2012  David Zuckerman , University of Texas at Austin; Member, School of Mathematics
Randomness Extraction: A Survey 

Monday, February 6, 2012  Fan Chung , University of California at San Diego
Graphlets: A Spectral Perspective for Graph Limits 

Tuesday, January 31, 2012  Avi Wigderson , Herbert H. Maass Professor, School of Mathematics
A Survey of Lower Bounds for the Resolution Proof System 

Monday, January 30, 2012  Santosh Vempala , Georgia Institute of Technology
Nearly Optimal Deterministic Algorithms Via MEllipsoids 

Tuesday, January 24, 2012  Russell Impagliazzo , University of California, San Diego; Member, School of Mathematics
A Tutorial on the Likely WorstCase Complexities of NPComplete Problems 

Monday, January 23, 2012  Michael Saks , Rutgers, The State University of New Jersey
An Optimal Lower Bound for File Maintenance 

Tuesday, December 13, 2011  Christopher Beck , Princeton University
TimeSpace Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space 

Monday, December 12, 2011  Pavel Hrubes , University of Calgary
Monotone Unification Problems 

Tuesday, December 6, 2011  Menachem Magidor , Hebrew University
Can the Continuum Problem be Solved? 

Monday, December 5, 2011  Mark Braverman , Princeton University
Towards Coding for Maximum Errors in Interactive Communication 

Tuesday, November 29, 2011  Raghu Meka , Member, School of Mathematics
Shorter Long Code and Applications to Unique Games 

Monday, November 28, 2011  Oded Regev , CNRSENSParis and Tel Aviv University
EntropyBased Bounds on Dimension Reduction in L_1 

Tuesday, November 22, 2011  Raghu Meka , Member, School of Mathematics
Shorter Long Code and Applications to Unique Games 

Monday, November 21, 2011  Siavosh Benabbas , University of Toronto
An Isoperimetric Inequality for the Hamming Cube and Integrality Gaps in BoundedDegree Graphs 

Tuesday, November 15, 2011  Ankur Moitra , Massachusetts Institute of Technology; Member, School of Mathemtics
Vertex Sparsification: An Introduction, Connections and Applications 

Monday, November 14, 2011  Mihalis Yannakakis , Columbia University
Polynomial Time Algorithms for MultiType Branching Processes and Stochastic ContextFree Grammars 

Tuesday, November 8, 2011  Ankur Moitra , Massachusetts Institute of Technology; Member, School of Mathematics
Vertex Sparsification: An Introduction, Connections and Applications 

Monday, November 7, 2011  Sigal Oren , Cornell University
How Bad is Forming Your Own Opinion 

Tuesday, November 1, 2011  No Seminar (CCI Quantum Computation Workshop)


Monday, October 31, 2011  Jeff Kahn , Rutgers, The State University of New Jersey
Mantel's Theorem for Random Graphs 

Tuesday, October 25, 2011  No Seminar (FOCS 2011 Meeting)


Monday, October 24, 2011  No Seminar (FOCS 2011 Meeting)


Tuesday, October 18, 2011  Ohad Feldheim , Tel Aviv University
Rigidity of 3Colorings of the dDimensional Discrete Torus 

Monday, October 17, 2011  Michael Krivelevich , Tel Aviv University
On the Number of Hamilton Cycles in PsdueoRandom Graphs 

Tuesday, October 11, 2011  Balazs Szegedy , University of Toronto; Member, School of Mathematics
Limit Theories and Higher Order Fourier Analysis 

Monday, October 10, 2011  Arkadev Chattopadhyay , University of Toronto
A Little Advice Can Be Very Helpful 

Tuesday, October 4, 2011  Balazs Szegedy , University of Toronto; Member, School of Mathematics
Limit Theories and Higher Order Fourier Analysis 

Monday, October 3, 2011  Jing Chen , Massachusetts Institute of Technology
Mechanism Design With SetTheoretic Beliefs 

Tuesday, September 27, 2011  Shubhangi Saraf , Microsoft Research; Member, School of Mathematics
Tight Lower Bounds for 2query LCCs Over Finite fields 

Monday, September 26, 2011  Benny Sudakov , University of California, Los Angeles
Nonnegative kSums, Fractional Covers, and Probability of Small Deviations 

Tuesday, September 20, 2011  Shachar Lovett , Member, School of Mathematics
Existence of Small Families of twise Independent Permutations and tDesigns Via Local Limit Theorems 