• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Dual Hashing-based Algorithms for Discrete Integration.
de Colnet,Alexis, and Kuldeep S. Meel.
In Proceedings of International Conference on Constraint Programming (CP), October 2019.
Given a boolean formula F and a weight function $\rho$, the problem of discrete integration seeks to compute the weight of $F$, defined as the sum of the weights of satisfying assignments. Discrete integration, also known as weighted model counting, is a fundamental problem in computer science with wide variety of applications ranging from machine learning and statistics to physics and infrastructure reliability. Given the intractability of the exact variant, the problem of approximate weighted model counting has been subject to intense theoretical and practical investigations over the years. The primary contribution of this paper is to investigate development of algorithmic approaches for discrete integration. Our framework allows us to derive two different algorithms, which can be seen as dual to each other: \textsfWISH, which was already discovered by Ermon et al \citeEGSS13c, and a new algorithm: \textsfSWITCH.We argue that these algorithms can be seen as dual to each other, in the sense that their complexities differ only by a permutation of certain parameters. Indeed we show that, for $F$ defined over $n$ variables, a weight function $\rho$ that can be represented using $p$ bits, and a confidence parameter $\delta$, there is a function $f$ and an NP oracle such that \textsfWISH makes $\mathcalO łeft(f(n,p,\delta)\right)$ calls to NP oracle while \textsfSWITCH makes $\mathcalOłeft(f(p,n,\delta)\right)$ queries. We find $f(x,y,\delta)$ polynomial in $x$, $y$ and $1/\delta$, more specifically $f(x,y,\delta) = xłog(y)łog(x/\delta)$. We first focus on striking similarities of both the design process and structure of the two algorithms but then show that despite this quasi-symmetry, the analysis yields time complexities dual to each other. Another contribution of this paper is the use of 3-wise property independence of XOR based hash functions in the analysis of WISH and SWITCH. To the best of our knowledge, this is the first usage of 3-wise independence in deriving stronger concentration bounds.
@inproceedings{DM19,
title={Dual Hashing-based Algorithms for Discrete Integration},
author={de Colnet,Alexis and Meel, Kuldeep S.},
year={2019},
month=oct,
booktitle=CP,
bib2html_rescat={Counting},
bib2html_dl_pdf={../Papers/cp19-dm.pdf},
bib2html_pubtype={Refereed Conference},
abstract={
Given a boolean formula F and a weight function $\rho$, the problem of discrete integration seeks to compute the weight of $F$, defined as the sum of the weights of satisfying assignments. Discrete integration, also known as weighted model counting, is a fundamental problem in computer science with wide variety of applications ranging from machine learning and statistics to physics and infrastructure reliability. Given the intractability of the exact variant, the problem of approximate weighted model counting has been subject to intense theoretical and practical investigations over the years.
The primary contribution of this paper is to investigate development of algorithmic approaches for discrete integration. Our framework allows us to derive two different algorithms, which can be seen as dual to each other: \textsf{WISH}, which was already discovered by Ermon et al~\cite{EGSS13c}, and a new algorithm: \textsf{SWITCH}.We argue that these algorithms can be seen as dual to each other, in the sense that their complexities differ only by a permutation of certain parameters. Indeed we show that, for $F$ defined over $n$ variables, a weight function $\rho$ that can be represented using $p$ bits, and a confidence parameter $\delta$, there is a function $f$ and an NP oracle such that \textsf{WISH} makes $\mathcal{O} \left(f(n,p,\delta)\right)$ calls to NP oracle while \textsf{SWITCH} makes $\mathcal{O}\left(f(p,n,\delta)\right)$ queries. We find $f(x,y,\delta)$ polynomial in $x$, $y$ and $1/\delta$, more specifically $f(x,y,\delta) = x\log(y)\log(x/\delta)$.
We first focus on striking similarities of both the design process and structure of the two algorithms but then show that despite this quasi-symmetry, the analysis yields time complexities dual to each other. Another contribution of this paper is the use of 3-wise property independence of XOR based hash functions in the analysis of WISH and SWITCH. To the best of our knowledge, this is the first usage of 3-wise independence in deriving stronger concentration bounds.
},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Sun Apr 14, 2024 11:15:51