Peter S. Gemmell and Madhu Sudan

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-661
December 1991

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 f 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 f, 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 n x n permanent is resilient to errors of up to 1/2 - p( n) for any polynomial p( n).

BibTeX citation:

@techreport{Gemmell:CSD-92-661,
    Author = {Gemmell, Peter S. and Sudan, Madhu},
    Title = {Highly Resilient Correctors for Polynomials},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1991},
    Month = {Dec},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/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 1991
%@ UCB/CSD-92-661
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1991/6146.html
%F Gemmell:CSD-92-661