SOURCE-LINKED INTELLIGENCE
On Statistical-Computational Gaps in Graph Combinatorial Testing Problems
We study high-dimensional graph combinatorial hypothesis testing problems in which a signal is supported on the edge set of an unknown subgraph drawn from a class invariant under vertex relabeling. For Gaussian observations, we characterize sharp statistical and computational thresholds (at polynomial order) for the signal magnitude required for strong detection across various combinatorial graph alternatives. Our analysis is based on bounding the second moments of the full and low-degree likelihood ratios in terms of the overlap of two independent latent structures and comparing the resulting
Read original source ↗ Open in workspace
- recordType
- paper
- region
- Global
Evidence & attribution
- arXiv · AI, language, vision and robotics · 2026-10-30T16:41:47.000Z
First collected: 2026-11-02T10:21:21.339Z. This is not the publication date.