Title :
Learning polynomials with queries: The highly noisy case
Author :
Goldreich, Oded ; Rubinfeld, Ronitt ; Sudan, Madhu
Author_Institution :
Weizmann Inst. of Sci., Rehovot, Israel
Abstract :
Given a function f mappping n-variate inputs from a finite field F into F, we consider the task of reconstructing a list of all n-variate degree d polynomials which agree with f on a tiny but non-negligible fraction, δ, of the input space. We give a randomized algorithm for solving this task which accesses f as a black box and runs in time polynomial in 1/δ, n and exponential in d, provided δ is Ω(√(d/|F|)). For the special case when d=1, we solve this problem for all εder/=δ-1/|F|>0. In this case the running time of our algorithm generalizes a previously known algorithm, due to Goldreich and Levin, that solves this task for the case when F=GF(2) (and d=1)
Keywords :
explanation; learning (artificial intelligence); polynomials; randomised algorithms; finite field; highly noisy case; n-variate degree d polynomials; n-variate inputs; polynomials with queries learning; randomized algorithm; running time; Argon; Computer aided software engineering; Computer science; Galois fields; Polynomials; Random processes; Read only memory;
Conference_Titel :
Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
Conference_Location :
Milwaukee, WI
Print_ISBN :
0-8186-7183-1
DOI :
10.1109/SFCS.1995.492485