Hansen, Kristoffer Arnsfelt3; Podolskii, Vladimir V.2
Krishnendu Chatterjee, Jirí Sgall
1 Department of Computer Science, Science and Technology, Aarhus University2 Steklov Mathematical Institute3 Department of Computer Science, Science and Technology, Aarhus University
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 12n . 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: PTFs of polynomial length and polynomial degree compute exactly the 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 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 AC0THR circuits.
Lecture Notes in Computer Science: 38th International Symposium, Mfcs 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, 2013, p. 516-527