咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Robust characterizations of po... 收藏

Robust characterizations of polynomials with applications to program testing

有到程序测试的应用程序的多项式的柔韧的描述

作     者:Rubinfeld, R Sudan, M 

作者机构:PRINCETON UNIV PRINCETON NJ 08544 USA IBM CORP THOMAS J WATSON RES CTR YORKTOWN HTS NY 10598 USA UNIV CALIF BERKELEY BERKELEY CA 94720 USA 

出 版 物:《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期:1996年第25卷第2期

页      面:252-271页

核心收录:

学科分类:07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术(可授工学、理学学位)] 

主  题:coding theory program correctness low-degree polynomial testing 

摘      要:The study of self-testing and self-correcting programs leads to the search for robust characterizations of functions. Here the authors make this notion precise and show such a characterization for polynomials. From this characterization, the authors get the following applications. Simple and efficient self-testers for polynomial functions are constructed. The characterizations provide results in the area of coding theory by giving extremely fast and efficient error-detecting schemes for some well-known codes. This error-detection scheme plays a crucial role in subsequent results on the hardness of approximating some NP-optimization problems.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分