Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds
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η,tn/log n, output length ⌊ n1−η⌋, and error 2−n1−η 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≥2. Applying Li's sumset extractor (FOCS 2023) gives depth Ωδ((n/ℓ)logℓ) for growing locality ℓ≤ n1−δ, where 0<δ<1 is fixed. In the same range, directional affine extractors give correlation 2−Ω(n/√ℓ) against local trees of depth c(n/ℓ)logℓ/loglogℓ, 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 Res(⊕) 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 Res(⊕) refutation of size S and depth d satisfies dlog(2S)=Ω(N2). This removes the log2 N loss in the tradeoff of Itsykson, Podolskii, and Shekhovtsov (CCC 2026).
Related
- On the maximum relational complexity of affine groups
- Federated Affine Variational Inequalities: Exact Averaging and Complexity Limits
- Small-time controllability of affine systems and quadratic Lie brackets
- Equidistant Affine Subspaces: Explicit Bounds, Codimension-Two Reduction, and Transverse Products
- Tight Heavy-Tailed Complexity Bounds for Optimizing Polyak--Łojasiewicz Objectives
BibTeX
@misc{li2026nonmalleable,
title = {{Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds}},
author = {Xin Li and Yan Zhong},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02407},
eprint = {2610.02407},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02407},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds
AU - Xin Li
AU - Yan Zhong
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02407
UR - https://arxiv.org/abs/2610.02407
AB - 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_η,tn/log n, output length ⌊ n^1−η⌋, 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≥2. Applying Li's sumset extractor (FOCS 2023) gives depth Ω_δ((n/ℓ)logℓ) for growing locality ℓ≤ n^1−δ, where 0<δ<1 is fixed. In the same range, directional affine extractors give correlation 2^−Ω(n/√ℓ) against local trees of depth c(n/ℓ)logℓ/loglogℓ, 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 Res(⊕) 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 Res(⊕) refutation of size S and depth d satisfies dlog(2S)=Ω(N^2). This removes the log^2 N loss in the tradeoff of Itsykson, Podolskii, and Shekhovtsov (CCC 2026).
ER -