License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2022.25
URN: urn:nbn:de:0030-drops-158350
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15835/
Go to the corresponding LIPIcs Volume Portal

Das, Bireswar ; Kumar, Anant ; Sharma, Shivdutt ; Thakkar, Dhara

Linear Space Data Structures for Finite Groups with Constant Query-Time

pdf-format:
LIPIcs-STACS-2022-25.pdf (0.7 MB)

Abstract

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

BibTeX - Entry

@InProceedings{das_et_al:LIPIcs.STACS.2022.25,
  author =	{Das, Bireswar and Kumar, Anant and Sharma, Shivdutt and Thakkar, Dhara},
  title =	{{Linear Space Data Structures for Finite Groups with Constant Query-Time}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15835},
  URN =		{urn:nbn:de:0030-drops-158350},
  doi =		{10.4230/LIPIcs.STACS.2022.25},
  annote =	{Keywords: Compact Data Structures, Space Efficient Representations, Finite Groups, Simple Groups, Classification Theorem for Finite Simple Groups}
}

Keywords: Compact Data Structures, Space Efficient Representations, Finite Groups, Simple Groups, Classification Theorem for Finite Simple Groups
Collection: 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Issue Date: 2022
Date of publication: 09.03.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI