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