Frequency computation and bounded queries

DOI10.1016/0304-3975(95)00149-2MaRDI QIDQ671360zbMATH OpenOpenAlexFDO

Authors Richard Beigel, William Gasarch, Efim Kinber

Publication date 27 February 1997

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

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

Recommendations

• scientific article; zbMATH DE number 1405575
• Some connections between bounded query classes and non-uniform complexity.
• The power of frequency computation
• Bounded queries in recursion theory
• scientific article; zbMATH DE number 1114037

Cites work

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

Cited in

(10)

• The space complexity of approximating the frequency moments
• Parallel learning of automatic classes of languages
• On the influence of technology on learning processes
• Resource Bounded Frequency Computations with Three Errors
• A proof of Beigel's cardinality conjecture
• Effective Search Problems
• scientific article; zbMATH DE number 6820309 (Why is no real title available?)
• The complexity of ODD_n^A
• The power of frequency computation
• Resource bounded frequency computations with three errors

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q671360)