Model counting meets \(F_0\) estimation

Randomized algorithms (68W20) Distributed algorithms (68W15) Online algorithms; streaming algorithms (68W27) Computational aspects of satisfiability (68R07)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
On computing minimal independent support and its applications to sampling and counting
Two improved range-efficient algorithms for \(F_0\) estimation
Probabilistic counting algorithms for data base applications
Monte-Carlo algorithms for the planar multiterminal network reliability problem
Random generation of combinatorial structures from a uniform distribution
Universal classes of hash functions
The space complexity of approximating the frequency moments
Probabilistic model counting with short XORs
When distributed computation is communication expensive
Uniform generation of NP-witnesses using an NP-oracle
Finding frequent items in data streams
Optimal tracking of distributed heavy hitters and quantiles
Not all FPRASs are equal: demystifying FPRASs for DNF-counting
CrystalBall: gazing in the black box of SAT solving
What can be sampled locally?
Tinted, detached, and lazy CNF-XOR solving and its applications to counting and sampling
Randomized algorithms for tracking distributed count, frequencies, and ranks
Zero-one frequency laws
Optimal Random Sampling from Distributed Streams Revisited
Algorithms for distributed functional monitoring
SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS
Optimal approximations of the frequency moments of data streams
Short XORs for Model Counting: From Theory to Practice
Functional Monitoring without Monotonicity
Monte-Carlo approximation algorithms for enumeration problems
The Complexity of Enumeration and Reliability Problems
An Optimal Algorithm for Monte Carlo Estimation
Sparse Hashing for Scalable Approximate Model Counting
Approximate Counting in SMT and Value Estimation for Probabilistic Programs
On Local Distributed Sampling and Counting
Range‐Efficient Counting of Distinct Elements in a Massive Data Stream
Continuous sampling from distributed streams
Tight bounds for distributed functional monitoring
Algorithms - ESA 2003
Provenance in databases: principles and applications