Weiming Feng

activity

20242026

collaborators

Showing cs.DSShow all

2 papers · 1 filter

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 $Φ$ from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) w…

cs.DS2024

Approximately Counting Knapsack Solutions in Subquadratic Time

Weiming Feng, Ce Jin

We revisit the classic #Knapsack problem, which asks to count the Boolean points $(x_{1}, \dots, x_{n}) \in {0, 1}^{n}$ in a given half-space $\sum_{i = 1}^{n} W_{i} x_{i} \leq T$ . This #P-complete pro…