Can we always approximate a semidefinite program with a linear program? Is it possible to approximately check nonnegativity of a multivariate polynomial by just a few pointwise evaluations? These questions fall into the general framework of approximating the cone of nonnegative polynomials with polyhedral cones.
In this talk, we will show inapproximability of the cone of nonnegative polynomials in the dense case (i.e. the case of all polynomials of a fixed degree). We will also show existence of a polyhedral approximation with polynomial number of facets in the sparse case (i.e. the case of a subspace of polynomials with small dimension). Our approximation result is an application of the recent solution of Kadison-Singer problem, and hence it is not constructive. Time permits, we will also discuss a randomized construction based on a different set of tools coming from computational geometry.