The following question arises from the study of quantum error correction, and high-dimensional expanders:
Is there an algorithm that for given numbers $n>0,d≤n,r≤n$ samples uniformly a linear operator $:\partial: F_2^n \to F_2^n$ , such that $\partial^2 = 0$, and each row/column of ∂ has Hamming weight at most d, and rank(∂)=r?
Note, that for d = n, i.e. boundary operators that are not sparse, the question can be solved in a straightforward manner as outlined in a paper of Bravyi and Hastings [Homological Product Codes]: one considers some fixed matrix Q - such that dim(im(Q))=r, and im(Q)⊆ker(Q) - and then the distribution is the set of matrices $A Q A^{-1}$ where A is a random invertible matrix over $F_2^n$.
Hence, the question is, whether the extra sparsity condition makes the problem intractable or not.
The importance of the question relates to the quantum LDPC conjecture: ideally, we would want to find such a procedure for $d=O_n(1)$. A solution to this question would at least imply that there exists some candidate ensemble where we can find good quantum LDPC codes - specifically of a type called CSS codes.
