On Testing Group Properties
摘要
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})\) .