7 papers
Faster FPRAS for the Permanent via Restricted Poincaré Inequalities and Coupled Flows
Xiaoyu Chen, Eric Vigoda, Xiongxin Yang
The permanent of an matrix equals the number of perfect matchings in the bipartite graph with edges defined by . Jerrum, Sinclair, and Vigoda (2004) presen…
-Polytopes with Exponentially Small Edge Expansion
Xiongxin Yang
We present a construction of a family of -polytopes whose edge expansion decreases exponentially with the dimension, which disproves the Mihail-Vazirani conjecture that the gr…
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,…
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…
Spectral Independence Beyond Total Influence on Trees and Related Graphs
Xiaoyu Chen, Xiongxin Yang, Yitong Yin +1
We study how to establish , a key concept in sampling, without relying on total influence bounds, by applying an of t…
Approximability of the Four-Vertex Model
Zhiguo Fu, Tianyu Liu, Xiongxin Yang
We study the approximability of the four-vertex model, a special case of the six-vertex model.We prove that, despite being NP-hard to approximate in the worst case, the four-vertex…
Beyond Windability: An FPRAS for The Six-Vertex Model
Zhiguo Fu, Junda Li, Xiongxin Yang
The six-vertex model is an important model in statistical physics and has deep connections with counting problems. There have been some fully polynomial randomized approximation sc…