2026-07-21T03:13:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15835 2024-03-06T10:56:18Z ddc:004 open_access

Linear Space Data Structures for Finite Groups with Constant Query-Time Das, Bireswar Kumar, Anant Sharma, Shivdutt Thakkar, Dhara Compact Data Structures Space Efficient Representations Finite Groups Simple Groups 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bireswar Das and Anant Kumar and Shivdutt Sharma and Dhara Thakkar 2022 Is Part Of LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2022.25 urn:nbn:de:0030-drops-158350 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.25 eng https://creativecommons.org/licenses/by/4.0/legalcode