Research Interests

Broadly speaking, my interest lies in theoretical computer science. Specifically, I have been actively exploring the following topics in recent times:

• Approximate counting and sampling
• Concentration inequalities and its application in machine learning
• Constructive lovasz local lemma and quantum lovasz local lemma

Research Articles

In accordance with the conventions of theoretical computers, authors are sorted alphabetically by last name.

• Improved Bounds for Sampling Solutions of Random CNF Formulas
  with Kewen Wu, and Kuan Yang
  SODA’23, Accepted [ PDF | arXiv]

  ---

• Deterministic counting Lovász local lemma beyond linear programming
  with Chunyang Wang and Yitong Yin
  SODA’23, Accepcted [ PDF | arXiv]

  ---

• Moser-Tardos Algorithm: beyond Shearer’s Bound
  with Qian Li and Xiaoming Sun
  SODA’23, Accepted. [ PDF | arXiv]

  ---

• Sampling Lovász Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time
  with Chunyang Wang and Yitong Yin
  FOCS’22, Accepted. [ PDF | arXiv]

  ---

• Sampling Constraint Satisfaction Solutions in the Local Lemma Regime
  with Weiming Feng and Yitong Yin
  STOC’21, pp. 1565-1578. [ PDF | arXiv]

  ---

• Dynamic Inference in Probabilistic Graphical Models
  with Weiming Feng, Xiaoming Sun and Yitong Yin
  ITCS’21, pp. 25:1–25:20. [ PDF | arXiv]

  ---

• New Versions of Lovász Local Lemma and Their Applications (in Chinese)
  with Xiaoming Sun
  SCIENCE CHINA Information Sciences, pp. 50:1680–1696, 2020. [ PDF | arXiv]

  ---

• Tight Bounds for Popping Algorithms
  with Heng Guo
  Random Struct. Algorithms, pp. 371-392, 2020. [ PDF | arXiv]

  ---

• Quantum Lovász Local Lemma: Shearer’s Bound Is Tight
  with Qian Li, Xiaoming Sun and Jiapeng Zhang
  STOC’19, pp. 461-472. [ PDF | arXiv]

  ---

• Variable-Version Lovász Local Lemma: Beyond Shearer’s Bound
  with Liang Li, Xingwu Liu, Yuyi Wang and Mingji Xia
  FOCS’17, pp. 451-462. [ PDF | arXiv]

  ---

• A Tighter Relation Between Sensitivity Complexity and Certificate Complexity
  with Qian Li and Xiaoming Sun
  Theor. Comput. Sci., 762, 1-12, 2019. Preliminary version: COCOON’17, pp. 262-274. [ PDF | arXiv]

Preprints

• Perfect Sampling for (Atomic) Lovász Local Lemma
  with Xiaoming Sun and Kewen Wu
  Submitted [ PDF | arXiv]

  ---