Peter S. Gemmell and Madhu Sudan

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-92-661

, 1992

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-661.pdf

We consider the problem of correcting programs that compute multivariate polynomials over large finite fields and give an efficient procedure to transform any program that computes a multivariate polynomial <i>f</i> correctly on 1/2 + delta fraction of its input (delta > 0) into a randomized program computing polynomials are "resilient" to a high fraction of errors. The resilience shown in this paper is better that those of the previously known correction procedures, and is close to the information theoretic optimum. The running time of the correction procedure is polynomial in the degree of <i>f</i>, the number of variables, and 1 / delta, where calls to the incorrect program are assessed a unit cost per call. An important consequence of this result is that the <i>n</i> x <i>n</i> permanent is resilient to errors of up to 1/2 - <i>p</i>(<i>n</i>) for any polynomial <i>p</i>(<i>n</i>).

---

BibTeX citation:

@techreport{Gemmell:CSD-92-661,
    Author= {Gemmell, Peter S. and Sudan, Madhu},
    Title= {Highly Resilient Correctors for Polynomials},
    Year= {1992},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6146.html},
    Number= {UCB/CSD-92-661},
    Abstract= {We consider the problem of correcting programs that compute multivariate polynomials over large finite fields and give an efficient procedure to transform any program that computes a multivariate polynomial <i>f</i> correctly on 1/2 + delta fraction of its input (delta > 0) into a randomized program computing polynomials are "resilient" to a high fraction of errors. The resilience shown in this paper is better that those of the previously known correction procedures, and is close to the information theoretic optimum. The running time of the correction procedure is polynomial in the degree of <i>f</i>, the number of variables, and 1 / delta, where calls to the incorrect program are assessed a unit cost per call. An important consequence of this result is that the <i>n</i> x <i>n</i> permanent is resilient to errors of up to 1/2 - <i>p</i>(<i>n</i>) for any polynomial <i>p</i>(<i>n</i>).},
}

EndNote citation:

%0 Report
%A Gemmell, Peter S. 
%A Sudan, Madhu 
%T Highly Resilient Correctors for Polynomials
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-661
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6146.html
%F Gemmell:CSD-92-661