Computer Science – Computational Complexity
Scientific paper
2009-10-22
In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010)
Computer Science
Computational Complexity
A few minor simplifications added
Scientific paper
The threshold degree of a function f:{0,1}^n->{-1,+1} is the least degree of a real polynomial p with f(x)=sgn p(x). We prove that the intersection of two halfspaces on {0,1}^n has threshold degree Omega(n), which matches the trivial upper bound and completely answers a question due to Klivans (2002). The best previous lower bound was Omega(sqrt n). Our result shows that the intersection of two halfspaces on {0,1}^n only admits a trivial 2^{Theta(n)}-time learning algorithm based on sign-representation by polynomials, unlike the advances achieved in PAC learning DNF formulas and read-once Boolean formulas. The proof introduces a new technique of independent interest, based on Fourier analysis and matrix theory.
No associations
LandOfFree
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Optimal bounds for sign-representing the intersection of two halfspaces by polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal bounds for sign-representing the intersection of two halfspaces by polynomials will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-690006