{"ID":2878655,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.18185","arxiv_id":"2508.18185","title":"Spectral Refutations of Semirandom $k$-LIN over Larger Fields","abstract":"We study the problem of strongly refuting semirandom $k$-LIN$(\\mathbb{F})$ instances: systems of $k$-sparse inhomogeneous linear equations over a finite field $\\mathbb{F}$. For the case of $\\mathbb{F} = \\mathbb{F}_2$, this is the well-studied problem of refuting semirandom instances of $k$-XOR, where the works of [GKM22,HKM23] establish a tight trade-off between runtime and clause density for refutation: for any choice of a parameter $\\ell$, they give an $n^{O(\\ell)}$-time algorithm to certify that there is no assignment that can satisfy more than $\\frac{1}{2} + \\varepsilon$-fraction of constraints in a semirandom $k$-XOR instance, provided that the instance has $O(n) \\cdot \\left(\\frac{n}{\\ell}\\right)^{k/2 - 1} \\log n /\\varepsilon^4$ constraints, and the work of [KMOW17] provides good evidence that this tight up to a $\\mathrm{polylog}(n)$ factor via lower bounds for the Sum-of-Squares hierarchy. However for larger fields, the only known results for this problem are established via black-box reductions to the case of $\\mathbb{F}_2$, resulting in an $|{\\mathbb{F}}|^{3k}$ gap between the current best upper and lower bounds. In this paper, we give an algorithm for refuting semirandom $k$-LIN$(\\mathbb{F})$ instances with the \"correct\" dependence on the field size $|{\\mathbb{F}}|$. For any choice of a parameter $\\ell$, our algorithm runs in $(|{\\mathbb{F}}|n)^{O(\\ell)}$-time and strongly refutes semirandom $k$-LIN$(\\mathbb{F})$ instances with at least $O(n) \\cdot \\left(\\frac{|{\\mathbb{F}^*}| n}{\\ell}\\right)^{k/2 - 1} \\log(n |{\\mathbb{F}^*}|) /\\varepsilon^4$ constraints. We give good evidence that this dependence on the field size $|{\\mathbb{F}}|$ is optimal by proving a lower bound for the Sum-of-Squares hierarchy that matches this threshold up to a $\\mathrm{polylog}(n |{\\mathbb{F}^*}|)$ factor. Our results also extend to the more general case of finite Abelian groups.","short_abstract":"We study the problem of strongly refuting semirandom $k$-LIN$(\\mathbb{F})$ instances: systems of $k$-sparse inhomogeneous linear equations over a finite field $\\mathbb{F}$. For the case of $\\mathbb{F} = \\mathbb{F}_2$, this is the well-studied problem of refuting semirandom instances of $k$-XOR, where the works of [GKM2...","url_abs":"https://arxiv.org/abs/2508.18185","url_pdf":"https://arxiv.org/pdf/2508.18185v1","authors":"[\"Nicholas Kocurek\",\"Peter Manohar\"]","published":"2025-08-25T16:38:24Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}