- Authors:
- Editor:
- Chatterjee, Krishnendu, Sgall, Jirí
- DOI:
- 10.1007/978-3-642-40313-2_46
- Abstract:
- 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.
- ISBN:
- 9783642403125, 9783642403132
- Type:
- Conference paper
- Language:
- English
- Published in:
- Lecture Notes in Computer Science: 38th International Symposium, Mfcs 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings, 2013, p. 516-527
- Keywords:
- circuit complexity; Communication complexity; lower bounds; Polynomial threshold functions; threshold circuits
- Main Research Area:
- Science/technology
- Publication Status:
- Published
- Series:
- Lecture Notes in Computer Science
- Review type:
- Peer Review
- Conference:
- International Symposium Mathematical Foundations of Computer Science, 2013
- Publisher:
- Springer-VS
- Submission year:
- 2013
- Scientific Level:
- Scientific
- ID:
- 250274106
Checking for on-site access...
