On analysis of Boolean functions

Abstract

We present new methods for analyzing Boolean functions. The methods have characteristics that eliminate many shortcomings of current procedures for analyzing Boolean functions. They also provide some useful theoretical insights. Functional partitioning is developed, a method which reduces the complexity of Boolean function analysis problems by dividing it into smaller, independent problems. A new function representation scheme--the Indexed BDD (IBDD) is presented. The scheme is capable of modeling many notoriously difficult functions. An integer-valued transformation and related procedures are developed whereby many inquiries regarding Boolean functions can be probabilistically answered, with a small probability of error that can be further, exponentially, reduced. The method is significantly more efficient in both space and time than its deterministic counterparts.