School of Mathematics

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.

    On the Approximation Resistance of Balanced Linear Threshold Functions

    Aaron Potechin
    University of Chicago
    March 25, 2019
    Constraint satisfaction problems (CSPs) are a central topic of study in computer science. A fundamental question about CSPs is as follows. Given a CSP where each constraint has the form of some predicate P and almost all of the constraints can be satisfied, is there a randomized polynomial time algorithm which is guaranteed to do significantly better in expectation than a random assignment? If so, then we say that the predicate P is approximable. If not, then we say that P is approximation resistant.

    Equivariant and nonequivariant contact homology

    Jo Nelson
    Rice University
    March 20, 2019

    I will discuss joint work with Hutchings which constructs nonequivariant and a family floer equivariant version of contact homology. Both theories are generated by two copies of each Reeb orbit over Z and capture interesting torsion information. I will then explain how one can recover the original cylindrical theory proposed by Eliashberg-Givental-Hofer via our construction.

    Multiplicity One Conjecture in Min-max theory

    Xin Zhou
    University of California, Santa Barbara; Member, School of Mathematics
    March 19, 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. 

    A Brief Tour of Proof Complexity: Lower Bounds and Open Problems

    Toniann Pitassi
    University of Toronto; Visiting Professor, School of Mathematics
    March 19, 2019

    I will give a tour of some of the key concepts and ideas in proof complexity. First, I will define all standard propositional proof systems using the sequent calculus which gives rise to a clean characterization of proofs as computationally limited two-player games. I will also define algebraic and semi-algebraic systems (SOS, IPS, Polynomial Calculus).