Approximate counting with m counters: a probabilistic analysis

MaRDI QIDQ307930zbMATH OpenFDO

Authors Guy Louchard, Helmut Prodinger

Publication date 5 September 2016

Published in Journal of Algebra Combinatorics Discrete Structures and Applications (Search for Journal in Brave)

zbMATH Keywords

momentsapproximate countingcomplex analysisconstant and fluctuating componentsproduct of Fourier series

Mathematics Subject Classification ID

Combinatorial probability (60C05) Asymptotic enumeration (05A16)

Recommendations

• Approximate counting with m counters: A detailed analysis
• Approximate counting: a detailed analysis
• Approximate counting:a martingale approach
• scientific article; zbMATH DE number 4162272
• How to count quickly and accurately: a unified analysis of probabilistic counting and other related problems

Cites work

• scientific article; zbMATH DE number 3176450 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (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 via the Poisson-Laplace-Mellin method
• Approximate counting with \(m\) counters: A detailed analysis
• 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 Revisited
• Exact and asymptotic distributions in digital and binary search trees
• Generalized approximate counting revisited
• Hypothetical analyses: Approximate counting in the style of Knuth, path length in the style of Flajolet
• Periodic oscillations in the analysis of algorithms and their cancellations

Cited in

(12)

• Generalized approximate counting revisited
• Approximate Counting with Deterministic Guarantees for Affinity Computation
• Approximate shared-memory counting despite a strong adversary
• An analysis of Monte Carlo algorithms for counting problems
• scientific article; zbMATH DE number 1670534 (Why is no real title available?)
• Approximate counting with \(m\) counters: A detailed analysis
• Approximate counting: a detailed analysis
• Approximate Counting in SMT and Value Estimation for Probabilistic Programs
• Advancing in the presence of a demon
• scientific article; zbMATH DE number 740353 (Why is no real title available?)
• scientific article; zbMATH DE number 4162272 (Why is no real title available?)
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle

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

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