Das, BireswarBireswarDasSharma, ShivduttShivduttSharma2025-08-312025-08-312021-01-01[9783030682101]10.1007/978-3-030-68211-8_82-s2.0-85102756771https://d8.irins.org/handle/IITG2025/25577A group with n elements can be stored using O(n²) space via its Cayley table which can answer a group multiplication query in O(1 ) time. Information theoretically it needs Ω(nlog n) bits or Ω(n) words in word-RAM model just to store a group (Farzan and Munro, ISSAC 2006). For functions s, t: N⟶ R<inf>≥ 0</inf>, we say that a data structure is an (O(s), O(t) ) -data structure if it uses O(s) space and answers a query in O(t) time. Except for cyclic groups it was not known if we can design (O(n), O(1 ) ) -data structure for interesting classes of groups. In this paper, we show that there exist (O(n), O(1 ) ) -data structures for several classes of groups and for any ring and thus achieve information theoretic lower bound asymptotically. More precisely, we show that there exist (O(n), O(1 ) ) -data structures for the following algebraic structures with n elements: Dedekind groups: This class contains abelian groups, Hamiltonian groups.Groups whose indecomposable factors admit (O(n), O(1 ) ) -data structures.Groups whose indecomposable factors are strongly indecomposable.Groups defined as a semidirect product of groups that admit (O(n), O(1 ) ) -data structures.Finite rings.falseAbelian groups | Compact data structures | Dedekind groups | Finite rings | Linear space representations | Strongly indecomposable groups | Theoretical computer scienceConference Paper1611334990-10220212cpBook Series1