Approximate set union via approximate randomization

DOI10.1016/J.TCS.2021.09.016MaRDI QIDQ5919116zbMATH OpenOpenAlexFDO

Authors Bin Fu, Pengfei Gu, Yuming Zhao

Publication date 21 October 2021

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

Full work available at URL https://arxiv.org/abs/1802.06204

zbMATH Keywords

\#P-hardlattice pointsrandomized approximationroundssublinear time

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• An analysis of Monte Carlo algorithms for counting problems
• Partial sublinear time approximation and inapproximation for maximum coverage
• scientific article; zbMATH DE number 1067837
• Approximate inclusion-exclusion
• Randomized approximation of bounded multicovering problems

Cites work

• A Short Proof of Jacobi's Formula for the Number of Representations of an Integer as a Sum of Four Squares
• Approximating the volume of unions and intersections of high-dimensional geometric objects
• Counting Lattice Points in The Sphere
• Exponential Sums and Lattice Points II
• scientific article; zbMATH DE number 5763313 (Why is no real title available?)
• scientific article; zbMATH DE number 3679919 (Why is no real title available?)
• scientific article; zbMATH DE number 1305358 (Why is no real title available?)
• scientific article; zbMATH DE number 2019620 (Why is no real title available?)
• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• scientific article; zbMATH DE number 3235403 (Why is no real title available?)
• scientific article; zbMATH DE number 3260895 (Why is no real title available?)
• scientific article; zbMATH DE number 3285390 (Why is no real title available?)
• scientific article; zbMATH DE number 3188619 (Why is no real title available?)
• Lattice points in ellipsoids
• Lattice points in high-dimensional spheres
• Monte-Carlo approximation algorithms for enumeration problems
• New omega theorems for two classical lattice point problems
• On a lattice point problem of L. Moser. I
• On lattice-points in a random sphere
• On the number of integer points in the displaced circles
• On the number of lattice points in a small sphere and a recursive lattice decoding algorithm
• Partial sublinear time approximation and inapproximation for maximum coverage
• Probabilistic counting algorithms for data base applications
• Probability Inequalities for Sums of Bounded Random Variables
• The complexity of computing the permanent
• The complexity of theorem-proving procedures
• The space complexity of approximating the frequency moments

Cited in

(2)

• Probabilistic Analysis of Disjoint Set Union Algorithms
• Approximate set union via approximate randomization

This page was built for publication: Approximate set union via approximate randomization

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