Markov chains as the single-site dynamics are defined sequentially.
Whether such sequentiality is inevitable, raised intriguing questions in theory.
In a seminal work [1]}, Mulmuley, Vazirani and Vazirani asked whether there is an efficient (\(\mathsf {RNC}\) ) parallel algorithm for sampling bipartite perfect matchings so that permanent can be approximately computed in parallel.
This was partially answered negatively by Teng [2]}, who pointed out a barrier to parallelize the chains for bipartite perfect matching, which are slightly beyond the scope of single-site dynamics.
