2026-08-21T18:02:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27471 2026-08-21T14:42:41Z ddc:004 open_access

Sublinear Time Algorithms for Abelian Group Property Testing Bshouty, Nader H. Property testing Abelian group In this paper, we study the problems of abelian group property testing in two models. In the partially specified model (PS-model), the algorithm does not know the group size but can access randomly chosen elements of the group, along with the Cayley table of these elements, which provides the result of the binary operation for every pair of selected elements. In the stronger fully specified model (FS-model), the algorithm knows the size of the group and has access to all its elements and the Cayley table. In property testing of abelian group property, given a finite set G and oracle access to a binary operation *:G² → G, we aim to distinguish whether (G,*) is an abelian group or is ε-far from any abelian group over G. Using a novel approach, we present a tester in the PS-model (and consequently in the FS-model) that runs in time Õ(√{|G|} + 1/ε), improving upon the Goldreich-Tauber tester, which runs in time O(|G|/ε). Additionally, our tester improves another tester by Goldreich and Tauber that runs in time O(|G|²) and makes Õ(|G| + 1/ε) queries. We further extend our result to testing subclasses of abelian groups G that are closed under isomorphism. Specifically, if one can decide in time T whether an abelian group of the form ℤ_{m_1} × ⋯ × ℤ_{m_r} belongs to G, then there exists a tester for G that runs in time T+Õ(√{|G|} + 1/ε) and makes O(√{|G|} + 1/ε) queries. This result gives testers that run in time O(√{|G|} + 1/ε) for subclasses such as abelian groups of rank at most k, abelian p-groups, and vector spaces over ℤ_p. We then present two subclasses, G₁ and G₂, of abelian groups that are closed under isomorphism for which any tester for G₁ in the FS-model must run in time Ω(|G|^{1/4} + 1/ε), and any tester for G₂ in the PS-model must run in time Ω(√{|G|} + 1/ε), showing that our approach provides tight bounds for certain subclasses of abelian groups. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nader H. Bshouty 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.89 urn:nbn:de:0030-drops-274716 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.89 eng https://creativecommons.org/licenses/by/4.0/legalcode