The problem of recognizing nonnegativity of a multivariate polynomial has a celebrated history, tracing back to Hilbert’s 17th problem. In recent years, there has been much renewed interest in the topic because of a multitude of applications in applied and computational mathematics and the observation that one can optimize over an interesting subset of nonnegative polynomials using “sum of squares (SOS) optimization”. In this talk, we give a brief overview of the developments in this field and then focus on two recent results. In part (i), we show that the joint spectral radius of a finite set of matrices is less than one if and only if there exists a polynomial norm (i.e., a norm which is the d-th root of a degree-d homogeneous polynomial) that decreases under the application of all matrices. Moreover, the convexity of this polynomial and its decrease inequalities can all be verified using SOS certificates. This result generalizes the classical theorem in linear algebra that the spectral radius of a matrix is less than one if and only if there exists a decreasing quadratic norm. In part (ii), we introduce new algebraic sufficient conditions for polynomial nonnegativity that are very similar to the SOS condition but instead of semidefinite programs lead to linear or second order cone programs when implemented numerically. These are what we call ``DSOS and SDSOS programs.’’ We show that these relaxations are orders of magnitude more scalable than the SOS relaxation while enjoying many of the same asymptotic theoretical guarantees.  Joint work (in different subsets) with Etienne de Klerk, Georgina Hall, Raphael Jungers, and Anirudha Majumdar.