Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On Hashing-Based Approaches to Approximate DNF-Counting   Propositional model counting is a fundamental problem in artificial
intelligence with a wide variety of applications, such as probabilistic
inference, decision making under uncertainty, and probabilistic databases.
Consequently, the problem is of theoretical as well as practical interest. When
the constraints are expressed as DNF formulas, Monte Carlo-based techniques
have been shown to provide a fully polynomial randomized approximation scheme
(FPRAS). For CNF constraints, hashing-based approximation techniques have been
demonstrated to be highly successful. Furthermore, it was shown that
hashing-based techniques also yield an FPRAS for DNF counting without usage of
Monte Carlo sampling. Our analysis, however, shows that the proposed
hashing-based approach to DNF counting provides poor time complexity compared
to the Monte Carlo-based DNF counting techniques. Given the success of
hashing-based techniques for CNF constraints, it is natural to ask: Can
hashing-based techniques provide an efficient FPRAS for DNF counting? In this
paper, we provide a positive answer to this question. To this end, we introduce
two novel algorithmic techniques: \emph{Symbolic Hashing} and \emph{Stochastic
Cell Counting}, along with a new hash family of \emph{Row-Echelon hash
functions}. These innovations allow us to design a hashing-based FPRAS for DNF
counting of similar complexity (up to polylog factors) as that of prior works.
Furthermore, we expect these techniques to have potential applications beyond
DNF counting.

20
The categories of this paper are: acc-phys
37
The categories of this paper are: supr-con
36
The categories of this paper are: cmp-lg
23
The categories of this paper are: solv-int
0
The categories of this paper are: hep-ph
11
The categories of this paper are: hep-lat
27
The categories of this paper are: comp-gas
21
The categories of this paper are: adap-org
31
The categories of this paper are: ao-sci
15
The categories of this paper are: nucl-ex
3
The categories of this paper are: physics
12
The categories of this paper are: nucl-th
24
The categories of this paper are: dg-ga
16
The categories of this paper are: stat
19
The categories of this paper are: eess
35
The categories of this paper are: mtrl-th