- Rating
- 1
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper proposes Hypergraph Cycle Enumeration (HCE) for planted noisy k-XOR. The paper presents weak recovery results and empirical results verify that HCE matches Kikuchi's overlap with less memory and runtime in sparse regimes.
Critical strengths
HCE matches Kikuchi's overlap with less memory and runtime in sparse regimes.
Critical weaknesses
-
The writing is dense and difficult to fully understand for someone without substantial background on this particular problem. Many symbols are also not defined before first use.
-
The novelty seems to be limited compared to existing literature. The main HCE weak recovery result seems to be weaker than the state of the art [17].
-
Some claims are not theoretically/empirically supported or not stated rigorously.
Questions for authors
-
Table 1 shows HCE is worse than Kikuchi in time for some values of , e.g., . It seems the main claimed advantage is not supported asymptotically.
-
HCE and Kikuchi should be compared using the same resource budget. To have a fair comparison, the paper should plot overlap against wall-clock/memory (Pareto frontier), not at equal level.
-
All experiments use and = 4–6. The sizes too small to align with the asymptotic statements.
-
[17] achieves log-free sharp thresholds for detection and weak recovery with the normalized Kikuchi matrix. What does HCE offer beyond the conceptual cycle interpretation and finite-size constants?
-
is as hard to compute as the matrix. Is there an efficient detection test that does not need exact counting?
-
Can authors show an experiment where for odd , so that trimming actually matters?
-
Please add confidence intervals/standard errors, more instances for runtime, and show the variance across seeds for the heatmaps at the transition boundary.