A New Necessary Condition for Threshold Function Identification

This article proposes a new necessary condition and the corresponding speedup strategies to the threshold function (TF) identification problem. The state-of-the-art to this identification problem could be very time-consuming when the function-under-identification is a non-TF with the unateness property. The proposed new necessary condition can be seamlessly integrated into this identification algorithm. As compared with the state-of-the-art, the improved identification algorithm with the proposed necessary condition can more effectively and efficiently detect non-TFs. Furthermore, according to the experimental results, the ratio of CPU time overhead in the process of checking the proposed necessary condition for identifying all the 8-input TF is only 0.1%.