Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
Xuan Chen, Shuangping Li
The low-degree heuristic has become a widely used framework for predicting computational thresholds in average-case planted-versus-null problems. However, a recent sequence of coun…
cs.CC2026
Stable algorithms cannot reliably find isolated perceptron solutions
Shuyang Gong, Brice Huang, Shuangping Li +1
We study the binary perceptron, a random constraint satisfaction problem that asks to find a Boolean vector in the intersection of independently chosen random halfspaces. A strikin…