Reconstructing randomly sampled multivariate polynomials from highly noisy data
Hal Wasserman · 1998
Sudan and others have considered the problem of reconstructing a bounded-degree polynomial f : F k ! F from n data-points, only t of which are guaranteed to be consistent with f . For t n=2, the solution may not be unique; but it may be possible to find a small set of candidates for f . Here we extend this work, proving results including the following: Pick ~x (1) ; : : : ; ~x (n) 2 u F k . Generate data-points (~x (1) ; f(~x (1) )); : : : ; (~x (n) ; f(~x (n) )), and allow an adversary to corrupt any n \\Gamma t of them. We require t to be greater than a bound on the order of n k k+1 ; we also require a lower-bound on jF j. Then, with high probability, we may reconstruct from the corrupted data a small set of candidates for f . Our results improve on past research in several respects. First, our bound on t is lower. Second, we allow for weaker restrictions on the distribution of ~x (1) ; : : : ; ~x (n) : in particular, as in the previous paragraph, we allow fo...