Xiongxin Yang

collaborators

3 papers

math.CO2026

$0/1$ -Polytopes with Exponentially Small Edge Expansion

Xiongxin Yang

We present a construction of a family of $0/1$ -polytopes whose edge expansion decreases exponentially with the dimension, which disproves the Mihail-Vazirani conjecture that the gr…

cs.LG2026

Learning $AC^{0}$ 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,…

cs.DS2025

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 $n$ -variables $k$ -CNF formula $I^¦$ from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF)…

0/1-Polytopes with Exponentially Small Edge Expansion

Learning AC0 under Locally Sampleable Graphical Models

Learning CNF formulas from uniform random solutions in the local lemma regime

$0/1$ -Polytopes with Exponentially Small Edge Expansion

Learning $AC^{0}$ under Locally Sampleable Graphical Models