The study aims to investigate the relationship between Markov chain Monte Carlo, correlation decay, and the Lee-Yang formalism of complex roots of partition functions to solve special cases of the "sign problem." Special cases include the independence polynomial with negative weights and the permanents of positive semi-definite matrices, which have connections to physics and can be algorithmically tractable. The study also addresses the conceptual problem of understanding the power of randomness in approximate counting algorithms.
Tata Institute of Fundamental Research (TIFR)
Acces sibility Controls