Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR23-214 | 2nd January 2024 17:44

On Testing Group Properties

RSS-Feed




Revision #1
Authors: Oded Goldreich, Laliv Tauber
Accepted on: 2nd January 2024 17:44
Downloads: 68
Keywords: 


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})$.



Changes to previous version:

Added suggestion for future directions (Sec 1.2) and a lower bound (Thm 1.6 and Sec 5).


Paper:

TR23-214 | 31st December 2023 10:35

On Testing Group Properties





TR23-214
Authors: Oded Goldreich, Laliv Tauber
Publication: 31st December 2023 10:35
Downloads: 123
Keywords: 


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})$.



ISSN 1433-8092 | Imprint