the mirror of log Calabi-Yau surfaces. In particular, we prove the Frobenius structure conjecture
of Gross-Hacking-Keel in dimension two. *This is joint work with Sean Keel.
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.
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?