{"id":"arxiv/2610.02407","url":"https://arxiv.org/abs/2610.02407","tags":["cs.CC","math.AG","math.CO"],"score":0,"title":"Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds","domain":"cs.CC","source":"arxiv","authors":["Xin Li","Yan Zhong"],"reviews":0,"subject":"cs.CC","summary":"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 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$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-01","reactions":{}}