The query complexity of estimating weighted averages

DOI10.1007/S00236-011-0145-8MaRDI QIDQ766183zbMATH OpenOpenAlexFDO

Authors Amit Chakrabarti, Venkatesan Guruswami, Andrew Wirth, Anthony Wirth

Publication date 23 March 2012

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-011-0145-8

zbMATH Keywords

query complexityretrieval systems

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Estimating Sum by Weighted Sampling
• scientific article; zbMATH DE number 1790452
• On a problem in quantum summation.
• Average case complexity of weighted approximation and integration over \(\mathbb R_{+}\)
• Complexity of weighted approximation over \(\mathbb{R}\)

Cites work

• An Optimal Algorithm for Monte Carlo Estimation
• Estimating Sum by Weighted Sampling
• Lower bounds for sampling algorithms for estimating the average
• Priority sampling for estimation of arbitrary subset sums
• Sampling algorithms: lower bounds and applications
• The DLT priority sampling is essentially optimal

Cited in

(1)

• Approximate Query Complexity

This page was built for publication: The query complexity of estimating weighted averages

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