Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-241 | 1st October 2026 21:05

Non-Malleable Affine Extractors with Small Error and Complexity Lower Bound

RSS-Feed




TR26-241
Authors: Xin Li, Yan Zhong
Publication: 9th October 2026 05:36
Downloads: 18
Keywords: 


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 $00$.

Our extractors derandomize the lossless lifting of Efremenko and Itsykson (STOC 2026). For every fixed $0<\xi<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-\xi)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)=\Omega(N^2)$. This removes the $\log^2 N$ loss in the tradeoff of Itsykson, Podolskii, and Shekhovtsov (CCC 2026).



ISSN 1433-8092 | Imprint