Following Ergun et al. (JCSS 2000), we consider testing group properties and focus on the problem of testing whether a binary operation is a group operation. That is, given a finite set S and oracle access to a function \(f:S\times S \rightarrow S\) , we wish to distinguish the case that (S, f) constitutes a group from the case that f is far from any function g such that (S, g) is a group. Our main result is a tester of running-time \({\widetilde{O}}(|S|)\) , which improves over the tester of Ergun et al. that has running time \({\widetilde{O}}(|S|^{3/2})\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Testing Group Properties

  • Oded Goldreich,
  • Laliv Tauber

摘要

Following Ergun et al. (JCSS 2000), we consider testing group properties and focus on the problem of testing whether a binary operation is a group operation. That is, given a finite set S and oracle access to a function \(f:S\times S \rightarrow S\) , we wish to distinguish the case that (S, f) constitutes a group from the case that f is far from any function g such that (S, g) is a group. Our main result is a tester of running-time \({\widetilde{O}}(|S|)\) , which improves over the tester of Ergun et al. that has running time \({\widetilde{O}}(|S|^{3/2})\) .