Local Property Restoring
Local Property Restoring
复制标题
当地财产恢复
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Zvika Brakerski
中科院分区：
文献类型：
--
作者：
Zvika Brakerski
在本文中，我们介绍了属性的本地还原的新概念。接近属性，例如函数单调性或图形双方。在错误校正代码的情况下，既要接近原始功能，又对应于本地自我校正。为了在密集图模型中提供属性的修复器：两肢和ρ-clique，以及功能单调性。
In this paper we present the new notion of local restoring of properties. A restorer gets implicit access, in the form of oracle queries, to a function (which may correspond to an object such as a graph, a code or a matrix) that is close to having a property, such as function monotonicity or graph bipartiteness. The restorer then, using a small number of queries to the function, can locally compute the value of a “corrected” function in any desired point. The corrected function is required to be both close to the original function and strictly have the property. In the case of error correcting codes, this corresponds to local self-correcting. Here we extend the definition and study for general functions and properties. We define the new notion and go on to give restorers for properties in the dense graph model: Bipartiteness and ρ-Clique, and for function monotonicity. We also show some general relations between property restoring and other notions such as property testing and tolerant property testing.