A Unified Framework for Testing Linear-Invariant Properties
A Unified Framework for Testing Linear-Invariant Properties
复制标题
测试线性不变属性的统一框架
DOI：
10.1002/rsa.20507
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
A. Shapira
中科院分区：
文献类型：
--
作者：
Arnab Bhattacharyya;Elena Grigorescu;A. Shapira
最近有一系列的论文致力于理解布尔函数的性质的可测性和关于域的变换的性质的不变性之间的关系。关于F_2-线性变换的不变性可以说是超立方体上布尔函数自然性质的最常见的对称性。因此，寻找线性不变性质可测性的充分必要条件是一个重要的目标。最近对苏丹的一项调查明确提出这是一个悬而未决的问题。我们得到以下结果：1.我们表明，每一个线性不变的属性，其特征在于禁止诱导解决方案（可能是无限的）一组线性方程组可以测试与单侧误差。2.我们表明，每一个线性不变的属性，可以测试单侧误差的特点是禁止诱导解决方案的一组（可能是无限的）{\em系统}的线性方程组。我们猜想我们的结果可以推广到线性方程组。我们进一步证明了这个猜想的有效性将具有以下含义：1。这意味着每个在线性子空间的限制下封闭的线性不变性质都是可测试的，具有单侧误差。这样的结果将统一几个以前的结果测试布尔函数，如可测性的低次多项式和傅立叶维数。2.这意味着一个线性不变性质${\cal P}$是可检验的，有单侧误差当且仅当} ${\cal P}$在线性子空间的限制下是封闭的，从而解决了苏丹问题。
There has been a sequence of recent papers devoted to understanding the relation between the testability of properties of Boolean functions and the invariance of the properties with respect to transformations of the domain. Invariance with respect to F_2-linear transformations is arguably the most common such symmetry for natural properties of Boolean functions on the hypercube. Hence, it is an important goal to find necessary and sufficient conditions for testability of linear-invariant properties. This is explicitly posed as an open problem in a recent survey of Sudan. We obtain the following results: 1. We show that every linear-invariant property that can be characterized by forbidding induced solutions to a (possibly infinite) set of linear equations can be tested with one-sided error. 2. We show that every linear-invariant property that can be tested with one-sided error can be characterized by forbidding induced solutions to a (possibly infinite) set of {\em systems} of linear equations. We conjecture that our result from item (1) can be extended to cover systems of linear equations. We further show that the validity of this conjecture would have the following implications: 1. It would imply that every linear-invariant property that is closed under restrictions to linear subspaces is testable with one-sided error. Such a result would unify several previous results on testing Boolean functions, such as the testability of low-degree polynomials and of Fourier dimensionality. 2. It would imply that a linear-invariant property ${\cal P}$ is testable with one-sided error {\bf if and only if} ${\cal P}$ is closed under restrictions to linear subspaces, thus resolving Sudan's problem.
普通树木着色的芒硝动力学混合时间
影响因子：
1
作者：
Goldberg L
通讯作者：
Goldberg L