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.

    One-relator groups, non-positive immersions and coherence

    Henry Wilton
    Cambridge University
    March 26, 2019

    Abstract: There seems to be an analogy between the classes of fundamental groups of compact 3-manifolds and of one-relator groups.  (Indeed, many 3-manifold groups are also one-relator groups.) For instance, Dehn’s Lemma for 3-manifolds (proved by Papakyriakopoulos) can be seen as analogous to Magnus’ Freiheitssatz for one-relator groups.  But the analogy is still very incomplete, and since there are deep results on each side that have no analogue on the other, there is a strong incentive to flesh it out.

    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.

    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).