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?

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.

Moduli spaces of elliptic curves in toric varieties

Dhruv Ranganathan
March 16, 2017
Abstract: The moduli spaces of stable maps to toric varieties occur naturally in enumerative
geometry and mirror symmetry. While they have several pleasing properties, they are often
quite singular, reducible, and non-equidimensional. When the source curves have genus 0, the
situation is markedly improved by adding logarithmic structure to the moduli problem. This
produces irreducible and non-singular moduli spaces of rational curves in toric varieties, whose