• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Model Counting meets F0 Estimation.
A. Pavan ⓡ N.V. Vinodchandran ⓡ Arnab Bhattacharya ⓡ Kuldeep S. Meel.
In Proceedings of ACM Symposium on Principles of Database Systems (PODS), June 2021.
CACM Research Highlight and 2021 ACM SIGMOD Research Highlight
Constraint satisfaction problems (CSP's) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSP's and computation of zeroth frequency moments $(F_0)$ for data streams. Our investigations lead us to observe striking similarity in the core techniques employed in the algorithmic frameworks that have evolved separately for model counting and $F_0$ computation. We design a recipe for translation of algorithms developed for $F_0$ estimation to that of model counting, resulting in new algorithms for model counting. We then observe that algorithms in the context of distributed streaming can be transformed to distributed algorithms for model counting. We next turn our attention to viewing streaming from the lens of counting and show that framing $F_0$ estimation as a special case of #DNF counting allows us to obtain a general recipe for a rich class of streaming problems, which had been subjected to case-specific analysis in prior works. In particular, our view yields a state-of-the art algorithm for multidimensional range efficient $F_0$ estimation with a simpler analysis.
@inproceedings{PVBM21,
title={Model Counting meets F0 Estimation},
author={
Pavan, A. and Vinodchandran, N.V. and Bhattacharya, Arnab and Meel, Kuldeep
S.
},
booktitle=PODS,
nameorder={random},
bib2html_rescat={Counting, Data Streams},
bib2html_dl_pdf={../Papers/pods21-pvbm.pdf},
bib2html_pubtype={Refereed Conference,Award Winner},
year={2021},
month=jun,
note={CACM Research Highlight and 2021 ACM SIGMOD Research Highlight},
abstract={
Constraint satisfaction problems (CSP's) and data stream models are two
powerful abstractions to capture a wide variety of problems arising in
different domains of computer science. Developments in the two communities
have mostly occurred independently and with little interaction between them.
In this work, we seek to investigate whether bridging the seeming
communication gap between the two communities may pave the way to richer
fundamental insights. To this end, we focus on two foundational problems:
model counting for CSP's and computation of zeroth frequency moments $(F_0)$
for data streams.
Our investigations lead us to observe striking similarity in the core
techniques employed in the algorithmic frameworks that have evolved
separately for model counting and $F_0$ computation. We design a recipe for
translation of algorithms developed for $F_0$ estimation to that of model
counting, resulting in new
algorithms for model counting. We then observe that algorithms in the
context of distributed streaming can be transformed to distributed
algorithms for model counting. We next turn our attention to viewing
streaming from the lens of counting and show that framing $F_0$ estimation
as a special case of \#DNF counting allows us to obtain a general recipe for
a rich class of streaming problems, which had been subjected to
case-specific analysis in prior works. In particular, our view yields a
state-of-the art algorithm for multidimensional range efficient $F_0$
estimation with a simpler analysis.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21