# Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds

Preprint · Xin Li, Yan Zhong

- Archive id: arxiv:2610.02407
- Published: 2026-10-01
- arXiv: https://arxiv.org/abs/2610.02407
- Source URL: https://arxiv.org/abs/2610.02407
- PDF: https://arxiv.org/pdf/2610.02407
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.