Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ariel Yadin:

TR09-118 | 18th November 2009
Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin

Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint