Algebraic-Geometric Parvaresh--Vardy Subspace Designs and Rank Condensers
Abstract
A subspace design is a collection of subspaces H1,…,Hn of 𝔽qk with the property that no low-dimensional subspace W intersects the collection "too much". Subspace designs and related objects in linear-algebraic pseudorandomness have found a broad range of applications, ranging from list decoding, to derandomizing algorithms. We construct explicit strong subspace designs over every finite field. In the extremal case where the co-dimension t of each Hi is equal to the dimension of W, for every constant field size our construction attains n=Ω(k) and matches the probabilistic intersection bound up to a constant factor. All previous constructions required the field size to grow with t (or k). Our subspace designs also imply new construction of rank condensers over arbitrary finite fields. This result is the first to achieve an optimal dependence on k while maintaining both a constant output entropy rate and a constant field size. As an application, we construct lossless rank extractors for linear sources of rank r, for all r < q, with parameters matching those of Guo, Raj, Shangguan and Zhang (FOCS '26), thereby generalizing their result to prime fields and smaller field sizes. Our construction is based on an algebraic-geometric version of the Parvaresh-Vardy codes (Parvaresh-Vardy FOCS '05, Guruswami ECCC '05), extending the framework underlying the condensers of Guruswami, Umans and Vadhan (JACM '09). We view our construction as a linear-algebraic analysis - tailored to affine sources - of the GUV construction, generalized to functions over algebraic curves. More specifically, inspired by Ta-Shma and Umans (CCC 12') we develop a two-level evaluation scheme, where we first evaluate a function on a curve at extension-field points, and then evaluate a corresponding affine-linear polynomial to obtain outputs over the base field.
Related
- Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding
- Geometric Fluctuations of the sinΘ Distance in High-Dimensional Principal Subspace Estimation
- The algebraic and geometric classification of semi-alternative superalgebras
- G-ORACLE: A Fast Geometric Method To Explore All Near-Optimal Designs for Energy Systems
- Étale Fundamental Groups: a geometric and topological approach to fundamental groups in algebraic geometry
BibTeX
@misc{cohen2026algebraicgeometric,
title = {{Algebraic-Geometric Parvaresh--Vardy Subspace Designs and Rank Condensers}},
author = {Gil Cohen and Dean Doron and Noam Goldgraber},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32834},
eprint = {2609.32834},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32834},
note = {CC0},
}
RIS
TY - UNPB
TI - Algebraic-Geometric Parvaresh--Vardy Subspace Designs and Rank Condensers
AU - Gil Cohen
AU - Dean Doron
AU - Noam Goldgraber
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32834
UR - https://arxiv.org/abs/2609.32834
AB - A subspace design is a collection of subspaces H_1,…,H_n of 𝔽_q^k with the property that no low-dimensional subspace W intersects the collection "too much". Subspace designs and related objects in linear-algebraic pseudorandomness have found a broad range of applications, ranging from list decoding, to derandomizing algorithms. We construct explicit strong subspace designs over every finite field. In the extremal case where the co-dimension t of each H_i is equal to the dimension of W, for every constant field size our construction attains n=Ω(k) and matches the probabilistic intersection bound up to a constant factor. All previous constructions required the field size to grow with t (or k). Our subspace designs also imply new construction of rank condensers over arbitrary finite fields. This result is the first to achieve an optimal dependence on k while maintaining both a constant output entropy rate and a constant field size. As an application, we construct lossless rank extractors for linear sources of rank r, for all r < q, with parameters matching those of Guo, Raj, Shangguan and Zhang (FOCS '26), thereby generalizing their result to prime fields and smaller field sizes. Our construction is based on an algebraic-geometric version of the Parvaresh-Vardy codes (Parvaresh-Vardy FOCS '05, Guruswami ECCC '05), extending the framework underlying the condensers of Guruswami, Umans and Vadhan (JACM '09). We view our construction as a linear-algebraic analysis - tailored to affine sources - of the GUV construction, generalized to functions over algebraic curves. More specifically, inspired by Ta-Shma and Umans (CCC 12') we develop a two-level evaluation scheme, where we first evaluate a function on a curve at extension-field points, and then evaluate a corresponding affine-linear polynomial to obtain outputs over the base field.
ER -