Reed-Muller forms for incompletely specified functions via sparse polynomial interpolation

In this paper we investigate the possibility of exploiting incompletely specified functions for the purpose of minimizing Reed-Muller (RM) forms. All the previous work in this area has been based on exhaustive search for the optimal solution, or on some approximations to it. Here we show that an alternative approach can bring better results: the definition of the MVL RM transforms as a polynomial interpolation over a finite field allows us to use the methods for sparse polynomial interpolation to find good approximations to the optimal solution. Starting from the general MVL case, we derive a computationally efficient algorithm for computing RM transforms for binary functions as well. We show empirically that the new method performs better than all known methods