Universal Functions for Classes of Bilinear and Polylinear Boolean Functions

Resumo

The following problem is considered: specify a Boolean function of n variables such that every bilinear (polylinear) function is reduced, on a certain number of tuples of the specified function, to a unique bilinear (polylinear) function that is identical with the specified function on these tuples. We show that this is feasible for bilinear functions and for polylinear functions with a fixed number of parentheses k, starting with some n , and we can restrict the analysis to a sequence of functions with definition domain of cardinality O(n).