Reconstructing Curves in Three (and Higher) Dimensional Space from Noisy Data

We consider the task of reconstructing a curve in constant dimensional space from noisy data. We consider curves of the form
C = { (x, y₁, . . . ,y_c) | y_j = p_j(x) }, where the p_j's are polynomials of low degree. Given n points in (c+1)-dimensional space,
such that t of these lie on some such unknown curve C while the other n -- t are chosen randomly and independently, we give an
efficient algorithm to recover the curve C and the identity of the good points. The success of our algorithm depends on the relation
between n, t, c and the degree of the curve C, requiring t = W ((ndeg(C))^1/(c+1)). This generalizes, in the restricted setting of random
errors, the work of Sudan (J. Complexity, 1997) and of Guruswami and Sudan (IEEE Trans. Inf. Th. 1999) that considered the case c = 1.