# Seminars

 Tuesday, April 18, 2017 Bounds on roots of polynomials (and applications) Adam Marcus (Princeton University; von Neumann Fellow, School of Mathematics) Monday, April 17, 2017 Efficient empirical revenue maximization in single-parameter auction environments Yannai Gonczarowski (Hebrew University of Jerusalem and Microsoft Research) Tuesday, April 11, 2017 Noncommutative probability for computer scientists Adam Marcus (Princeton University; von Neumann Fellow, School of Mathematics) Monday, April 10, 2017 In pursuit of obfuscation Allison Bishop (Columbia University) Tuesday, April 4, 2017 Computability and complexity in analysis and dynamics Mark Braverman (Princeton University; von Neumann Fellow, School of Mathematics) Monday, April 3, 2017 A time-space lower bound for a large class of learning problems Ran Raz (Princeton University) Tuesday, March 28, 2017 Applications of monotone constraint satisfaction Robert Robere (University of Toronto) Monday, March 27, 2017 Extremal problems in combinatorial geometry Orit Raz (Member, School of Mathematics) Monday, March 27, 2017 Applications of monotone constraint satisfaction Robert Robere (University of Toronto) Monday, March 20, 2017 Approximate counting and the Lovasz local lemma Ankur Moitra (Massachusetts Institute of Technology) Monday, March 13, 2017 Indistinguishability obfuscation from 5-linear maps: a reduction from flying pigs to jumping pigs Nir Bitansky (Massachusetts Institute of Technology) Monday, March 13, 2017 On the cryptographic hardness of finding a Nash equilibrium Nir Bitansky (Massachusetts Institute of Technology) Tuesday, March 7, 2017 Some basic problems and results from Invariant Theory Avi Wigderson (Herbert H. Maass Professor, School of Mathematics) Monday, March 6, 2017 Interactive coding with nearly optimal round and communication blowup Yael Kalai (Microsoft Research) Tuesday, February 28, 2017 Structural and computational aspects of Brascamp-Lieb inequalities Avi Wigderson (Herbert H. Maass Professor, School of Mathematics) Monday, February 27, 2017 New insights on the (non)-hardness of circuit minimization and related problems Eric Allender (Rutgers University) Tuesday, February 21, 2017 Program obfuscation: outside the black box Omer Paneth (Massachusetts Institute of Technology) Tuesday, February 14, 2017 A unified duality-based approach to Bayesian mechanism design Matt Weinberg (Princeton University) Monday, February 13, 2017 Nearest neighbor search for general symmetric norms via embeddings into product spaces Ilya Razenshteyn (Massachusetts Institute of Technology) Tuesday, February 7, 2017 Optimization in dynamical systems Amir Ali Ahmadi (Princeton University) Monday, February 6, 2017 Strongly Refuting Random CSPs below the spectral threshold Prasad Raghavendra (University of California, Berkeley) Tuesday, January 31, 2017 Sketching and embedding are equivalent for norms Alex Andoni (Columbia University) Monday, January 30, 2017 Quantifying tradeoffs between fairness and accuracy in online learning Aaron Roth (University of Pennsylvania) Tuesday, January 24, 2017 Robust sensitivity Shachar Lovett (University of California, San Diego) Monday, January 23, 2017 Active learning with "simple" membership queries Shachar Lovett (University of California, San Diego) Tuesday, January 17, 2017 The polynomial method: more results and open questions Jordan Ellenberg (University of Wisconsin) Tuesday, January 17, 2017 The polynomial method and the cap set problem Jordan Ellenberg (University of Wisconsin) Tuesday, December 13, 2016 Sum of squares lower bounds for refuting any CSP Pravesh Kothari (Member, School of Mathematics) Monday, December 12, 2016 On gradient complexity of measures on the discrete cube Ronen Eldan (Weizmann Institute of Science) Tuesday, December 6, 2016 Approximate constraint satisfaction requires sub-exponential size linear programs Pravesh Kothari (Member, School of Mathematics) Monday, December 5, 2016 On the number of ordinary lines determined by sets in complex space Shubhangi Saraf (Rutgers University) Tuesday, November 29, 2016 Combinatorial rigidity of graphs embedded in $\mathbb{R}^2$ Orit Raz (Member, School of Mathematics) Monday, November 28, 2016 Stochastic block models and probabilistic reductions Emmanuel Abbe (Princeton University) Tuesday, November 22, 2016 Theory of accelerated methods Zeyuan Allen-Zhu (Member, School of Mathematics) Monday, November 21, 2016 On the effect of randomness on planted 3-coloring models Uri Feige (Weizmann Institute of Science) Tuesday, November 15, 2016 Non-malleable extractors for constant depth circuits, and affine functions Eshan Chattopadhyay (Member, School of Mathematics) Monday, November 14, 2016 The mathematics of natural algorithms Bernard Chazelle (Princeton University) Tuesday, November 8, 2016 Exact tensor completion via sum of squares Aaron Potechin (Member, School of Mathematics) Monday, November 7, 2016 Non-unique games over compact groups and orientation estimation in cryo-EM Amit Singer (Princeton University) Tuesday, November 1, 2016 Settling the complexity of computing approximate two-player Nash equilibria Aviad Rubinstein (University of California, Berkeley) Monday, October 31, 2016 Communication complexity of approximate Nash equilibria Aviad Rubinstein (University of California, Berkeley) Tuesday, October 25, 2016 Sum of squares, quantum entanglement, and log rank David Steurer (Cornell University; Member, School of Mathematics) Monday, October 24, 2016 On the query complexity of Boolean monotonicity testing Xi Chen (Columbia University) Tuesday, October 18, 2016 Real rooted polynomials and multivariate extensions Adam Marcus (Princeton University; von Neumann Fellow, School of Mathematics) Monday, October 17, 2016 Matrix invariants and algebraic complexity theory Harm Derksen (University of Michigan) 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 Counting solutions to random constraint satisfaction problems Allan Sly (Princeton University) Tuesday, September 20, 2016 Algebraic geometric codes and their applications Gil Cohen (Princeton University)