Almost Tight Upper Bound for Finding Fourier Coefficients of Bounded Pseudo- Boolean Functions

Abstract

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