1 Search Results for "Sharma, Shivdutt"

Document
DOI: 10.4230/LIPIcs.STACS.2022.25
Linear Space Data Structures for Finite Groups with Constant Query-Time

Authors: Bireswar Das, Anant Kumar, Shivdutt Sharma, and Dhara Thakkar

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

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

Bireswar Das, Anant Kumar, Shivdutt Sharma, and Dhara Thakkar. Linear Space Data Structures for Finite Groups with Constant Query-Time. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.25},
  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}
}
  • Refine by Author
  • 1 Das, Bireswar
  • 1 Kumar, Anant
  • 1 Sharma, Shivdutt
  • 1 Thakkar, Dhara

  • Refine by Classification
  • 1 Theory of computation → Data compression
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 Classification Theorem for Finite Simple Groups
  • 1 Compact Data Structures
  • 1 Finite Groups
  • 1 Simple Groups
  • 1 Space Efficient Representations

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact