Approximate Query Complexity

DOI10.1145/2003685.2003688MaRDI QIDQ2947556zbMATH OpenOpenAlexFDO

Authors Clifford Smyth

Publication date 24 September 2015

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2003685.2003688

zbMATH Keywords

communication complexitydecision tree complexitycertificate complexityapproximate certificate complexityapproximate decision tree complexity

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Approximation algorithms (68W25)

Recommendations

• Query complexity in expectation
• From query complexity to computational complexity
• On the complexity of database queries
• The complexity of higher-order queries
• Space Complexity vs. Query Complexity
• Space complexity vs. query complexity
• The complexity of evaluating relational queries
• Computational complexity of queries based on itemsets
• Inherent complexity of recursive queries
• The query complexity of estimating weighted averages

This page was built for publication: Approximate Query Complexity

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