CS Paper Radar

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

Xin Li, Yan Zhong

cs.CC math.AGmath.CO ·submitted 2026-10-01 19:33 UTC · v1
publishedtheory

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).

Comment
Abstract shortened due to constraints. 140 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Multiplicative and Additive Extractors for Low Entropy Samplable Sources Under Reduced Assumptions

cs.CC ·2026-11-05 ·Marshall Ball, Eshan Chattopadhyay, Mohit Gurumukhani, Ronen Shaltiel, Yunya Zhao
hot direction similarity 0.68
Abstract

Trevisan and Vadhan [TV, FOCS'00] constructed (seedless) extractors for distributions samplable by poly-size circuits that have very high min-entropy, under the very strong complexity theoretic hardness assumption that $\mathsf{E}=\mathsf{DTIME}(2^{O(n)})$ requires size $2^{Ω(n)}$ circuits that have oracle access to $Σ_6^{\text{P}}$. In this paper we give three new explicit constructions of extractors for samplable distributions. First, we construct an extractor that extracts one bit, with constant error, for min-entropy $k=O(\log n)$, which matches the non-constructive probabilistic argument. This result uses hardness for nondeterministic circuits, and achieves the same parameters as the recent extractor of Oh and Shaltiel [OS, STOC'26] under an incomparable hardness assumption. In contrast to the extractor of [OS26], our extractor (and, similarly, the constructions below) also works for the more general class of distributions samplable with postselection (a model introduced by [BGDM, FOCS'23] that generalizes samplable and recognizable sources). Second, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=n^α$, where $α>0$ is an arbitrary constant. This result also uses hardness for nondeterministic circuits, and significantly improves upon the recent extractor of [Shaltiel, FOCS'25] which required a much stronger assumption. This extractor is also \textit{multiplicative}: a stronger notion suggested in [AASY, Comp. Complexity'16; Shaltiel, CCC'25] to make extractors for samplable distributions suitable for selecting keys for cryptographic protocols. Third, we construct an extractor that extracts almost all the entropy, with polynomially small error, for min-entropy $k=\mathrm{polylog}(n)$. This result uses hardness for circuits that have oracle access to $Σ_2^{\text{P}}$.

0.30

Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness

cs.CC math.CO ·2026-10-19 ·Xin Li, Yan Zhong
publishedtheory similarity 0.68
Abstract

We give a short-description decomposition of bounded-width CNFs. For every fixed $\varepsilon>0$, every width-$b$ CNF on $m$ variables is an exact disjoint union of at most $2^{\varepsilon m}$ width-$b$ CNFs, each determined by $2^{O_\varepsilon(b)}\log(m+1)$ satisfying assignments. For every fixed $d\ge3$, we prove a worst-case size lower bound of $2^{Ω_d((n\log n)^{1/(d-1)})}$ against depth-at-most-$d$ unbounded-fan-in AND/OR circuits with input negations for three polynomial-time Boolean families: inverse trace over binary fields, the Goldreich--Tal trilinear function, and OpenAI's polynomial evaluator with its original parameters. All parameter bits count as inputs. For inverse trace, every such circuit of size at most $S$, where $n\le S\le2^{c_dn^{1/(d-1)}}$, has uniform sign correlation at most $2^{-η_dn\log\log S/(\log S)^{d-1}}$. Here $c_d,η_d>0$ depend only on $d$. This improves on the classical parity correlation bound. The lower bounds combine the decomposition with restriction arguments; the correlation bound additionally uses common partial decision trees. We also construct exact nonuniform AND/OR circuits for inverse trace of size $2^{O(n^{2/3})}$ at depth eight and $2^{O(\sqrt n\log n)}$ at depth nine. For every fixed integer $h\ge2$, the construction gives depth-$(4h+1)$ circuits of size $2^{O_h(n^{1/h}\log n)}$. The upper bounds implement finite-field evaluation and interpolation using circuits that enumerate intermediate states.

0.53

Near-Inverse-Linear Barriers for Explicit Affine Witness Isolation

cs.CC ·2026-10-08 ·Sebastian Ben Daniel
similarity 0.64
Abstract

We study randomized nonuniform polynomial-size transformations that output explicit binary affine filters for circuit inputs whose nonempty satisfying sets are affine. The filter may depend on the entire input description; no affine basis is supplied. For every fixed $δ<1$, a worst-case singleton success guarantee $Ω(n^{-δ})$, where $n$ is the witness arity, implies $NP\subseteq P/poly$. More generally, any success guarantee $ω(\log n/n)$ yields satisfiability circuits of size $(s+2)^{O(1)}2^{o(v)}$ for length-$s$ descriptions with at most $v$ witness variables, hence subexponential in $v$ when $s=v^{O(1)}$. Conversely, SAT search-to-decision gives deterministic perfect isolation, making polynomial-resource fixed-exponent strong affine isolation equivalent to $NP\subseteq P/poly$. For explicit unions of at most $n^β$ affine components, success $Ω(n^{-δ})$ implies the same collapse whenever $β,δ\ge0$ and $β+δ<1$. The inverse-linear endpoint is not claimed.

0.07

The CNF Encoding Complexity of Boolean Functions

cs.CC cs.LO ·2026-11-03 ·Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux
theory similarity 0.64
Abstract · 36 pages, comments are welcome!

We study the minimum number of clauses required to encode a boolean function into a CNF formula with auxiliary variables. Our main result is that if a boolean function can be evaluated in nondeterministic time $t$ (in the RAM model) with $m$ bits of advice such that at most $b$ bits of advice are accessed for each input, then it admits a CNF encoding with $\widetilde{O}(t + \sqrt{mb})$ clauses. This constitutes a nonuniform generalization of Robson's (TCS'91) variant of the Cook--Levin theorem, for which a naïve generalization would yield $\widetilde{O}(t+m)$ clauses; our applications leverage $b = o(m)$ to obtain significantly better bounds. Since preprocessed data structures can be modeled as computation with advice, our result allows us to translate space- and time-efficient data structures to compact CNF encodings. As an application, we derandomize a data structure of Larsen and Williams (SODA'17) to show that every $k$-CNF function on $n$ inputs can be encoded with $n^k/2^{Ω_k(\sqrt{\lg n})}$ clauses. Notably, despite encoding a $k$-CNF function, the encoding itself necessarily contains clauses of unbounded width, since an information-theoretic argument shows that the minimum number of bounded-width clauses to encode such functions is $Ω_k(n^{k}/\lg n)$ in the worst case. In general terms, our results imply that for a wide variety of NP-complete problems, one can reduce to CNF-SAT in a way that results in asymptotically fewer clauses than previously known methods.

0.31

Quadratic Extractors

cs.CC cs.CRmath.CO ·2026-11-05 ·Gautam Chandrasekaran, Jesse Goodman, David Zuckerman
similarity 0.63
Abstract

A quadratic source is a random variable $X\sim\mathbb{F}_2^n$ generated by applying $n$ quadratics to a hidden uniform string. Previously, the best-known explicit extractor for this model required min-entropy roughly $k=n-\sqrt{\log n}$. In this paper, we give an explicit construction for min-entropy $k=\mathrm{polylog}(n)$. Even for the special case of $2$-local sources, where each bit of $X$ depends on two hidden uniform bits, achieving an entropy requirement below $k=\sqrt{n}$ was an important open problem. This is because such sources provably cannot be reduced (in a black-box manner) to our most powerful general-purpose seedless extractor, known as a sumset extractor. Our new extractor bypasses this barrier, providing the first explicit construction to go beyond sumset extraction.

0.23

Improved lower bounds for decomposable randomized encoding

cs.CC cs.CRcs.DM ·2026-09-16 ·Justin Holmgren, Kewen Wu
theory similarity 0.62
Abstract · 24 pages

A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection of encodings reveals $f(x_1,\ldots,x_n)$ and nothing else. DREs are widely used in efficient multiparty computation. Their main complexity measure is size, the total bit length of the local encodings. Yet the optimal DRE size remains poorly understood even for the $n$-bit OR function. We prove the first superlinear lower bound for OR and, more generally, for every non-periodic symmetric function. Under an additional symmetry assumption, we prove a sharp $Ω(n\log n)$ lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first $Ω(n^2)$ lower bound on DRE size for non-explicit Boolean functions.

0.46

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.62
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

XOR-Functions and Beyond in the Random Query Model

cs.DS ·2026-11-03 ·Sumegha Garg, Janani Sundaresan, Santhoshini Velusamy
theory similarity 0.61
Abstract · 62 pages, 6 figures

We study time--space tradeoffs for computing Boolean functions $f:\{0,1\}^n \to \{0,1\}$ in the random query model. On input $x$, a branching program receives independent samples $(i,x(i))$, where $i$ is uniform in $[n]$. We want to evaluate $f(x)$ while minimizing the width $2^S$ and the length $T$ of the branching program. There is a simple upper bound of $T = \tilde{O}(n)$, $S = O(n)$: coupon-collector shows that $\tilde{O}(n)$ samples suffice, and they can be stored in $O(n)$ space. Raz and Zhan (ITCS 2020) introduced this model and studied the zero-error setting. In the bounded-error setting, Dinur (SODA 2024) proved $TS = \tildeΩ(n \cdot inf[f])$, where $inf[f]$ is the total influence of $f$. For many functions with low influence such as Equality and Tribes, this lower bound can leave a substantial gap from the best known upper bounds. Our main result is a stronger lower bound of $T(S+\log T) = Ω(n \cdot sens[g])$ for any XOR-function $g(x,y)= f(x \oplus y)$, where $sens[g]$ is the sensitivity of $g$. Through simple corollaries, we get tight nearly-quadratic time--space lower bounds for Tribes and Equality, despite their low influence. Our proof introduces a new notion of information complexity tailored to the random query model along with a corresponding direct-sum argument which may be of independent interest. Dinur also proved a tight bound of $TS = Ω(n^2)$ for Majority, whose influence is only $Θ(\sqrt{n})$, and asked whether an alternative characterization of Boolean functions could give a unified proof of tight results for a broader class of functions, including Majority. We answer this open question by proving $TS = \tildeΩ(n \cdot dgn[f])$, where $dgn[f]$ is the degeneracy of the sensitivity graph of $f$ (for Majority, this is $Θ(n)$). We also prove that this bound is tight for all symmetric functions up to logarithmic factors.

0.37