Subspace arrangements, graph rigidity and derandomization through submodular optimization

Orit E. Raz, Avi Wigderson

This paper presents a deterministic, strongly polynomial time algorithm for computing the matrix rank for a class of symbolic matrices (whose entries are polynomials over a field).…