Majorizing estimators and the approximation of \#P-complete problems

DOI10.1145/301250.301320MaRDI QIDQ2819556zbMATH OpenOpenAlexFDO

Authors Leonard J. Schulman, Vijay V. Vazirani

Publication date 29 September 2016

Published in Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution
• An optimal (ϵ,δ)‐randomized approximation scheme for the mean of random variables with bounded relative variance
• How many needles are in a haystack, or how to solve \#P-complete counting problems fast
• scientific article; zbMATH DE number 1670534
• Approximating the permanent: A simple approach

Cited in

(2)

• A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution
• Optimal polynomial-time estimators: a Bayesian notion of approximation algorithm

This page was built for publication: Majorizing estimators and the approximation of \#P-complete problems

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