On the query complexity of sets

DOI10.1007/3-540-61550-4_149MaRDI QIDQ4375806zbMATH OpenFDO

Authors Richard Beigel, Timothy H. McNicholl, William Gasarch, Martin Kummer, Georgia A. Martin, Frank Stephan

Publication date 10 May 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61550-4_149

zbMATH Keywords

query complexitytt-degree

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Query complexity of membership comparable sets.
• On the complexity of set-based analysis
• scientific article; zbMATH DE number 437544
• Lower bounds for set intersection queries
• On the computational complexity of defining sets
• Computational complexity of queries based on itemsets
• Bounded queries to arbitrary sets
• A Theory of Local Set Queries
• On the Complexity of Hard-Core Set Constructions
• On the Structure of Bounded Queries to Arbitrary NP Sets

Cited in

(12)

• Query complexity of membership comparable sets.
• Terse, superterse, and verbose sets
• Lower bounds for set intersection queries
• The complexity of irredundant sets parameterized by size
• scientific article; zbMATH DE number 1678392 (Why is no real title available?)
• The performance of difference coding for sets and relational tables
• A proof of Beigel's cardinality conjecture
• The complexity of ODD_n^A
• A Theory of Local Set Queries
• On different topologies for set-indexing collections
• Aspects of complexity of probabilistic learning under monotonicity constraints
• Frequency computation and bounded queries

This page was built for publication: On the query complexity of sets

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