Polynomial threshold functions and Boolean threshold circuits

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 { 0, 1 } n or { − 1, 1 } n 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 THR ∘ MAJ circuits. We note that known lower bounds for THR ∘ MAJ circuits extend to the likely strictly stronger model of PTFs (with no degree restriction). We also show that a “max-plus” version of PTFs is related to AC 0 ∘ 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 THR ∘ 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.

Authors

• Kristoffer Arnsfelt Hansen
• Vladimir V. Podolskii

Keywords

• Polynomial threshold functions
• Threshold circuits
• Communication complexity