×

Highly resilient correctors for polynomials. (English) Zbl 0767.68075

Summary: 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 a \(1/2+\delta\) fraction of its inputs \((\delta>0)\) into a randomized program that computes \(f\) correctly on every input with high probability. This shows that programs computing polynomials are “resilient” to a high fraction of errors. The resilience shown is better than that 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 consequences of this result is that the \(n\times n\) permanent is resilient to errors of up to \(1/2- p(n)\) for any polynomial \(p(n)\).

MSC:

68Q60 Specification and verification (program logics, model checking, etc.)
68N99 Theory of software
11T06 Polynomials over finite fields
68N01 General topics in the theory of software
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ar, S.; Lipton, R.; Rubinfeld, R.; Sudan, M., Reconstructing algebraic functions from mixed data, Manuscript (1992)
[2] Beaver, D.; Feigenbaum, J., Hiding instance in multioracle queries, (Proc. 7th Symp. on Theoritical Aspects of Computer Science. Proc. 7th Symp. on Theoritical Aspects of Computer Science, Lecture Notes in Computer Science, 415 (1990), Springer: Springer Berlin), 37-48 · Zbl 0733.68005
[3] Beaver, D.; Feigenbaum, J.; Kilian, J.; Rogaway, P., Security with low communication overhead, (Proc. Crypto ’90. Proc. Crypto ’90, Lecture Notes in Computer Science, 537 (1991), Springer: Springer Berlin), 62-76 · Zbl 0800.68416
[4] E. Berlekamp and L. Welch, Error correction of algebraic block codes, US Patent Number 4,633,470.; E. Berlekamp and L. Welch, Error correction of algebraic block codes, US Patent Number 4,633,470.
[5] Blum, M.; Luby, M.; Rubinfeld, R., Self-testing/correcting with applications to numerical problems, Proc. 22nd ACM Symp. on Theory of Computing, 73-83 (1990)
[6] Feige, U.; Lund, C., On the hardness of computing the permanent of random matrices, Proc. 24th ACM Symp. on Theory of Computing, 643-654 (1992)
[7] Gemmell, P.; Lipton, R.; Rubinfeld, R.; Sudan, M.; Wigderson, A., Self-testing/correcting for polynomials and for approximate functions, Proc. 23rd ACM Symp. on Theory of Computing, 32-42 (1991)
[8] Lipton, R., New directions in testing, (Distributed Computing and Cryptography. Distributed Computing and Cryptography, DIMACS Series in Discrete Mathematics and Theoritical Computer Science, 2 (1991), American Mathematical Society: American Mathematical Society Providence, RI), 191-202
[9] Luby, M., A simple parallel algorithm for the minimal independent set problem, SIAM J. Comput., 15, 1036-1053 (1986) · Zbl 0619.68058
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.