A pseudo-deterministic NC algorithm for a search problem is an RNC algorithm that, for a given input, outputs a fixed solution with high probability. In this talk, we describe a pseudo-deterministic NC algorithm for the linear matroid intersection problem. Our work strengthens the RNC algorithm for the linear matroid intersection given by Narayanan, Saran and Vazirani (NSV'94). It also generalizes the pseudo-deterministic NC algorithm for the bipartite matching (due to Goldwasser and Grossman 2017) to linear matroid intersection.
It is a joint work with Rohit Gurjar.
