TR13-021 Authors: Kristoffer Arnsfelt Hansen, Vladimir Podolskii

Publication: 5th February 2013 18:01

Downloads: 5105

Keywords:

We study the complexity of computing Boolean functions on general

Boolean domains by polynomial threshold functions (PTFs). A typical

example of a general Boolean domain is $\{1,2\}^n$. We are mainly

interested in the length (the number of monomials) of PTFs, with

their degree and weight being of secondary interest. We show that

PTFs on general Boolean domains are tightly connected to depth two

threshold circuits. Our main results in regard to this connection are:

$\bullet$ PTFs of polynomial length and polynomial degree compute exactly

the functions computed by ${\rm THR} \circ {\rm MAJ}$ circuits.

$\bullet$ An exponential length lower bound for PTFs that holds regardless of degree, thereby extending known lower bounds for ${\rm THR} \circ {\rm MAJ}$ circuits.

$\bullet$ We generalize two-party unbounded error communication complexity to the multi-party number-on-the-forehead setting, and show that communication lower bounds for 3-player protocols would yield size lower bounds for ${\rm THR} \circ {\rm THR}$ circuits.

We obtain several other results about PTFs. These include

relationships between weight and degree of PTFs, and a degree lower

bound for PTFs of constant length. We also consider a variant of PTFs

over the max-plus algebra. We show that they are connected to PTFs

over general domains and to ${\rm AC}^0 \circ {\rm THR}$ circuits.