Estimating the Distance from Testable Affine-Invariant Properties
Estimating the Distance from Testable Affine-Invariant Properties
复制标题
估计可测试仿射不变属性的距离
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Shachar Lovett
中科院分区：
文献类型：
--
作者：
Hamed Hatami;Shachar Lovett
设P是常长有限域上多元函数的仿射不变性质。我们表明，如果P是本地可测试的查询数量恒定，那么可以估计的距离函数f从P与查询的数量恒定。这是以前未知的，即使是简单的属性，如三次多项式的二进制字段。我们的测试很简单：将f限制为常数维仿射子空间，并测量其与P的距离。我们表明，通过选择足够大的维度，这很有可能逼近f与P的全局距离。该分析结合了Fischer和纽曼的方法[SIAM J. Comp 2007]，他们为图形属性建立了类似的结果，并使用最近开发的高阶傅里叶分析工具，特别是Bhattacharyya等人[STOC 2013]中开发的那些。
Let P be an affine invariant property of multivariate functions over a constant size finite field. We show that if P is locally testable with a constant number of queries, then one can estimate the distance of a function f from P with a constant number of queries. This was previously unknown even for simple properties such as cubic polynomials over the binary field. Our test is simple: take a restriction of f to a constant dimensional affine subspace, and measure its distance from P. We show that by choosing the dimension large enough, this approximates with high probability the global distance of f from P. The analysis combines the approach of Fischer and Newman [SIAM J. Comp 2007] who established a similar result for graph properties, with recently developed tools in higher order Fourier analysis, in particular those developed in Bhattacharyya et al. [STOC 2013].