Frequency computation and bounded queries

DOI10.1016/0304-3975(95)00149-2zbMath0874.03048OpenAlexW3129458497MaRDI QIDQ671360

Richard Beigel, E. B. Kinber, William I. Gasarch

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00149-2

zbMATH Keywords

number of queries needed to compute a function as a measure of its complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (6)

On the Influence of Technology on Learning Processes ⋮ Resource bounded frequency computations with three errors ⋮ Parallel learning of automatic classes of languages ⋮ A proof of Beigel's cardinality conjecture ⋮ Resource Bounded Frequency Computations with Three Errors ⋮ The complexity of ODD_n^A

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Good coverings of Hamming spaces with spheres
• The complexity of optimization problems
• Quasi-linear truth-table reductions to \(p\)-selective sets
• Terse, superterse, and verbose sets
• Enumerative counting is hard
• Theory of Formal Systems. (AM-47)
• Covering radius---Survey and recent results
• Further results on the covering radius of codes
• Improved sphere bounds on the covering radius of codes
• A proof of Beigel's cardinality conjecture
• Frequency computations and the cardinality theorem
• Recursively enumerable sets and degrees
• Effective Search Problems
• Semirecursive Sets and Positive Reducibility
• Modified bounds for covering codes

This page was built for publication: Frequency computation and bounded queries