Polynomial threshold functions and Boolean threshold circuits

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

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.
Original languageEnglish
JournalElectronic Colloquium on Computational Complexity
Number of pages25
Publication statusPublished - 2013

    Research areas

  • circuit complexity, Communication complexity, lower bounds, Polynomial threshold functions, threshold circuits

See relations at Aarhus University Citationformats

ID: 52714724