5 papers
Simulated annealing and Weak Poincaré inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model
Zhe Hou, Jingcheng Liu, Yixiao Yu
We study sampling from the Gibbs distribution of the Sherrington-Kirkpatrick (SK) model with Glauber dynamics. For every fixed inverse temperature and every fixed $M,D>0…
Learning under Locally Sampleable Graphical Models
Weiming Feng, Xiongxin Yang, Yixiao Yu +1
The problem of learning constant-depth circuits holds profound implications for computational learning theory. In a seminal result, by introducing the low-degree algorithm, Linial,…
Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime
Jingcheng Liu, Yixiao Yu
We show that for -colorings in -uniform hypergraphs with maximum degree , if and , there is a "Lee-Yang" zero-free strip around the i…
Learning CNF formulas from uniform random solutions in the local lemma regime
Weiming Feng, Xiongxin Yang, Yixiao Yu +1
We study the problem of learning a -variables -CNF formula from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) w…
Phase Transitions via Complex Extensions of Markov Chains
Jingcheng Liu, Chunyang Wang, Yitong Yin +1
We study algebraic properties of partition functions, particularly the location of zeros, through the lens of rapidly mixing Markov chains. The classical Lee-Yang program initiated…