Sharp Low-Degree Thresholds for Planted-vs-Planted Testing

Anda Skeja, Daniel Gutiérrez Espinoza, Fiona Skerman, Alexander S. Wein

arXivarxiv/2606.05266Jun 3, 2026cs.LGscore 0

We establish the first sharp thresholds for low-degree polynomial tests in planted-vs-planted settings, where the goal is to determine with vanishing error which of two structured planted mechanisms generated the observed data. We prove matching low-degree upper and lower bounds for counting communities in the planted submatrix and planted dense subgraph models. The resulting testing threshold coincides, down to the sharp constant, with the known low-degree recovery threshold. In contrast, the task of weak testing, where the goal is to outperform random guessing, does not have a sharp…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2606.05266
curl -X POST /api/v1/records/arxiv/2606.05266/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.05266/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'