Fooling polytopes

Li-Yang Tan
Stanford University
April 1, 2019

We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \mathrm{log}(n)$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any $\{0,1\}$-integer program. Joint work with Ryan O'Donnell and Rocco Servedio.

A recent perspective on invariant theory

Viswambhara Makam
Member, School of Mathematics
April 1, 2019

Invariant theory is a fundamental subject in mathematics, and is potentially applicable whenever there is symmetry at hand (group actions). In recent years, new problems and conjectures inspired by complexity have come to light. In this talk, I will describe some of these new problems, and discuss some positive and negative results regarding them.

Multiplicity One Conjecture in Min-max theory (continued)

Xin Zhou
University of California, Santa Barbara; Member, School of Mathematics
March 27, 2019

I will present a proof with some substantial details of the Multiplicity One Conjecture in Min-max theory, raised by Marques and Neves. It says that in a closed manifold of dimension between 3 and 7 with a bumpy metric, the min-max minimal hypersurfaces associated with the volume spectrum introduced by Gromov, Guth, Marques-Neves are all two-sided and have multiplicity one.

Coherence and lattices

Matthew Stover
Temple University
March 27, 2019

Abstract: I will survey (in)coherence of lattices in semisimple Lie groups, with a view toward open problems and connections with the geometry of locally symmetric spaces. Particular focus will be placed on rank one lattices, where I will discuss connections with reflection groups,  "algebraic" fibrations of lattices, and analogies with classical low-dimensional topology.

 

Factors of sparse polynomials: structural results and some algorithms

Shubhangi Saraf
Member, School of Mathematics
March 26, 2019
Are factors of sparse polynomials sparse? This is a really basic question and we are still quite far from understanding it in general.

    In this talk, I will discuss a recent result showing that this is in some sense true for multivariate polynomials when the polynomial has each variable appearing only with bounded degree. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem.