{"ID":2882579,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.09422","arxiv_id":"2508.09422","title":"A Classical Quadratic Speedup for Planted $k$XOR","abstract":"A recent work of Schmidhuber et al (QIP, SODA, \u0026 Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted $k$XOR problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant $k$. Thus for such $k$, the quantum speedup of Schmidhuber et al. becomes only quadratic (though it retains a space advantage). Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration.","short_abstract":"A recent work of Schmidhuber et al (QIP, SODA, \u0026 Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted $k$XOR problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of...","url_abs":"https://arxiv.org/abs/2508.09422","url_pdf":"https://arxiv.org/pdf/2508.09422v1","authors":"[\"Meghal Gupta\",\"William He\",\"Ryan O'Donnell\",\"Noah G. Singer\"]","published":"2025-08-13T01:45:47Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CR\",\"quant-ph\"]","methods":"[]","has_code":false}