ECCC-Report TR13-021https://eccc.weizmann.ac.il/report/2013/021Comments and Revisions published for TR13-021en-usTue, 05 Feb 2013 18:01:32 +0200
Paper TR13-021
| Polynomial threshold functions and Boolean threshold circuits |
Kristoffer Arnsfelt Hansen,
Vladimir Podolskii
https://eccc.weizmann.ac.il/report/2013/021We 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.Tue, 05 Feb 2013 18:01:32 +0200https://eccc.weizmann.ac.il/report/2013/021