Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion

Maurice Jansen

In (Kabanets, Impagliazzo, 2004) it is shown how to decide the circuit polynomial identity testing problem (CPIT) in deterministic subexponential time, assuming hardness of some ex…