Tuesday, May 3, 2016 | Fourier tails for Boolean functions and their applications Avishay Tal (Member, School of Mathematics) |
Tuesday, April 26, 2016 | Reed-Muller codes for random erasures and errors Amir Shpilka (Tel Aviv University) |
Tuesday, April 19, 2016 | A characterization of functions with vanishing averages over products of disjoint sets Pooya Hatami (Member, School of Mathematics) |
Tuesday, April 5, 2016 | An average-case depth hierarchy theorem for Boolean circuits II Li-Yang Tan (Toyota Technological Institute, Chicago) |
Monday, April 4, 2016 | An average-case depth hierarchy theorem for Boolean circuits I Li-Yang Tan (Toyota Technological Institute, Chicago) |
Monday, March 28, 2016 | A local central limit theorem for triangles in a random graph Swastik Kopparty (Rutgers University) |
Tuesday, March 22, 2016 | The Resolution proof system Avi Wigderson (Herbert H. Maass Professor, School of Mathematics) |
Monday, March 21, 2016 | Polynomial-time tensor decompositions via sum-of-squares Tengyu Ma (Princeton University) |
Tuesday, March 15, 2016 | Proof complexity - an introduction Avi Wigderson (Herbert H. Maass Professor, School of Mathematics) |
Monday, March 14, 2016 | Lower bounds for homogeneous depth-5 arithmetic circuits over finite fields Mrinal Kumar (Rutgers University) |
Tuesday, March 8, 2016 | Fast learning requires good memory: a time-space lower bound for parity learning Ran Raz (Weizmann Institute of Science; Visiting Professor, School of Mathematics) |
Monday, March 7, 2016 | Almost optimal sum of squares lower bound for planted clique Pravesh Kothari (University of Texas, Austin) |
Tuesday, March 1, 2016 | Graph isomorphism in quasipolynomial time II László Babai (University of Chicago) |
Monday, February 29, 2016 | Graph isomorphism in quasipolynomial time I László Babai (University of Chicago) |
Tuesday, February 23, 2016 | Minkowski sums, mixed faces and combinatorial isoperimetry Karim Adiprasito (Member, School of Mathematics) |
Monday, February 22, 2016 | The deterministic communication complexity of approximate fixed point Omri Weinstein (New York University) |
Tuesday, February 16, 2016 | The singularity of symbolic matrices Avi Wigderson (Herbert H. Maass Professor, School of Mathematics) |
Tuesday, February 9, 2016 | The singularity of symbolic matrices Avi Wigderson (Herbert H. Maass Professor, School of Mathematics) |
Monday, February 8, 2016 | Bipartite perfect matching is in quasi-NC Stephen Fenner (University of South Carolina) |
Tuesday, February 2, 2016 | Constant-round interactive-proofs for delegating computations (continued) Ron Rothblum (Massachusetts Institute of Technology) |
Monday, February 1, 2016 | Constant-round interactive-proofs for delegating computations Ron Rothblum (Massachusetts Institute of Technology) |
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 | Proof Complexity Lower Bounds from Algebraic Circuit Complexity Michael Forbes (Visitor, School of Mathematics) |
Tuesday, January 12, 2016 | Anti-concentration: results and applications Hoi Nguyen (Ohio State University; von Neumann Fellow, School of Mathematics) |
Monday, December 14, 2015 | Toward the KRW conjecture: cubic lower bounds via communication complexity Or Meir (University of Haifa) |
Tuesday, December 8, 2015 | Ramanujan coverings of graphs Doron Puder (Member, School of Mathematics) |
Monday, December 7, 2015 | Bias vs low rank of polynomials with applications to list decoding and effective algebraic geometry Abhishek Bhowmick (University of Texas at Austin) |
Thursday, December 3, 2015 | Randomness Extractors
Avi Wigderson (School of Mathematics, Institute for Advanced Study) video |
Thursday, December 3, 2015 | When Do Sparse Sets Have Dense Models?
Russell Impagliazzo (University of California at San Diego and Member, School of Mathematics) video |
Thursday, December 3, 2015 | Exponential Sums, Equidistribution and Pseudo-Randomness
Jean Bourgain (School of Mathematics, Institute for Advanced Study) video |
Tuesday, December 1, 2015 | Rigidity of random Toeplitz matrices with an application to depth three circuits Avishay Tal (Member, School of Mathematics) |
Monday, November 30, 2015 | Lower bounds on the size of semidefinite programming relaxations David Steurer (Cornell University) |
Tuesday, November 24, 2015 | General systems of linear forms: equidistribution and true complexity Pooya Hatami (Member, School of Mathematics) |
Monday, November 23, 2015 | Advances on Ramsey numbers Jacob Fox (Stanford University) |
Tuesday, November 17, 2015 | Cohomology for computer science Alex Lubotzky (Hebrew University of Jerusalem) |
Monday, November 16, 2015 | How quaternion algebras over number fields are useful for creating compiler for a quantum computer? Vadym Kliuchnikov (Microsoft Research) |
Tuesday, November 10, 2015 | Exponential separation of communication and external information Gillat Kol (Member, School of Mathematics) |
Monday, November 9, 2015 | Cutting plane method: A faster algorithm for many (combinatorial) optimization problems Yin Tat Lee (Massachusetts Institute of Technology) |
Tuesday, November 3, 2015 | Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs II Gil Cohen (California Institute of Technology) |
Monday, November 2, 2015 | Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs I Gil Cohen (California Institute of Technology) |
Tuesday, October 27, 2015 | Algorithmic proof of the Lovasz Local Lemma via resampling oracles Jan Vondrák (IBM Almaden Research Center; Member, School of Mathematics) |
Monday, October 26, 2015 | Random words, longest increasing subsequences, and quantum PCA John Wright (Carnegie Mellon University) |
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 | Non-constructive combinatorics Noga Alon (Tel Aviv University; Visiting Professor, School of Mathematics) |
Monday, October 12, 2015 | Factors of polynomials of low individual degree Rafael Oliveira (Princeton University) |
Tuesday, October 6, 2015 | Invariants of random knots Chaim Even Zohar (Hebrew University of Jerusalem) |
Monday, October 5, 2015 | Is optimization computationally equivalent to online learning? Elad Hazan (Princeton University) |
Tuesday, September 29, 2015 | No talk today
No talk today () |
Monday, September 28, 2015 | Ramsey numbers of degenerate graphs Choongbum Lee (Massachusetts Institute of Technology) |
Tuesday, September 22, 2015 | Explicit two-source extractors and resilient functions II Eshan Chattopadhyay (University of Texas at Austin) |
Monday, September 21, 2015 | Explicit two-source extractors and resilient functions I Eshan Chattopadhyay (University of Texas at Austin) |