Skip to main content
Article
Frequency Computation and Bounded Queries
Computer Science & Information Technology Faculty Publications
  • Richard Beigel, University of Maryland at College Park
  • William I. Gasarch
  • Efim Kinber, Sacred Heart University
Document Type
Article
Publication Date
8-30-1996
Disciplines
Abstract

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: Ft(xl,. . .,x0) = ,4(x,). .A(x,). We are interested in the complexity (in terms of the number of queries) of approximating Fi. Let b

Comments

At the time of publication Efim Kinber was affiliated with University of Delaware.

DOI
10.1016/0304-3975(95)00149-2
Citation Information
Beigel, R., Gasarch, W., & Kinber, E. (1996). Frequency computation and bounded queries. Theoretical Computer Science, 163(1-2), 177-192. doi:10.1016/0304-3975(95)00149-2