Low rank matrix completion (LRMC) has received tremendous attention in recent years.  The low rank assumption means that the columns (or rows) of the matrix to be completed are points on a low-dimensional linear variety.  This work extends this thinking to cases where the columns are points on low-dimensional nonlinear algebraic varieties, a problem which we call Low Algebraic-Dimension Matrix Completion (LADMC). We discuss two optimization approaches to this problem, one kernelized algorithm and one that leverages existing LRMC techniques on a tensorized representation of the data. We also provide a formal mathematical justification for the success of our method and experimental results showing that the new approach outperforms existing state-of-the-art methods for matrix completion in many situations.