Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion

Maurice Jansen
Kabanets and Impagliazzo \cite{KaIm04} show how to decide the circuit polynomial identity testing problem (CPIT) in deterministic subexponential time, assuming hardness of some explicit multilinear polynomial family $\{f_m\}_{m \geq 1}$ for arithmetic circuits. In this paper, a special case of CPIT is considered, namely non-singular matrix completion ($\NSMC$) under a low-individual-degree promise. For this subclass of problems it is shown how to obtain the same deterministic time bound, using a weaker assumption in terms of...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.