Real rooted polynomials and multivariate extensions

Adam Marcus
Princeton University; von Neumann Fellow, School of Mathematics
October 18, 2016
I will introduce two notions that generalize the idea of real rootedness to multivariate polynomials: real stability and hyperbolicity. I will then show two applications of these types of polynomials that will (hopefully) be of interest to the CS audience---Gurvits' method for lower bounding the permanent and a generalization of semidefinite programming known as hyperbolic programming.

The Hasse-Weil zeta functions of the intersection cohomology of minimally compactified orthogonal Shimura varieties

Yihang Zhu
Harvard University
October 20, 2016
Initiated by Langlands, the problem of computing the Hasse-Weil zeta functions of Shimura varieties in terms of automorphic L-functions has received continual study. We will discuss how recent progress in various aspects of the field has allowed the extension of the project to some Shimura varieties not treated before.

On the query complexity of Boolean monotonicity testing

Xi Chen
Columbia University
October 24, 2016
Monotonicity testing has been a touchstone problem in property testing for more than fifteen years, with many exciting recent developments in just the past few years. When specialized to Boolean-valued functions over $\{0,1\}^n$, we are interested in the number of queries required to distinguish whether an unknown function is monotone or far from every monotone function. In this talk we discuss recent results on Boolean monotonicity testing and some related problems, focusing on the lower bound side.

Regularity methods in combinatorics, number theory, and computer science

Jacob Fox
Stanford University
October 24, 2016
Understanding the structure of large graphs is a fundamental problem, as it can yield critical insights into topics ranging from the spread of diseases to how the brain works to patterns in the primes. Szemerédi's regularity lemma gives a rough structural result for all graphs. It is one of the most powerful tools in graph theory, with many applications in combinatorics, number theory, and computer science. Roughly speaking, it says that every graph can be partitioned into a small number of parts such that between almost all pairs of parts the graph is random-like.

Sum of squares, quantum entanglement, and log rank

David Steurer
Cornell University; Member, School of Mathematics
October 25, 2016
The sum-of-squares (SOS) method is a conceptually simple algorithmic technique for polynomial optimization that---quite surprisingly---captures and generalizes the best known efficient algorithms for a wide range of NP-hard optimization problems. For many of these, especially problems related to Khot's Unique Games Conjecture, no strong limitations for SOS are known, unlike for many other algorithmic techniques. Therefore, there is hope that SOS gives efficient algorithms with significantly stronger guarantees than other techniques.

Towards a theory of singular symplectic varieties

Aleksey Zinger
Stony Brook University
October 25, 2016
Singular algebraic (sub)varieties are fundamental to the theory of smooth projective manifolds. In parallel with his introduction of pseudo-holomorphic curve techniques into symplectic topology 30 years ago, Gromov asked about the feasibility of introducing notions of singular (sub)varieties suitable for this field. I will describe a new perspective on this question and motivate its appropriateness in the case of normal crossings singularities.

Arithmetic regularity, removal, and progressions

Jacob Fox
Stanford University
October 25, 2016
A celebrated theorem of Roth from 1953 shows that every dense set of integers contains a three-term arithmetic progression. This has been the starting point for the development of an enormous amount of beautiful mathematics. In this talk, I will discuss some shocking developments over the last few months on the bounds on some of the well-studied variants of Roth's theorem.