Noah Fleming, UCSD CSE postdoctoral fellow
Title: Semi-algebraic proofs and algorithms
Abstract: Many combination optimization problems can naturally phrased as a optimizing a linear objective function over a polytope -- a linear program. Unfortunately, for many problems of interest, these natural polytopes have an exponential-sized description, and thus are not efficient solvable by current methods. One way to circumvent this is to find a simpler polytope in a higher dimension which admits a linear projection back down to the original polytope; thus, one can optimize over the simpler polytope instead. This higher dimensional polytope is known as an Extended Formulation of the original polytope. The study complexity of extended formulation, initiated by Yannakakis [Y91], is a burgeoning area of research in both complexity theory and combinatorial optimization.
In this talk we will explore extended formulations as a computational model for boolean functions, as formalized by Hrubes [H20], known as separation complexity. Given a function f:{0,1}^n -> {0,1}, the separation complexity of f in the smallest (extended formulation of a) polytope which contains the 1's of f and does not contain the 0's. It's not difficult to see that this model captures boolean circuits, and its monotone variant captures monotone circuits.
We will investigate a query analogue of monotone separation complexity, known as conical junta degree and show a tight relationship between it and the Sherali-Adams proof system, allowing us to give a simplified definition of Sherali-Adams. Using this, we will show that small Sherali-Adams proofs imply small extended formulations, via an interpolation theorem. Finally, by proving lower bounds on conical junta degree, we show that monotone separation complexity is a strictly stronger model of computation than monotone circuits.
This is based on joint work with Mika Goos, Toniann Pitassi, and Robert Rober