Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BAYESIAN INFERENCE:
Reports tagged with Bayesian inference:
TR03-003 | 19th December 2002
Fahiem Bacchus, Shannon Dalmao

DPLL with Caching: A new algorithm for #SAT and Bayesian Inference

Bayesian inference and counting satisfying assignments are important
problems with numerous applications in probabilistic reasoning. In this
paper, we show that plain old DPLL equipped with memoization can solve
both of these problems with time complexity that is at least as
good as all known algorithms. Furthermore, DPLL with memoization
more >>>


TR23-145 | 20th September 2023
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran

Total Variation Distance Estimation Is as Easy as Probabilistic Inference

In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for ... more >>>




ISSN 1433-8092 | Imprint