Lower bound on the complexity of finding polynomials of Boolean functions in the class of circuits with separated variables

摘要

We prove that, in the class of circuits with separated variables in the basis A_(L0) = {x ~? y}, the complexity of the problem to find all the coefficients of a polynomial of the Boolean function f(x_1,...,x_n) given a vector of N = 2~n function values is exactly equal n ? 2~(n-1). In the basis, the complexity of this problem is between 3n ? 2~(n-1) and 4n ? 2~(n-1).