Video Lectures

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...

Combinatorial geometry is a field that studies combinatorial problems that involve some simple geometric objects/notions, such as: lines, points, distances, collinearity. While such problems are often easy to state, some of them are very difficult...

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...

In this talk, we first introduce the notion of a continuous cover of a manifold parametrised by any compact manifold endowed with a mass 1 volume-form. We prove that any such cover admits a partition of unity where the usual sum is replaced by...

We present a full $h$-principle (relative, parametric, $C^0$-close) for the simplification of singularities of Lagrangian and Legendrian fronts. More precisely, we prove that if there is no homotopy theoretic obstruction to simplifying the...

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...

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...