Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets
Zeyu Guo, Roshan Raj, Chong Shangguan, Zihan Zhang · 2026
Read Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets by Zeyu Guo, Roshan Raj, Chong Shangguan, Zihan Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-13431.txt.
Introduction
Guo and three colleagues construct, explicitly rather than by existence argument, several objects used in pseudorandomness. These are lossless rank extractors. They also build weak subspace designs and strong blocking sets over finite fields. Their focus is the small-field case. There, field size depends only on rank or codimension, not on ambient dimension. They give the first explicit lossless extractors and weak designs for small rank, with near-best parameters, and blocking sets matching the best non-explicit bounds.
Catalog record
| CREATOR | Zeyu Guo, Roshan Raj, Chong Shangguan, Zihan Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 130317 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.13431
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Explicit Rank Extractors and Subspace Designs via Function Fields, with Applications to Strong Blocking Sets Zeyu Guo, Roshan Raj, Chong Shangguan, Zihan Zhang Abstract We give new explicit constructions of several fundamental objects in linear-algebraic pseudorandomness and combinatorics, including lossless rank extractors, weak subspace designs, and strong s s -blocking sets over finite fields. Our focus is on the small-field regime, where the field size depends only on a secondary parameter (such as the rank or codimension) and is independent of the ambient dimension. This regime is central to several applications, yet remains poorly understood from the perspective of explicit constructions. In this setting, we obtain the first explicit constructions of lossless rank extractors and weak subspace designs for r ≪ k r\ll k , where r r denotes the rank (or codimension), over finite fields 𝔽 q \mathbb{F}_{q} with q ≥ poly ( r ) q\geq\mathrm{poly}(r) and q q non-prime, with near-optimal parameters. For other finite fields, including prime fields and small fields, we obtain weaker but still improved bounds. As a consequence, we construct explicit strong s s -blocking sets in PG ( k − 1 , q ) \mathrm{PG}(k-1,q) of size O ( s ( k − s ) q s ) O(s(k-s)q^{s}) for all sufficiently large non-prime fields q ≥ poly ( s ) q\geq\mathrm{poly}(s) , matching the best known non-explicit bounds up to constant factors. This significantly improves the previous best bound 2 O ( s 2 log s ) q s k 2^{O(s^{2}\log s)}q^{s}k of Bishnoi and Tomon (Combinatorica, 2026), which requires q ≥ 2 Ω ( s ) q\geq 2^{\Omega(s)} . Our approach is primarily algebraic, combining techniques from function fields and polynomial identity testing. In addition, we develop a complementary Fourier-analytic framework based on ε \varepsilon -biased sets, which yields improved explicit constructions of strong s s -blocking sets over small fields. 1 Introduction A central theme in theoretical computer science is the explicit construction of combinatorial and algebraic objects that match the guarantees of the probabilistic method. In recent years, a rich theory of linear-algebraic pseudorandomness has emerged, focusing on structured collections of linear maps that behave like random ones with respect to rank and dimension. Prominent examples include lossless rank extractors, subspace designs, and dimension expanders, which play a key role in polynomial identity testing, coding theory, and derandomization. A recurring challenge in this area is to obtain explicit constructions over small finite fields . While the probabilistic method often yields near-optimal parameters over any field, known explicit constructions typically require the field size to grow with the ambient dimension. Bridging this gap, especially in the regime where the field size depends only on a small parameter, is a central open problem with numerous applications. In this work, we study this problem for several natural objects in linear-algebraic pseudorandomness and combinatorics, including lossless rank extractors, weak subspace designs, and strong s -blocking sets. Our main algebraic approach uses function fields and polynomial identity testing, and for strong s -blocking sets we also develop a complementary Fourier-analytic approach via \varepsilon -biased sets. Lossless rank condensers and extractors. A central object in the theory of “linear-algebraic pseudorandomness” [ 17 ] is the notion of (seeded) lossless rank condensers and extractors [ 23 , 19 , 18 , 17 ] . Definition 1.1 (Lossless rank condensers and extractors) . Let r\leq t\leq k be positive integers. A finite collection \mathcal{E}=\{E_{i}\}_{i=1}^{n}\subseteq\mathbb{F}^{t\times k} of matrices over a field \mathbb{F} is called a (k,r,t,L) lossless rank condenser over \mathbb{F} if for every matrix M\in\mathbb{F}^{k\times r} of rank r , the number of indices i\in[n] for which \mathrm{rank}(E_{i}M)<r is at most L . We call n the size of \mathcal{E} . When r=t , which is optimal, such an object is called a (k,r,L) lossless rank extractor. Explicit lossless rank extractors of small size were first constructed by Gabizon and Raz [ 23 ] , who used them to obtain explicit affine extractors over large fields. In particular, they gave explicit (k,r,kr^{2}) lossless rank extractors of any size n\leq q . Forbes and Shpilka [ 19 ] gave a different construction over fields \mathbb{F} with |\mathbb{F}|>k using Vandermonde matrices, improving the parameter L to kr . Forbes, Saptharishi, and Shpilka [ 18 ] refined the analysis of this construction and achieved L=r(k-r) , which is optimal over algebraically closed fields (see [ 16 , 28 , 9 ] ). It is also known that explicit lossless rank condensers can be constructed from classical Wronskians [ 30 , 18 ] . Beyond their role in constructing affine extractors [ 23 ] , lossless rank condensers and extractors play a central role in polynomial identity testing for various models, including depth-3 arithmetic circuits [ 41 , 42 , 47 , 46 ] and read-once oblivious arithmetic branching programs [ 20 , 18 , 1 ] . For further applications and a comprehensive discussion, see [ 17 ] . Nonlinear variants of these objects have also been studied. Dvir, Gabizon, and Wigderson [ 13 ] introduced deterministic rank extractors for polynomial sources and gave explicit constructions. Guo, Volk, Jalan, and Zuckerman [ 27 ] extended this line of work by defining deterministic rank condensers and extractors for varieties as dimension-preserving maps, yielding explicit constructions for algebraic sources that generalize [ 13 , 14 ] . They also observed that the objects in Definition 1 can be viewed as linear seeded rank condensers and extractors for varieties. Finally, Guo [ 28 ] introduced variety evasive subspace families as a nonlinear generalization, with further applications to polynomial identity testing. In this paper, we focus on explicit lossless rank extractors over a finite field \mathbb{F}_{q} , i.e., the case r=t and \mathbb{F}=\mathbb{F}_{q} in Definition 1 . This setting is crucial for many of the applications discussed above. From a non-explicit perspective, the probabilistic method shows that (k,r,L) lossless rank extractors of small size exist over any finite field \mathbb{F}_{q} , with L=\mathrm{poly}(k) (and in fact L=O(r(k-r)) ; see Theorem A.1 ). However, known explicit constructions such as [ 23 , 19 ] achieve such parameters only when the field size is sufficiently large. To avoid trivialities, we assume L<n , since otherwise one could allow \mathrm{rank}(E_{i}M)<r for all i\in[n] . Under this assumption, the constructions in [ 23 , 19 ] require q\geq n , and hence q>L . More concretely, this gives q>kr^{2} in [ 23 ] and q>r(k-r) in [ 19 ] . In addition, the construction in [ 19 ] requires q>k , as it relies on the existence of an element \gamma\in\mathbb{F}_{q}^{\times} whose multiplicative order is at least k . A natural approach to constructing lossless rank extractors over small fields is via concatenation or field-reduction techniques. Indeed, [ 17 , Proposition 8.5] shows that a (k,r,t,L) lossless rank condenser over \mathbb{F}_{q^{d}} can be converted into a (k,r,dt,L) lossless rank condenser over \mathbb{F}_{q} . However, unless d=1 , this transformation does not preserve the lossless rank extractor property, as it necessarily increases the output dimension to dt>r . This motivates the problem of constructing explicit lossless rank extractors over small fields. In particular, we ask: Question A