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

作者：Choi Sung Soon; Jung Kyomin^*; Kim Jeong Han

来源：Journal of Computer and System Sciences, 2011, 77(6): 1039-1053.

DOI：10.1016/j.jcss.2010.08.011

• Pseudo-Boolean function
• Fourier coefficients
• Graph finding
• Learning polynomials
• Linkage discovery
• Walsh analysis

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(m logn) function evaluations. The best known upper bound was O(lambda(n, m)m log n), where lambda(n, m) is between n(1/2) and n depending on m. Our bound improves the previous bound by a factor of Omega(n(1/2)). It is almost tight with respect to the lower bound Omega(mlogn/logm). 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.

• 出版日期2011-11