School of Mathematics

Applications of monotone constraint satisfaction

Robert Robere
University of Toronto
March 28, 2017

Recently, a certain "monotone" version of the constraint satisfaction problem has proved an extremely useful tool for attacking problems in circuit, communication, and proof complexity theory. In this talk we discuss this version of the constraint satisfaction problem and touch on its connection to fundamental lower-bounds problems in these areas. We also consider a recent and interesting application: the first exponential lower bounds on the length of cutting planes refutations of random CNF formulas.

Applications of monotone constraint satisfaction

Robert Robere
University of Toronto
March 27, 2017

Recently, a certain "monotone" version of the constraint satisfaction problem has proved an extremely useful tool for attacking problems in circuit, communication, and proof complexity theory. In this talk we discuss this version of the constraint satisfaction problem and touch on its connection to fundamental lower-bounds problems in these areas. We also consider a recent and interesting application: the first exponential lower bounds on the length of cutting planes refutations of random CNF formulas.

Efficient non-convex polynomial optimization and the sum-of-squares hierarchy

David Steurer
Cornell University; Member, School of Mathematics
March 20, 2017

The sum-of-squares (SOS) hierarchy (due to Shor'85, Parrilo'00, and Lasserre'00) is a widely-studied meta-algorithm for (non-convex) polynomial optimization that has its roots in Hilbert's 17th problem about non-negative polynomials.

SOS plays an increasingly important role in theoretical computer science because it affords a new and unifying perspective on the field's most basic question:

What's the best possible polynomial-time algorithm for a given computational problem?

Approximate counting and the Lovasz local lemma

Ankur Moitra
Massachusetts Institute of Technology
March 20, 2017

We introduce a new approach for approximately counting in bounded degree systems with higher-order constraints. Our main result is an algorithm to approximately count the number of solutions to a CNF formula where the degree is exponential in the number of variables per clause. Moreover our algorithm extends straightforwardly to approximate sampling, which shows that under Lovasz Local Lemma-like conditions, it is possible to generate a satisfying assignment approximately uniformly at random.

Real Lagrangians in toric degenerations

Bernd Siebert
University of Hamburg
March 17, 2017
Abstract: Real loci of the canonical toric degenerations constructed from integral affine
manifolds with singularities in the joint work with Mark Gross, provide an ample source of
examples of Lagrangians that conjecturally are amenable to algebraic-geometric versions of
Floer theory. In the talk I will discuss joint work with Hülya Argüz on how the topology of the real
locus can be understood by means of the affine geometry and by Kato-Nakayama spaces
associated to log spaces.

Calabi-Yau geometry and quantum B-model

Si Li
Tsinghua University
March 17, 2017
We discuss the Kadaira-Spencer gauge theory (or BCOV theory) on Calabi-Yau geometry. We explain Givental's loop space formalism at cochain level which leads to a degenerate BV theory on Calabi-Yau manifolds. Homotopic BV quantization together with a splitting of the Hodge filtration lead to higher genus B-model. We illustrate such quantization and higher genus mirror symmetry by the elliptic curve example.