Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-021 | 5th February 2013 17:24

Polynomial threshold functions and Boolean threshold circuits



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.

ISSN 1433-8092 | Imprint