Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR08-080 | 3rd July 2008
Ido Ben-Eliezer, Rani Hod, Shachar Lovett

Random low degree polynomials are hard to approximate

Revisions: 1

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

ISSN 1433-8092 | Imprint