Seminars

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)