Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-118 | 29th November 2009 21:37

Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

RSS-Feed




Revision #1
Authors: Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin
Accepted on: 29th November 2009 21:37
Downloads: 1155
Keywords: 


Abstract:

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.
Our second result relates to constructing pseudorandom generators fooling low-degree polynomial threshold functions. This problem has received attention recently, where Diakonikolas et al proved that $k$-wise independence suffices to fool linear threshold functions. We prove that any low-degree polynomial threshold function, which can be represented as a function of a small number of linear threshold functions, can also be fooled by $k$-wise independence. We view this as an important step towards fooling general polynomial threshold functions, and we discuss a plausible approach achieving this goal based on our techniques.
Our results combine tools from real approximation theory, hyper-contractive inequalities and probabilistic methods. In particular, we develop several new tools in approximation theory which may be of independent interest.


Paper:

TR09-118 | 18th November 2009 23:44

Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness





TR09-118
Authors: Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin
Publication: 19th November 2009 20:24
Downloads: 1590
Keywords: 


Abstract:

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.
Our second result relates to constructing pseudorandom generators fooling low-degree polynomial threshold functions. This problem has received attention recently, where Diakonikolas et al proved that $k$-wise independence suffices to fool linear threshold functions. We prove that any low-degree polynomial threshold function, which can be represented as a function of a small number of linear threshold functions, can also be fooled by $k$-wise independence. We view this as an important step towards fooling general polynomial threshold functions, and we discuss a plausible approach achieving this goal based on our techniques.
Our results combine tools from real approximation theory, hyper-contractive inequalities and probabilistic methods. In particular, we develop several new tools in approximation theory which may be of independent interest.



ISSN 1433-8092 | Imprint