3 papers
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…
math.ST2026
Detection of local geometry in random graphs: information-theoretic and computational limits
Jinho Bok, Shuangping Li, Sophie H. Yu
We study the problem of detecting local geometry in random graphs. We introduce a model , where a hidden community of average size has edges drawn as a…