Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

Understand

We study the computational power of polynomial threshold functions, that is, threshold functions of real polynomials over the boolean cube.

• We provide two new results bounding the computational power of this model.
• Our first result shows that low-degree polynomial threshold functions cannot approximate any function with many influential variables.
• We provide a couple of examples where this technique yields tight approximation bounds.