Approximate Query Complexity

DOI10.1145/2003685.2003688zbMath1322.68063OpenAlexW1987693787MaRDI QIDQ2947556

Clifford D. 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

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