Model counting meets \(F_0\) estimation

DOI10.1145/3603496zbMATH Open1541.6845MaRDI QIDQ6535267

A. Pavan, Arnab Bhattacharyya, Kuldeep S. Meel, N. V. Vinodchandran

Publication date: 29 November 2023

Published in: ACM Transactions on Database Systems (Search for Journal in Brave)

zbMATH Keywords

streaming algorithmsmodel counting\(F_0\)-computationDNF counting

Mathematics Subject Classification ID

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

Related Items (2)

New width parameters for model counting ⋮ Statistical model and BPS D4-D2-D0 counting

Recommendations

• Unnamed Item 👍 👎
• On maximum likelihood estimation for count data models 👍 👎
• Estimation in some counting process models with multiplicative structure 👍 👎
• Fast and flexible probabilistic model counting 👍 👎
• A new probabilistic algorithm for approximate model counting 👍 👎
• On probabilistic inference by weighted model counting 👍 👎
• Using Model Counting to Find Optimal Distinguishing Tests 👍 👎
• Theory and Applications of Satisfiability Testing 👍 👎

This page was built for publication: Model counting meets \(F_0\) estimation