Optimal bounds for sign-representing the intersection of two halfspaces by polynomials |
| |
Authors: | Alexander A. Sherstov |
| |
Affiliation: | 1. Computer Science Department, UCLA, Los Angeles, California, 90095, USA
|
| |
Abstract: | The threshold degree of a function f: {0,1} n → {?1,+1} is the least degree of a real polynomial p with f(x) ≡ sgnp(x). We prove that the intersection of two halfspaces on {0,1} n has threshold degree Ω(n), which matches the trivial upper bound and solves an open problem due to Klivans (2002). The best previous lower bound was Ω({ie73-1}). Our result shows that the intersection of two halfspaces on {0,1} n only admits a trivial {ie73-2}-time learning algorithm based on sign-representation by polynomials, unlike the advances achieved in PAC learning DNF formulas and read-once Boolean formulas. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|