Yixiao Yu

collaborators

4 papers

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.DS2026

Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime

Jingcheng Liu, Yixiao Yu

We show that for $q$ -colorings in $k$ -uniform hypergraphs with maximum degree $I^$ , if $k \geq 50$ and $q \geq 700 I^^{\frac{5}{k - 10}}$ , there is a "Lee-Yang" zero-free strip around the…

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)…

cs.DS2025

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…

Learning AC0 under Locally Sampleable Graphical Models

Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime

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

Phase Transitions via Complex Extensions of Markov Chains

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