{
  "abstract": "We construct explicit non-malleable affine extractors for every constant entropy rate, with linear output length and exponentially small error, against any fixed number of affine tamperings without fixed points. For every fixed $0<η<1$ and $t$, we also obtain entropy threshold $C_{η,t}n/\\log n$, output length $\\lfloor n^{1-η}\\rfloor$, and error $2^{-n^{1-η}}$ against $t$ tamperings. Our extractors, as well as the directional affine extractors of Li and Zhong (CCC 2024), yield explicit Boolean functions with correlation $2^{-Ω(n)}$ against weakly read-once linear branching programs of size $2^{Ω(n)}$. For non-oblivious decision trees, we prove linear depth lower bounds for queries of each fixed degree $r\\ge2$. Applying Li's sumset extractor (FOCS 2023) gives depth $Ω_δ((n/\\ell)\\log\\ell)$ for growing locality $\\ell\\le n^{1-δ}$, where $0<δ<1$ is fixed. In the same range, directional affine extractors give correlation $2^{-Ω(n/\\sqrt\\ell)}$ against local trees of depth $c(n/\\ell)\\log\\ell/\\log\\log\\ell$, for a sufficiently small constant $c>0$. Our extractors derandomize the lossless lifting of Efremenko and Itsykson (STOC 2026). For every fixed $0<ξ<1$, this gives explicit polynomial-size unsatisfiable CNFs on $N$ variables whose $\\mathrm{Res}(\\oplus)$ refutations of resolution depth at most $N$ require size at least $2^{(1-ξ)N}$. Separately, parity substitutions give polynomial-size CNFs on $N$ variables with polynomial-size ordinary-resolution proofs for which every $\\mathrm{Res}(\\oplus)$ refutation of size $S$ and depth $d$ satisfies $d\\log(2S)=Ω(N^2)$. This removes the $\\log^2 N$ loss in the tradeoff of Itsykson, Podolskii, and Shekhovtsov (CCC 2026).",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2610.02407",
  "author_total": 2,
  "authors": [
    {
      "name": "Xin Li"
    },
    {
      "name": "Yan Zhong"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/25epwq2tszfqw.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2610.02407",
  "fulltext_url": null,
  "id": "25epwq2tszfqw",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2610.02407",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.CC"
    ],
    [
      "arxiv",
      "math.AG"
    ],
    [
      "arxiv",
      "math.CO"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://arxiv.org/pdf/2610.02407",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-01",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/25epwq2tszfqw.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:26:50Z",
      "native_id": "2610.02407",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2610.02407"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.AG",
      "subfield": "algebra-number-theory"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds",
  "title_text": "Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds",
  "type": "preprint",
  "updated_at": "2026-10-30T12:26:50Z",
  "url": "https://research.draconitic.com/paper/25epwq2tszfqw",
  "venue": "arXiv",
  "versions": []
}