# Seminars

 Tuesday, March 13, 2018 Shay Moran , University of California, San Diego; Member, School of Mathematics Abstract Convexity, Weak Epsilon-Nets, and Radon Number Monday, March 12, 2018 Rajiv Gandhi, Dan Zaharopol , Program on Algorithmic and Combinatorial Thinking (PACT), Bridge to Enter Advanced Mathematics (BEAM) Math for underprivileged high school kids Monday, March 12, 2018 Tuesday, March 6, 2018 Yuval Filmus , Technion Boolean function analysis: beyond the Boolean cube (continued). Monday, March 5, 2018 Yuval Filmus , Technion Boolean function analysis: beyond the Boolean cube. Thursday, March 1, 2018 Thodoris Lykouris , Cornell University Small-loss bounds for online learning with partial information Tuesday, February 27, 2018 Roi Livni , Princeton University On the Communication Complexity of Classification Problems Monday, February 26, 2018 Guy Moshkovitz , Harvard University A Tight Bound for Hypergraph Regularity Thursday, February 22, 2018 Nadav Cohen , Member, School of Mathematics On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization Tuesday, February 20, 2018 Mrinal Kumar , Harvard University Some closure results for polynomial factorization Tuesday, February 13, 2018 Maryanthe Malliaris , The University of Chicago; von Neumann Fellow, School of Mathematics Model theory and ultraproducts Monday, February 12, 2018 Christopher Musco , Massachusetts Institute of Technology Nonlinear dimensionality reduction for faster kernel methods in machine learning. Thursday, February 8, 2018 No Seminar Tuesday, February 6, 2018 Pravesh Kothari Outlier-Robust Estimation via Sum-of-Squares Monday, February 5, 2018 Arya Mazumdar , University of Massachusetts, Amherst Locally Repairable Codes, Storage Capacity and Index Coding Thursday, February 1, 2018 Kunal Talwar Two approaches to (Deep) Learning with Differential Privacy Tuesday, January 30, 2018 Amnon Ta-Shma , Tel Aviv University Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound Monday, January 29, 2018 Amnon Ta-Shma , Tel Aviv University Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound Thursday, January 25, 2018 Cyril Zhang , Princeton University Prediction and Control of Linear Dynamical Systems Tuesday, January 23, 2018 Ola Svensson , Ã‰cole polytechnique fÃ©dÃ©rale de Lausanne A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem Monday, January 22, 2018 Ola Svensson , Ã‰cole polytechnique fÃ©dÃ©rale de Lausanne The Matching Problem in General Graphs is in Quasi-NC 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 log-concavity: provable guarantees for sampling multi-modal distributions using simulated tempering Langevin Monte Carlo Monday, November 27, 2017 Shubhangi Saraf , Rutgers University Locally testable and locally correctable codes approaching the Gilbert-Varshamov 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, hard-core 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, hard-core 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 Cap-sets in $(F_q)^n$ and related problems Monday, October 30, 2017 Rocco Servedio , Columbia University Fooling intersections of low-weight 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 null-cone 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 single-parameter 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 time-space 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 5-linear 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 Brascamp-Lieb 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 duality-based 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 sub-exponential 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 Allen-Zhu , 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 3-coloring models Tuesday, November 15, 2016 Eshan Chattopadhyay , Member, School of Mathematics Non-malleable 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 Non-unique games over compact groups and orientation estimation in cryo-EM Tuesday, November 1, 2016 Aviad Rubinstein , University of California, Berkeley Settling the complexity of computing approximate two-player 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 Reed-Muller 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 Li-Yang Tan , Toyota Technological Institute, Chicago An average-case depth hierarchy theorem for Boolean circuits II Monday, April 4, 2016 Li-Yang Tan , Toyota Technological Institute, Chicago An average-case 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 Polynomial-time tensor decompositions via sum-of-squares 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 depth-5 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 time-space 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 quasi-NC Tuesday, February 2, 2016 Ron Rothblum , Massachusetts Institute of Technology Constant-round interactive-proofs for delegating computations (continued) Monday, February 1, 2016 Ron Rothblum , Massachusetts Institute of Technology Constant-round interactive-proofs 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 Anti-concentration: 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 Pseudo-Randomness 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 Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs II Monday, November 2, 2015 Gil Cohen , California Institute of Technology Two-source 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 Non-constructive 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 two-source extractors and resilient functions II Monday, September 21, 2015 Eshan Chattopadhyay , University of Texas at Austin Explicit two-source 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 Average-case lower bounds for formula size Monday, March 16, 2015 Oded Regev , New York University Tight hardness of the non-commutative 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 Effective-resistance-reducing 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 log-concavity conjecture and the tropical Laplacian Monday, February 16, 2015 Sivakanth Gopi , Princeton University 2-Server PIR with sub-polynomial 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 Publicly-verifiable non-interactive 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 sum-of-squares 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 Sum-of-squares 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 Ron-Zewi , Member, School of Mathematics Sampling-based proof of the quasipolynomial Bogolyubov-Ruzsa 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 poly-time approximation of the permanent and settling Friedland's conjecture on the Monomer-Dimer 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 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 Tuesday, May 14, 2013 No Seminar Talk Monday, May 13, 2013 Raghu Meka , DIMACS (Rutgers); Member, School of Mathematics Association Schemes, Non-Commutative 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 Message-Passing 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 , Tel-Aviv 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 Ben-Sasson , Technion; Massachusetts Institute of Technology Constant Rate PCPs for Circuit-SAT 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/Sum-of-Squares) 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 Read-Once 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 Jin-Yi 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 Black-Box 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 OR-Conjectures: Limits to Efficient Preprocessing Monday, October 15, 2012 Tsuyoshi Ito , NEC Laboratories America, Inc. A Multi-Prover 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 Read-Once 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 Near-Linear Time Approximation Algorithm for Balanced Separator Tuesday, April 10, 2012 Swastik Kopparty , Rutgers University List-Decoding 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 Higher-Order 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 Quasi-Polynomial Freiman-Ruzsa 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 FT-Mollification II Monday, March 12, 2012 Mina Teicher , Bar-Ilan 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 FT-Mollification 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 Log-Rank Conjecture in Communication Complexity Thursday, February 23, 2012 Amir Yehudayoff , Technion--Israel 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 High-Confidence 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 M-Ellipsoids Tuesday, January 24, 2012 Russell Impagliazzo , University of California, San Diego; Member, School of Mathematics A Tutorial on the Likely Worst-Case Complexities of NP-Complete 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 Time-Space 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 , CNRS-ENS-Paris and Tel Aviv University Entropy-Based 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 Bounded-Degree 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 Multi-Type Branching Processes and Stochastic Context-Free 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 3-Colorings of the d-Dimensional Discrete Torus Monday, October 17, 2011 Michael Krivelevich , Tel Aviv University On the Number of Hamilton Cycles in Psdueo-Random 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 Set-Theoretic Beliefs Tuesday, September 27, 2011 Shubhangi Saraf , Microsoft Research; Member, School of Mathematics Tight Lower Bounds for 2-query LCCs Over Finite fields Monday, September 26, 2011 Benny Sudakov , University of California, Los Angeles Nonnegative k-Sums, Fractional Covers, and Probability of Small Deviations Tuesday, September 20, 2011 Shachar Lovett , Member, School of Mathematics Existence of Small Families of t-wise Independent Permutations and t-Designs Via Local Limit Theorems