School of Mathematics

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

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. 

An Application of the Universality Theorem for Tverberg Partitions

Imre Barany
Renyi Institute, Hungary and UCL, London
March 18, 2019

We show that, as a consequence of a remarkable new result of
Attila P\'or on universal Tverberg partitions, any large-enough set
$P$ of points in $\Re^d$ has a $(d+2)$-sized subset whose Radon point
has half-space depth at least $c_d \cdot |P|$, where $c_d \in (0, 1)$
depends only on $d$. We then give an application of this result to
computing weak $\eps$-nets by random sampling. Joint work with Nabil