The query complexity of estimating weighted averages

DOI10.1007/S00236-011-0145-8zbMATH Open1234.68132OpenAlexW2006202471MaRDI QIDQ766183FDOQ766183

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

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}\)

zbMATH Keywords

query complexityretrieval systems

Mathematics Subject Classification ID

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

Cites Work

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

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)