Model counting meets F₀ estimation

DOI10.1145/3603496MaRDI QIDQ6535267zbMATH OpenFDO

Authors Aduri Pavan, N. V. Vinodchandran, Arnab Bhattacharyya, Kuldeep S. Meel

Publication date 29 November 2023

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

Full work available at URL https://doi.org/10.1145/3603496

zbMATH Keywords

\(F_0\)-computationDNF countingmodel countingstreaming algorithms

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

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

Cited in

(2)

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

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

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