# Seminars

 Friday, June 8, 2018 Capacities, Hyperbolicity, Submodularity and all the jazz... Leonid Gurvits (The City College of New York) Friday, June 8, 2018 Combinatorial methods for PIT (and ranks of matrix spaces) Roy Meshulam (Technion) Thursday, June 7, 2018 Solution to the Paulsen problem (via operator scaling) Lap Chi Lau (University of Waterloo) Thursday, June 7, 2018 Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing Yuanzhi Li (Princeton University) Thursday, June 7, 2018 An Introduction to Geodesic Convexity Nisheeth Vishnoi (EPFL) Thursday, June 7, 2018 The dynamics of regularized flows on convex bodies James Lee (University of Washington) Wednesday, June 6, 2018 Geometric complexity theory (GCT): Algorithmic challenges in invariant theory Ketan D. Mulmuley (University of Chicago) Wednesday, June 6, 2018 Algorithmic invariant theory Visu Makam (University of Michigan) Wednesday, June 6, 2018 Some PIT problems in the light of the non-communtative rank algorithm Gábor Ivanyos (Research Institute of Computer Science and Control, Budapest) Wednesday, June 6, 2018 An algebraic algorithm for non-commutative rank over any field K.V. Subrahmanyam (Chennai Mathematical Institute) Tuesday, June 5, 2018 Tensors: rank, entropy and entanglement Matthias Christandl (University of Coppenhagen) Tuesday, June 5, 2018 Alternate minimization algorithms for scaling problems and their analysis Rafael Oliveira (University of Toronto) Tuesday, June 5, 2018 Introduction to geometric invariant theory 2: Moment polytopes Michael Walter (University of Amsterdam) Tuesday, June 5, 2018 Introduction to geometric invariant theory 1: Noncommutative duality Ankit Garg (Microsoft Research New England) Monday, June 4, 2018 An introduction to Invariant Theory Harm Derksen (University of Michigan) Monday, June 4, 2018 A gentle introduction to group representation theory Peter Buergisser (Technical University of Berlin) Monday, June 4, 2018 Motivations, connections and scope of the workshop Avi Wigderson (IAS) Monday, June 4, 2018 Motivations, connections and scope of the workshop Avi Wigderson (IAS) Thursday, April 26, 2018 Entire Regularization Path for Maximum Entropy Models Yoram Singer (Princeton University) Thursday, April 19, 2018 Online Improper Learning with an Approximation Oracle Zhiyuan Li (Princeton University) Tuesday, April 17, 2018 A simple proof of a reverse Minkowski inequality Noah Stephens-Davidowitz (Visitor, School of Mathematics) Monday, April 16, 2018 Sums of Squares Over k-Subset Hypercubes Annie Raymond (University of Massachusetts, Amherst) Thursday, April 12, 2018 Stability and Generalization in Adaptive Data Analysis Vitaly Feldman (Google Brain) Tuesday, April 10, 2018 Explicit Binary Tree Codes with Polylogarithmic Size Alphabet Gil Cohen (Princeton University) Monday, April 9, 2018 Large deviations in random graphs Eyal Lubetzky (New York University) Thursday, April 5, 2018 A Compressed Sensing View of Unsupervised Text Embeddings, Bag-of-n-Grams, and LSTMs Mikhail Khodak (Princeton University) Tuesday, March 27, 2018 Heisenberg geometry and the Goemans—Linial SDP Assaf Naor (Princeton University; Member, School of Mathematics) Monday, March 26, 2018 Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP Cody Murray (Massachusetts Institute of Technology) Tuesday, March 20, 2018 Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing (Continued) Yuanzhi Li (Princeton University) Monday, March 19, 2018 Operator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testing Yuanzhi Li (Princeton University) Tuesday, March 13, 2018 Abstract Convexity, Weak Epsilon-Nets, and Radon Number Shay Moran (University of California, San Diego; Member, School of Mathematics) Monday, March 12, 2018 Math for underprivileged high school kids Rajiv Gandhi, Dan Zaharopol (Program on Algorithmic and Combinatorial Thinking (PACT), Bridge to Enter Advanced Mathematics (BEAM)) Monday, March 12, 2018 Computer Science/Discrete Mathematics Seminar I No Seminar () Tuesday, March 6, 2018 Boolean function analysis: beyond the Boolean cube (continued) Yuval Filmus (Technion) Monday, March 5, 2018 Boolean function analysis: beyond the Boolean cube Yuval Filmus (Technion) Thursday, March 1, 2018 Small-loss bounds for online learning with partial information Thodoris Lykouris (Cornell University) Tuesday, February 27, 2018 On the Communication Complexity of Classification Problems Roi Livni (Princeton University) Monday, February 26, 2018 A Tight Bound for Hypergraph Regularity Guy Moshkovitz (Harvard University) Thursday, February 22, 2018 On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization Nadav Cohen (Member, School of Mathematics) Tuesday, February 20, 2018 Some closure results for polynomial factorization Mrinal Kumar (Harvard University) Tuesday, February 13, 2018 Model theory and ultraproducts Maryanthe Malliaris (The University of Chicago; von Neumann Fellow, School of Mathematics) Monday, February 12, 2018 Nonlinear dimensionality reduction for faster kernel methods in machine learning. Christopher Musco (Massachusetts Institute of Technology) Thursday, February 8, 2018 Seminar on Theoretical Machine Learning No Seminar () Tuesday, February 6, 2018 Outlier-Robust Estimation via Sum-of-Squares Pravesh Kothari (Princeton University; Member, School of Mathematics) Monday, February 5, 2018 Locally Repairable Codes, Storage Capacity and Index Coding Arya Mazumdar (University of Massachusetts, Amherst) Thursday, February 1, 2018 Two approaches to (Deep) Learning with Differential Privacy Kunal Talwar (Google Brain) Tuesday, January 30, 2018 Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound Amnon Ta-Shma (Tel Aviv University) Monday, January 29, 2018 Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound Amnon Ta-Shma (Tel Aviv University) Thursday, January 25, 2018 Prediction and Control of Linear Dynamical Systems Cyril Zhang (Princeton University) Tuesday, January 23, 2018 A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem Ola Svensson (École polytechnique fédérale de Lausanne) Monday, January 22, 2018 The Matching Problem in General Graphs is in Quasi-NC Ola Svensson (École polytechnique fédérale de Lausanne) Tuesday, December 12, 2017 A PSPACE construction of a hitting set for the closure of small algebraic circuits Amir Shpilka (Tel Aviv University) Monday, December 11, 2017 Learning with little data Richard Zemel (University of Toronto; Visitor, School of Mathematics) Monday, December 11, 2017 Recent advances in high dimensional robust statistics Daniel Kane (University of California, San Diego) Tuesday, December 5, 2017 Short proofs are hard to find (joint work w/ Toni Pitassi and Hao Wei) Ian Mertz (University of Toronto) Monday, December 4, 2017 General strong polarization Madhu Sudan (Harvard University) Tuesday, November 28, 2017 Geometric complexity theory from a combinatorial viewpoint Greta Panova (University of Pennsylvania; von Neumann Fellow, School of Mathematics) Monday, November 27, 2017 Everything you wanted to know about machine learning but didn't know whom to ask Sanjeev Arora (Princeton University; Visiting Professor, School of Mathematics) Monday, November 27, 2017 Beyond log-concavity: provable guarantees for sampling multi-modal distributions using simulated tempering Langevin Monte Carlo Holden Lee (Princeton University) Monday, November 27, 2017 Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound Shubhangi Saraf (Rutgers University) Tuesday, November 21, 2017 A practical guide to deep learning Richard Zemel (University of Toronto; Visitor, School of Mathematics) Monday, November 20, 2017 No seminar today No seminar today () Tuesday, November 14, 2017 Learning models: connections between boosting, hard-core distributions, dense models, GAN, and regularity II Russell Impagliazzo (University of California, San Diego) Monday, November 13, 2017 Towards a better understanding of neural networks: learning dynamics, interpretability and RL generalization Maithra Raghu (Cornell University) Monday, November 13, 2017 Learning models: connections between boosting, hard-core distributions, dense models, GAN, and regularity I Russell Impagliazzo (University of California, San Diego) Tuesday, November 7, 2017 Pseudorandom generators for unordered branching programs Eshan Chattopadhyay (Member, School of Mathematics) Monday, November 6, 2017 Naturalizing a programming language Sida Wang (Visitor, School of Mathematics) Monday, November 6, 2017 Language edit distance, $(\min,+)$-matrix multiplication & beyond Barna Saha (University of Massachusetts, Amherst) Tuesday, October 31, 2017 Cap-sets in $(F_q)^n$ and related problems Zeev Dvir (Princeton University; von Neumann Fellow, School of Mathematics) Monday, October 30, 2017 Fooling intersections of low-weight halfspaces Rocco Servedio (Columbia University) Tuesday, October 24, 2017 On the strength of comparison queries Shay Moran (University of California, San Diego; Member, School of Mathematics) Monday, October 23, 2017 A nearly optimal lower bound on the approximate degree of AC$^0$ Mark Bun (Princeton University) Tuesday, October 17, 2017 No seminar: FOCS No seminar: FOCS () Monday, October 16, 2017 Keeping IT cool: machine learning for data center cooling Nevena Lazic (Google) Monday, October 16, 2017 No seminar: FOCS No seminar: FOCS () Tuesday, October 10, 2017 Structural aspects of the null-cone problem in invariant theory Ankit Garg (Microsoft Research) Monday, October 9, 2017 Barriers for rank methods in arithmetic complexity Rafael Oliveira (University of Toronto) Tuesday, October 3, 2017 Elementary open problems in Algebra (with consequences in computational complexity) Avi Wigderson (Herbert H. Maass Professor, School of Mathematics) Monday, October 2, 2017 Hyperparameter optimization: a spectral approach Elad Hazan (Princeton University) Monday, October 2, 2017 Crossing the logarithmic barrier for dynamic boolean data structure lower bounds Omri Weinstein (Columbia University) Tuesday, September 26, 2017 Lifting theorems in communication complexity and applications Toniann Pitassi (University of Toronto; Visiting Professor, School of Mathematics) Monday, September 18, 2017 Rigorous RG: a provably efficient and possibly practical algorithm for simulating 1D quantum systems Umesh Vazirani (University of California, Berkeley)