Seminar Details
Linear Space Data Structures for Finite Groups with Constant Query-Time
- Start Date: January 25, 2023
- Event Start Time: 11:00 AM
- Event End Time: 12:15 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Bireswar Das - Indian Institute of Technology, Gandhinagar
- Event Location: Online Event
- Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar" target="_blank">https://theory.cs.rutgers.edu/theory_seminar</a></p> <p>This seminar will be held online via zoom only.</p>
- Presentation Type: Stand Alone Presentation
- 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^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).