Subspace Designs:
A Universal Tool for Derandomization

A subspace design is a collection of large linear subspaces whose members, on average, have small intersection dimension with every low-dimensional subspace. Originally introduced as a tool for constructing list-decodable codes, subspace designs have emerged as a useful primitive in linear-algebraic pseudorandomness, and a unifying derandomization tool in coding theory.

Intriguingly, near-optimal subspace designs are themselves constructed from algebraic codes such as folded Reed–Solomon or univariate multiplicity codes. Recent work reveals a powerful reverse connection: the subspace-design property explains why these highly structured codes admit optimal list-size bounds for list decoding and proximity gaps approaching the optimal radius. More broadly, near-optimal subspace-design codes inherit, up to an arbitrarily small loss in rate, the guarantees of random linear codes for local coordinate-wise linear (LCL) properties—a general framework encompassing list decoding and list recovery. Recent work has shown that by capturing bipartite perfect matching as a LCL property, one can obtain a deterministic NC algorithm for bipartite perfect matching using subspace designs.

The talk will survey this circle of ideas. It will introduce the definitions, constructions, and connections pertaining to subspace designs, and set the stage for follow-up talks in the workshop on the various aspects mentioned above.

I will present Yeyuan Chen and Zihan Zhang's breakthrough results showing optimal list-decoding of folded Reed-Solomon and more generally subspace-design codes. I will connect their techniques to previous works in the area on optimal list-decoding of random linear and random Reed-Solomon codes due to Alrabiah, Guo, Guruswami, Li, and Zhang.

When many points on an affine line are close to a linear code, must the entire line be close to the code? Proximity gaps capture this local-to-global phenomenon and play an important role in interactive oracle proofs and their cryptographic applications.

In this talk, I will discuss how line decoding, a notion introduced by Goyal and Guruswami, connects proximity gaps to the framework of local properties and subspace designs. Rather than asking only whether each point has a nearby codeword, line decoding asks whether many of these codewords themselves lie on a line with the same parameterization. I will explain how to view line decoding as a local property and how to establish it via pruning arguments building on the work of Ashvinkumar, Habib, and Srivastava. Together, these ideas yield near-capacity proximity gaps for subspace-design codes and random codes.

Based on joint work with Rohan Goyal, Venkatesan Guruswami, and Mary Wootters.

In coding theory, the problem of list recovery asks one to find all codewords $c$ of a given code $C$ which such that at least $1-\rho$ fraction of the symbols of $c$ lie in some predetermined set of $\ell$ symbols for each coordinate of the code. A key question is bounding the maximum possible list size $L$ of such codewords for the given code $C$.

In this talk, I will present novel combinatorial upper bounds on the list recoverability of various families of linear and folded linear codes, including random linear codes, random Reed–Solomon codes, explicit folded Reed–Solomon codes, and explicit univariate multiplicity codes. In the zero-error regime our upper bound matches known lower bounds. The primary technique is a novel application of a discrete entropic Brascamp–Lieb inequality to the problem of list recovery, allowing us to relate the local structure of each coordinate with the global structure of the recovered list.

Based on joint work with Yeyuan Chen, Manik Dhar, and Zihan Zhang