Feng, Weiming and Guo, Heng and Wang, Chunyang and Wang, Jiaheng and Yin, Yitong (2025) TOWARD DERANDOMIZING MARKOV CHAIN MONTE CARLO. SIAM JOURNAL ON COMPUTING, 54 (3). pp. 775-813. ISSN 0097-5397, 1095-7111
Full text not available from this repository. (Request a copy)Abstract
We present a new framework to derandomize certain Markov chain Monte Carlo (MCMC) algorithms. As in MCMC, we first reduce counting problems to sampling from a sequence of marginal distributions. For the latter task, we introduce a method called coupling toward the past that can, in logarithmic time, evaluate one or a constant number of variables from a stationary Markov chain state. Since there are at most logarithmic random choices, this leads to very simple derandomization. As an application, we provide an efficient deterministic approximate counting algorithm for hypergraph independent sets, under local lemma type conditions matching, up to lower-order factors, their state-of-the-art randomized counterparts.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | DETERMINISTIC RANDOM-WALKS; TIME APPROXIMATION ALGORITHMS; CORRELATION DECAY; STOPPING-TIMES; COLORINGS; VOLUME; approximate counting; Markov chain Monte Carlo; deterministic algorithm |
| Subjects: | 000 Computer science, information & general works > 004 Computer science |
| Divisions: | Informatics and Data Science > General computer science > Chair of Algorithms and Complexity Theory (Prof. Dr. Radu Curticapean) |
| Depositing User: | Dr. Gernot Deinzer |
| Date Deposited: | 28 Jul 2026 08:49 |
| Last Modified: | 28 Jul 2026 08:49 |
| URI: | https://pred.uni-regensburg.de/id/eprint/67312 |
Actions (login required)
 |
View Item |
