# Members Seminar

## Efficient non-convex polynomial optimization and the sum-of-squares hierarchy

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?

## Information complexity and applications

Over the past two decades, information theory has reemerged within computational complexity theory as a mathematical tool for obtaining unconditional lower bounds in a number of models, including streaming algorithms, data structures, and communication complexity. Many of these applications can be systematized and extended via the study of information complexity – which treats information revealed or transmitted as the resource to be conserved.