One of the most common ways to represent a Boolean function is as the sign
of a real polynomial. If a Boolean function can be sign-represented by a polynomial
of degree d, it is called a degree-d Polynomial Threshold Function (PTF).
PTFs have played an important role in computer science for decades, at least since
the 1968 work of Minsky and Papert on perceptrons.

In this talk, I will present a "regularity lemma" for low-degree polynomial threshold
functions (PTFs) over the Boolean hypercube. Roughly speaking, this result shows that
every degree-d PTF can be decomposed into a constant number of subfunctions such that
almost all of the subfunctions are close to being "regular" PTFs. Hence, the result
provides a way to reduce questions about arbitrary PTFs to ones about "regular" PTFs.


This lemma has played an important role in a range of recent results for PTFs.
These include the discovery of various structural properties of PTFs -- which in turn
lead to efficient learning algorithms -- and the construction of explicit pseudorandom
generators. The talk will discuss these applications and emphasize the connections
between them.


(Based on joint works with R. Servedio, Li-Yang Tan and Andrew Wan.)