We study the complexity of computing Boolean functions on generalBoolean domains by polynomial threshold functions (PTFs). A typicalexample of a general Boolean domain is 12n . We are mainlyinterested in the length (the number of monomials) of PTFs, withtheir degree and weight being of secondary interest. We show thatPTFs on general Boolean domains are tightly connected to depth twothreshold circuits. Our main results in regard to this connection are:

PTFs of polynomial length and polynomial degree compute exactlythe functions computed by THRMAJ circuits. An exponential length lower bound for PTFs that holds regardless of degree, thereby extending known lower bounds for THRMAJ circuits. 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 THRTHR circuits.

We obtain several other results about PTFs. These includerelationships between weight and degree of PTFs, and a degree lowerbound for PTFs of constant length. We also consider a variant of PTFsover the max-plus algebra. We show that they are connected to PTFsover general domains and to AC0THR circuits.