New degree bounds for polynomial threshold functions

83 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “The lower bound for the classification accuracy using low-degree polynomials has been widely studied as the (approximate) threshold degree of a function or the sign-rank of a matrix [18, 21, 25, 41, 75, 81].”
Agnostically learning halfspaces (2005, result): “For example, results of O’Donnell and Servedio [32] show that any Boolean function f : {−1, 1}n → {−1, 1} computed by a Boolean formula of linear size and constant depth is 2-approximated in the L∞ norm by a polynomial of degree Õ( √ n) · poly log 12 .”