在任意随机样本分布下我们给出一困难性结论
我们给出在随机样本模型下函数属性测试的一些困难性结论
我们给出在样本均匀分布下的测试困难性结论
关键词: 属性测试; 半空间的交; 弱伪随机函数 Lu Haining * ( School of Information Security Engineering, Shanghai Jiao Tong University, Shanghai 200240
该结论的一个推论是:半空间的交集合在样本分布任意下不可测试
在弱伪随机函数存在假设下
) Abstract: This note presents some hardness results of testing Boolean functions in the random example model
First we present a hardness of testing under arbitrary distributions
As a consequence, we obtain that the class of intersections of halfspaces cannot be tested in arbitrary distributions
Second we present a hardness result of testing under the uniform distribution when assuming weak pseudorandom functions
Keywords: Property Testing; Intersection of Halfspaces; Weak Pseudorandom Functions 下载PDF阅读器 PDF全文下载: 初稿 ( 0 ) 作者简介: Lu Haining(1979-), male, Ph
D
candidate in School of Information Security Engineering of Shanghai Jiao Tong University
He received an M
E
degree in 2004, and a B
Eng
degree in 2001, both in the Department of Computer Science & Engineering from Shanghai Jiao Tong University
His current research is in cryptography based cloud security and network security
通信联系人: 【收录情况】 中国科技论文在线: 陆海宁
关于函数属性测试困难性的注记[EB/OL]
北京:中国科技论文在线
总览 评价 陆海宁 * ( 上海交通大学 信息安全工程学院, 上海 200240
【详情见下载】