Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions

摘要

A k-bounded pseudo-Boolean function is a real-valued function on {0,1}n that can be expressed as a sum of functions depending on at most k input bits. The k-bounded functions play an important role in a number of areas including molecular biology, biophysics, and evolutionary computation. We consider the problem of finding the Fourier coefficients of k-bounded functions, or equivalently, finding the coefficients of multilinear polynomials on {−1,1}n of degree k or less. Given a k-bounded function f with m non-zero Fourier coefficients for constant k, we present a randomized algorithm to find the Fourier coefficients of f with high probability in O(mlogn) function evaluations. The best known upper bound was O(λ(n,m)mlogn), where λ(n,m) is between n12 and n depending on m. Our bound improves the previous bound by a factor of Ω(n12). It is almost tight with respect to the lower bound Ω(mlognlogm). In the process, we also consider the problem of finding k-bounded hypergraphs with a certain type of queries under an oracle with one-sided error. The problem is of self interest and we give an optimal algorithm for the problem.