In this note, we give a simple analysis of a non-adaptive simulated annealing algorithm for estimating the partition function of Gibbs distributions. This yields the most efficient reduction of this kind so far. We also establish lower bounds for both general and non-adaptive algorithms, showing that our algorithm is o...
Heng Guo, Hong-Yang Liu, Xiong-Xin Yang et al.· 1 citation
The permanent of an $n\times n$ $0/1$ matrix $A$ equals the number of perfect matchings in the bipartite graph with edges defined by $A$. Jerrum, Sinclair, and Vigoda (2004) presented an FPRAS for approximating the permanent of any nonnegative matrix using a novel simulated-annealing algorithm. The running time was imp...
Xiao-Yu Chen, Eric Vigoda, Xiong-Xin Yang· 2 citations
This approach integrates a classic grid-based partition framework with a novel charging analysis that controls the cost of structure-sensitive offline routines within each cell, to perform a global aggregation of the update time, by circumventing the worst-case costs associated with individual cell updates.
S. Bhore, Subhash Suri, Jie Xue et al.· International Colloquium on...· 0 citations
A quasipolynomial-time learner for $\mathsf{AC}^0$ under graphical models that admit efficient local samplers, circumventing the polynomial-growth requirement in prior work.
Weiming Feng, Xiongxin Yang, Yixiao Yu et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
