On Testing Group Properties

Webpage for a paper by Oded Goldreich and Laliv Tauber


Abstract

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 \to 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 $\tildeO(|S|)$, which improves over the tester of Ergun et al. that has running time $\tildeO(|S|^{3/2})$.

Material available on-line


Back to either Oded Goldreich's homepage or general list of papers.