New degree bounds for polynomial threshold functions |
| |
Authors: | Ryan O’Donnell Rocco A Servedio |
| |
Institution: | (1) Department of Computer Sciences, The University of Texas at Austin, Austin, TX 78712, USA |
| |
Abstract: | A real multivariate polynomial p(x
1, …, x
n
) is said to sign-represent a Boolean function f: {0,1}
n
→{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1}
n
. We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds
for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds
since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|