Revision #1 Authors: Alexander A. Sherstov

Accepted on: 30th December 2009 00:35

Downloads: 1299

Keywords:

The threshold degree of a Boolean function

$f\colon\{0,1\}^n\to\{-1,+1\}$ is the least degree of a real

polynomial $p$ such that $f(x)\equiv\mathrm{sgn}\; p(x).$ We

construct two halfspaces on $\{0,1\}^n$ whose intersection has

threshold degree $\Theta(\sqrt n),$ an exponential improvement on

previous lower bounds. This solves an open problem due to Klivans

(2002) and rules out the use of perceptron-based techniques for

PAC learning the intersection of two halfspaces, a central

unresolved challenge in computational learning. We also prove

that the intersection of two majority functions has threshold

degree $\Omega(\log n),$ which is tight and settles a conjecture

of O'Donnell and Servedio (2003).

Our proof consists of two parts. First, we show that

for any nonconstant Boolean functions $f$ and $g,$ the

intersection $f(x)\wedge g(y)$ has threshold degree

$O(d)$ if and only if $\|f-F\|_\infty + \|g-G\|_\infty

< 1$ for some rational functions $F,$ $G$ of degree

$O(d).$ Second, we settle the least degree required for

approximating a halfspace and a majority function to

any given accuracy by rational functions.

Our technique further allows us to make progress on

Aaronson's challenge (2008) and contribute direct sum

theorems for polynomial representations of composed Boolean functions

of the form $F(f_1,...,f_n).$ In particular, we give an improved

lower bound on the approximate degree of the AND-OR tree.

1) Bibliographic information added in Section 3.1 on

complementary upper bounds for approximating composed

Boolean functions, due to Buhrman, Newman, Rohrig, and

de Wolf (2007).

2) Typos corrected in the abstract.

TR09-098 Authors: Alexander A. Sherstov

Publication: 10th October 2009 17:27

Downloads: 1581

Keywords:

The threshold degree of a Boolean function

$f\colon\{0,1\}\to\{-1,+1\}$ is the least degree of a real

polynomial $p$ such $f(x)\equiv\mathrm{sgn}\; p(x).$ We

construct two halfspaces on $\{0,1\}^n$ whose intersection has

threshold degree $\Theta(\sqrt n),$ an exponential improvement on

previous lower bounds. This solves an open problem due to Klivans

(2002) and rules out the use of perceptron-based techniques for

PAC learning the intersection of two halfspaces, a central

unresolved challenge in computational learning. We also prove

that the intersection of two majority functions has threshold

degree $\Omega(\log n),$ which is tight and settles a conjecture

of O'Donnell and Servedio (2003).

Our proof consists of two parts. First, we show that for any

Boolean functions $f$ and $g,$ the intersection $f(x)\wedge g(y)$

has threshold degree $O(d)$ if and only if $\|f-F\|_\infty +

\|g-G\|_\infty < 1$ for some rational functions $F,$ $G$ of

degree $O(d).$ Second, we settle the least degree

required for approximating a halfspace and a majority function to

any given accuracy by rational functions.

Our technique further allows us to make progress on

Aaronson's challenge (2008) and contribute strong direct product

theorems for polynomial representations of composed Boolean functions

of the form $F(f_1,...,f_n).$ In particular, we give an improved

lower bound on the approximate degree of the AND-OR tree.