Speaker: Shachar Lovett
The Weizman Institute of Science
Topic: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness
Abstract: We study the computational power of polynomial threshold functions (PTFs),
that is, threshold functions of real polynomials over the boolean
cube. We provide new results bounding the computational power of this model.
Our first result shows that low-degree PTFs cannot approximate any
function with many influential variables. We provide a couple of
examples where this technique yields tight approximation bounds.
Our second result relates to constructing pseudorandom generators fooling
low-degree PTFs, where we extend previous known cases where k-wise independence fools PTFs.
Both results are based on a new tool: a regularity theorem for PTFs.
This tool has also been developed in several other parallel works, where
it has been useful in other domains as well.
Based on joint work with Ido Ben-Eliezer and Ariel Yadin.