Linear Space Data Structures for Finite Groups with Constant Query-time
| Autor: | Das, Bireswar, Kumar, Anant, Sharma, Shivdutt, Thakkar, Dhara |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Group Theory (math.GR) Finite Groups Theory of computation ��� Data compression Simple Groups Theory of computation ��� Data structures design and analysis Computer Science - Data Structures and Algorithms FOS: Mathematics Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Compact Data Structures Combinatorics (math.CO) Classification Theorem for Finite Simple Groups Space Efficient Representations Mathematics - Group Theory Computer Science::Databases Computer Science - Discrete Mathematics |
| Popis: | 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^2)$ 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^2)$ 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 $\Omega(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). Comment: A preliminary version of this article appeared in the pro- ceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|