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.

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.

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?

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.

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.

Equivariant geometry and Calabi-Yau manifolds

Daniel Halpern-Leistner
Columbia University
March 16, 2017
Abstract: Mirror symmetry has led to deep conjectures regarding the geometry of Calabi-Yau
manifolds. One of the most intriguing of these conjectures states that various geometric
invariants, some classical and some more homological in nature, agree for any two Calabi-Yau
manifolds which are birationally equivalent to one another. I will discuss how new methods in
equivariant geometry have shed light on this conjecture over the past few years, ultimately