Browsing by Author "Sharma, Shivdutt"

A 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≥ 0, 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.

A finite group of order n can be represented by its Cayley table. In the word-RAM model the Cayley table of a group of order n can be stored using O(n²) words and can be used to answer a multiplication query in constant time. It is interesting to ask if we can design a data structure to store a group of order n that uses o(n²) space but can still answer a multiplication query in constant time. Das et al. (J Comput Syst Sci 114:137–146, 2020) showed that for any finite group G of order n and for any δ∈[1/logn,1], a data structure can be constructed for G that uses O(n^1+δ/δ) space and answers a multiplication query in time O(1/δ). Farzan and Munro (ISSAC, 2006) gave an information theoretic lower bound of Ω(n) on the number of words to store a group of order n. We design a constant query-time data structure that can store any finite group using O(n) words where n is the order of the group. Since our data structure achieves the information theoretic lower bound and answers queries in constant time, it is optimal in both space usage and query-time. A crucial step in the process is essentially to design linear space and constant query-time data structures for nonabelian simple groups. The data structures for nonabelian simple groups are designed using a lemma that we prove using the Classification Theorem for Finite Simple Groups.

A finite group of order n can be represented by its Cayley table. In the word-RAM model the Cayley table of a group of order n can be stored using O(n²) words and can be used to answer a multiplication query in constant time. It is interesting to ask if we can design a data structure to store a group of order n that uses o(n²) space but can still answer a multiplication query in constant time. We design a constant query-time data structure that can store any finite group using O(n) words where n is the order of the group. Farzan and Munro (ISSAC 2006) gave an information theoretic lower bound of Ω(n) on the number of words to store a group of order n. Since our data structure achieves this lower bound and answers queries in constant time, it is optimal in both space usage and query-time. A crucial step in the process is essentially to design linear space and constant query-time data structures for nonabelian simple groups. The data structures for nonableian simple groups are designed using a lemma that we prove using the Classification Theorem for Finite Simple Groups (CFSG).

The isomorphism problem for groups, when the groups are given by their Cayley tables is a well-studied problem. This problem has been studied for various restricted classes of groups. Kavitha gave a linear time isomorphism algorithm for abelian groups (JCSS 2007). Although there are isomorphism algorithms for certain nonabelian group classes represented by their Cayley tables, the complexities of those algorithms are usually super-linear. In this paper, we design linear and nearly linear time isomorphism algorithms for some nonabelian groups. More precisely, We design a linear-time algorithm to factor Hamiltonian groups. This allows us to obtain an O(n) algorithm for the isomorphism problem of Hamiltonian groups, where n is the order of the groups.We design a nearly linear time algorithm to find a maximal abelian direct factor of an input group. As a byproduct we obtain an O~ (n) isomorphism for groups that can be decomposed as a direct product of a nonabelian group of bounded order and an abelian group, where n is the order of the groups.We observe that testing normality, computing the center of a group, finding a logarithmic sized generating set, computing quotient groups for groups given by their Cayley table could be done in linear or nearly linear time.

The isomorphism problem for groups, when the groups are given by their Cayley tables is a well-studied problem. This problem has been studied for various restricted classes of groups. Kavitha gave a linear time isomorphism algorithm for abelian groups (JCSS 2007). Although there are isomorphism algorithms for certain nonabelian group classes, the complexities of those algorithms are usually super-linear. In this paper, we design linear and nearly linear time isomorphism algorithms for some nonabelian groups. More precisely, We design a linear time algorithm to factor Hamiltonian groups. This allows us to obtain an O(n) algorithm for the isomorphism problem of Hamiltonian groups, where n is the order of the groups.We design a nearly linear time algorithm to find a maximal abelian factor of an input group. As a byproduct we obtain an O~ (n) isomorphism for groups that can be decomposed as a direct product of a nonabelian group of bounded order and an abelian group, where n is the order of the groups.

The Cayley table representation of a group uses (formula presented) words for a group of order n and answers multiplication queries in time O(1) in word RAM model. It is interesting to ask if there is a (formula presented) space representation of groups that still has O(1) query-time. We show that for any (formula presented), (formula presented), there is an (formula presented) space representation for groups of order n with (formula presented) query-time. We also show that for Dedekind groups, simple groups and several group classes defined in terms of semidirect product, there are linear space representation to answer multiplication queries in logarithmic time. Farzan and Munro (ISSAC’06) defined a model for group representation and gave a succinct data structure for abelian groups with constant query-time. They asked if their result can be extended to categorically larger group classes. We show we can construct data structures in their model to represent Hamiltonian groups and extensions of abelian groups by cyclic groups to answer multiplication queries in constant time.