Almost every Boolean function has central threshold degree

Martin Anthony

The polynomial threshold degree (or threshold degree) of a Boolean function is the least degree of a real polynomial whose sign represents it. We prove that almost every Boolean fu…