Approximate counting with m counters: A detailed analysis

DOI10.1016/J.TCS.2012.03.016MaRDI QIDQ441872zbMATH OpenOpenAlexFDO

Authors Helmut Prodinger

Publication date 8 August 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.03.016

zbMATH Keywords

approximate countingRice's methodcancellations\(q\)-analysis

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) (q)-calculus and related topics (05A30)

Recommendations

• Approximate counting with \(m\) counters: a probabilistic analysis
• Approximate counting: a detailed analysis
• scientific article; zbMATH DE number 1670534
• On the parameterized complexity of approximate counting
• The relative complexity of approximate counting problems
• Generalized approximate counting revisited
• scientific article; zbMATH DE number 7701429
• scientific article; zbMATH DE number 549850
• Approximate counting and NP search problems
• scientific article; zbMATH DE number 1979521

Cites work

• scientific article; zbMATH DE number 4035166 (Why is no real title available?)
• scientific article; zbMATH DE number 3577263 (Why is no real title available?)
• scientific article; zbMATH DE number 740353 (Why is no real title available?)
• Approximate counting : an alternative approach
• Approximate counting: a detailed analysis
• Asymptotic variance of random symmetric digital search trees
• Asymptotics of the moments of extreme-value related distribution functions
• Digital Search Trees Again Revisited: The Internal Path Length Perspective
• Generalized approximate counting revisited
• Hypothetical analyses: Approximate counting in the style of Knuth, path length in the style of Flajolet
• Mellin transforms and asymptotics: Finite differences and Rice's integrals
• Periodic oscillations in the analysis of algorithms and their cancellations

Cited in

(11)

• Efficient deterministic approximate counting for low-degree polynomial threshold functions
• Generalized approximate counting revisited
• Approximate Counting with Deterministic Guarantees for Affinity Computation
• Approximate shared-memory counting despite a strong adversary
• scientific article; zbMATH DE number 1670534 (Why is no real title available?)
• Approximate counting with \(m\) counters: a probabilistic analysis
• Approximate counting: a detailed analysis
• Approximate counting:a martingale approach
• scientific article; zbMATH DE number 740353 (Why is no real title available?)
• Approximate counting via the Poisson-Laplace-Mellin method
• Approximate counting with a floating-point counter

This page was built for publication: Approximate counting with \(m\) counters: A detailed analysis

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