Frequency computation and bounded queries

There have been several papers over the last ten years that consider the number of queries needed to compute a function as a measure of its complexity. The following function has been studied extensively in that light: F a A (x 1, …, x a ) = A(x 1)…A(x a ). We are interested in the complexity (in terms of the number of queries) of approximating F a A. Let b ⩽ a and let f be any function such that F a A (x 1, …, x a ) and f(x 1, …, x a ) agree on at least b bits. For a general set A we have matching upper and lower bounds on f that depend on coding theory. These are applied to get exact bounds for the case where A is semirecursive, A is superterse, and (assuming P ≠ NP) A = SAT. We obtain exact bounds when A is the halting problem using different methods.

Authors

• Richard Beigel
• William Gasarch
• Efim Kinber

Keywords

No keywords are indexed for this paper.