Name
Title | ||
|---|---|---|
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(mlogn) function evaluations. The best known upper bound was O(@l(n,m)mlogn), where @l(n,m) is between n^1^2 and n depending on m. Our bound improves the previous bound by a factor of @W(n^1^2). It is almost tight with respect to the lower bound @W(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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.jcss.2010.08.011 | Journal of Computer and System Sciences |
Keywords | DocType | Volume |
k input bit,function evaluation,fourier coefficient,k-bounded function,degree k,k-bounded hypergraphs,constant k,k-bounded pseudo-boolean function,optimal algorithm,real-valued function,molecular biology,randomized algorithm,evolutionary computing,upper bound,lower bound | Conference | 77 |
Issue | ISSN | Citations |
6 | Journal of Computer and System Sciences | 5 |
PageRank | References | Authors |
0.50 | 25 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sung-Soon Choi | 1 | 112 | 11.03 |
| Kyomin Jung | 2 | 394 | 37.38 |
| Jeong Han Kim | 3 | 699 | 60.19 |