Polynomial threshold functions and Boolean threshold circuits

Information and Computation. 2015. Vol. 240. P. 56–73.

Hansen K. A., Podolskii V. V.

We initiate a comprehensive study of the complexity of computing Boolean functions by polynomial threshold functions (PTFs) on general Boolean domains (as opposed to domains such as $\zon$ or $\mon$ that enforce multilinearity). A typical example of such a general Boolean domain, for the purpose of our results, 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. First we motivate the study of PTFs over the $\{1,2\}^n$ domain by showing their close relation to depth two threshold circuits. In particular we show that PTFs of polynomial length and polynomial degree compute exactly the functions computed by polynomial size $\ensuremath{{\rm \sf THR}} \circ \ensuremath{{\rm \sf MAJ}}$ circuits. We note that known lower bounds for $\ensuremath{{\rm \sf THR}} \circ \ensuremath{{\rm \sf MAJ}}$ circuits extends to the likely strictly stronger model of PTFs (with no degree restriction). We also show that a ``max-plus'' version of PTFs are related to $\mathsf{AC}^0 \circ \ensuremath{{\rm \sf THR}}$ circuits. We exploit this connection to gain a better understanding of threshold circuits. In particular, we show that (super-logarithmic) lower bounds for 3-player randomized communication protocols with unbounded error would yield (super-polynomial) size lower bounds for $\ensuremath{{\rm \sf THR}} \circ \ensuremath{{\rm \sf THR}}$ circuits. Finally, having thus motivated the model, we initiate structural studies of PTFs. These include relationships between weight and degree of PTFs, and a degree lower bound for PTFs of constant length.

Keywords: communication complexity, Polynomial threshold functions, Threshold circuits