Hypergraph cycle enumeration for efficient inference of planted k-XOR with smooth trade-off

Arman Babakhani, Enrico Fontana, Junhyung Lyle Kim, Shouvanik Chakrabarti, Ruslan Shaydulin

arXivarxiv/2610.40941Oct 29, 2026quant-phscore 0

We introduce hypergraph cycle enumeration (HCE), a simple spectral framework for detecting and recovering planted signals in noisy hypergraph inference problems. We study HCE on one representative problem from this class, namely planted noisy k-XOR, also known as sparse Learning Parity with Noise (LPN). Both theoretically and empirically, HCE achieves comparable recovery behavior to Kikuchi method, matching Kikuchi hierarchy. We identify parameter regimes where HCE outperforms Kikuchi method, showing that neither algorithm is universally better. We also show a subquadratic quantum speedup…

SourceJSON

Comments and reviews

No comments yet.

API

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