45 citations · 87 across the 6 of their papers we have counts for
Showing 2006Show all
2 papers · 1 filter
cs.AI2006★ 2 cited
Local approximate inference algorithms
Kyomin Jung, Devavrat Shah
We present a new local approximation algorithm for computing Maximum a Posteriori (MAP) and log-partition function for arbitrary exponential family distribution represented by a fi…
cs.DM2006★ 27 cited
Counting good truth assignments of random k-SAT formulae
Andrea Montanari, Devavrat Shah
We present a deterministic approximation algorithm to compute logarithm of the number of `good' truth assignments for a random k-satisfiability (k-SAT) formula in polynomial time (…