Abstract
We present polynomial-time algorithms for approximate counting and sampling solutions to constraint satisfaction problems (CSPs) with atomic constraints within the local lemma regime $pD^{2+o_q(1)}\lesssim 1$. When the domain size $q$ of each variable becomes sufficiently large, this almost matches the known lower bound $pD^2\gtrsim 1$ for approximate counting and sampling solutions to atomic CSPs [Bezáková et al, SICOMP ‘19; Galanis, Guo, Wang, TOCT ‘22], thus establishing an almost tight sampling Lovász local lemma for large domain sizes.
Chunyang Wang
Ph.D Student
I am currently a fifth-year Ph.D student in the Theory Group in the Department of Computer Science and Technology at Nanjing University. My research interest lies in a broad aspect of computer science. Currently, I am focusing on algorithms for counting and sampling.
Yitong Yin
Professor
I am a professor in the Theory Group in the Department of Computer Science and Technology at Nanjing University. I am interested in Theoretical Computer Science.