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.
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?
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.
from a new prospective. Applications to geometry will be considered.