Skip to content
DraconiticResearch
Search Sources API
197,578 studies31 sourcesUpdated 27 min ago
PreprintCC BY 4.0arXiv

A Short Note on Algorithms For The Noisy k-XOR Problem

  • Kiril Bangachev
Open at sourcePDFDOICite

Abstract

This mostly expository note studies the sample-noise regimes in which the testing problem for noisy k-XOR in dimension n can be efficiently solved. Concretely, we ask what pairs $(β, δ)$ admit algorithms running in time nO(k) where m = nβ, β∈ [0,k] is the number of samples and Bern(n−δ),δ∈ (0,+∞) is the noise distribution. The current state-of-the-art algorithms are: I. A folklore algorithm when β> 1, δ>1 based on Gaussian elimination; II. A folklore algorithm when β≥ k/2 based on the birthday paradox; III. A recent algorithm in the regime β> δ+ k(1−δ), δ∈ (0,1) based on a reduction to the first algorithm [DJ24,CSZ24]. IV. Extending [AF09], we strictly improve the last regime to β> δ+ (k−1)(1−δ), δ∈ (0,1). These algorithms correspond to efficiently finding short cycles in uniform hypergraphs and can be equivalently phrased as algorithmic Moore bounds.

Related

  1. On the Performance Evaluation of Anytime Algorithms in Noisy Optimization
    Ramona Boeh, Thomas Hanne
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  2. Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds
    Yashaswini Kaluguri, Nikhil Karamchandani
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  3. A note on the convergence guarantees of RLT-based algorithms for polynomial optimization
    Alejandro Barros-González, Julio González-Díaz, Brais González-Rodríguez +1
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  4. A short note about the spaces BVs(Rn)
    Guillermo García-Sáez
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  5. A short note on Kn-irregular graphs
    Tatiana Dovzhenok
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{bangachev2026short,
  title = {{A Short Note on Algorithms For The Noisy $k$-XOR Problem}},
  author = {Kiril Bangachev},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.27147},
  eprint = {2610.27147},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.27147},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A Short Note on Algorithms For The Noisy k-XOR Problem
AU  - Kiril Bangachev
PY  - 2026
DA  - 2026/10/19
PB  - arXiv
DO  - 10.48550/arxiv.2610.27147
UR  - https://arxiv.org/abs/2610.27147
AB  - This mostly expository note studies the sample-noise regimes in which the testing problem for noisy k-XOR in dimension n can be efficiently solved. Concretely, we ask what pairs $(β, δ)$ admit algorithms running in time n^O(k) where m = n^β, β∈ [0,k] is the number of samples and Bern(n^−δ),δ∈ (0,+∞) is the noise distribution. The current state-of-the-art algorithms are: I. A folklore algorithm when β> 1, δ>1 based on Gaussian elimination; II. A folklore algorithm when β≥ k/2 based on the birthday paradox; III. A recent algorithm in the regime β> δ+ k(1−δ), δ∈ (0,1) based on a reduction to the first algorithm [DJ24,CSZ24]. IV. Extending [AF09], we strictly improve the last regime to β> δ+ (k−1)(1−δ), δ∈ (0,1). These algorithms correspond to efficiently finding short cycles in uniform hypergraphs and can be equivalently phrased as algorithmic Moore bounds.
ER  -