Hypergraph cycle enumeration for efficient inference of planted k-XOR with smooth trade-off
Abstract
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 for HCE by replacing one of the algorithm's steps with a quantum walk. Our classical and quantum algorithms do not refute the quartic quantum speedup of quantum Kikuchi method, which remains valid for the practically relevant regime of large size and high noise strength.
Related
- Smooth Tensor Multi-View Clustering on Well Logs via Hypergraph Topology and Concurrent Group Sparsity
- Bayesian hypergraph inference from scarce and noisy dynamical observations
- PPI++: Efficient prediction-powered inference
- Automated, Efficient, and Model-Free Inference for Randomized Clinical Trials via Data-Driven Covariate Adjustment
- Efficient Bayesian inference for multiple network data
BibTeX
@misc{babakhani2026hypergraph,
title = {{Hypergraph cycle enumeration for efficient inference of planted k-XOR with smooth trade-off}},
author = {Arman Babakhani and Enrico Fontana and Junhyung Lyle Kim and Shouvanik Chakrabarti and Ruslan Shaydulin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40941},
eprint = {2610.40941},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40941},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Hypergraph cycle enumeration for efficient inference of planted k-XOR with smooth trade-off
AU - Arman Babakhani
AU - Enrico Fontana
AU - Junhyung Lyle Kim
AU - Shouvanik Chakrabarti
AU - Ruslan Shaydulin
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40941
UR - https://arxiv.org/abs/2610.40941
AB - 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 for HCE by replacing one of the algorithm's steps with a quantum walk. Our classical and quantum algorithms do not refute the quartic quantum speedup of quantum Kikuchi method, which remains valid for the practically relevant regime of large size and high noise strength.
ER -