All reports by Author Ido Ben-Eliezer:

__
TR09-118
| 18th November 2009
__

Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin#### Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

Revisions: 1

__
TR08-080
| 3rd July 2008
__

Ido Ben-Eliezer, Rani Hod, Shachar Lovett#### Random low degree polynomials are hard to approximate

Revisions: 1

Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin

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

Ido Ben-Eliezer, Rani Hod, Shachar Lovett

We study the problem of how well a typical multivariate polynomial can be approximated by lower degree polynomials over $\F$.

We prove that, with very high probability, a random degree $d$ polynomial has only an exponentially small correlation with all polynomials of degree $d-1$, for all degrees $d$ up to ...
more >>>