Fast sampling and counting k-SAT solutions in the local lemma regime

Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang
July, 2021
PDF Talk@STOC Talk@IJTCS Slides@STOC Slides@ICT_CAS Heng's slides Heng's talk
Type
2
Publication
Journal of the ACM (JACM) 68 (6), 1-42 (Conference version in STOC 2020)
Weiming Feng
Weiming Feng
Junior Fellow

I am a Junior Fellow at the Institute for Theoretical Studies, ETH Zürich. My research interest lies in theoretical computer science. Currently, I focus on sampling and counting algorithms.

Heng Guo
Heng Guo
Reader

I am a reader in algorithms and complexity in the School of informatics, University of Edinburgh. My research focuses on algorithms from a complexity perspective.

Yitong Yin
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.

Chihao Zhang
Chihao Zhang
Associate Professor

I am an Associate Professor in John Hopcroft Center for Computer Science at Shanghai Jiao Tong University since 2018. I work in the area of theoretical computer science.