Search Results

Documents authored by Sharma, Shivdutt

Document
DOI: 10.4230/LIPIcs.FSTTCS.2024.4
The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem

Authors: V. Arvind, Samir Datta, Asif Khan, Shivdutt Sharma, Yadu Vasudev, and Shankar Ram Vasudevan

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract
Let G be a finite group given as input by its multiplication table. For a subset S ⊆ G and an element g ∈ G the Cayley Group Membership Problem (CGM) is to check if g belongs to the subgroup generated by S. While this problem is easily seen to be in polynomial time, pinpointing its parallel complexity has been of research interest over the years. Barrington et al [Barrington et al., 2001] have shown that for abelian groups the CGM problem can be solved in O(log log |G|) parallel time. In this paper we further explore the parallel complexity of the abelian CGM problem, with focus on the dynamic setting: the generating set S changes with insertions and deletions and the goal is to maintain a data structure that supports efficient membership queries to the subgroup ⟨S⟩. Though the static version of the CGM problem can be easily reduced to digraph reachability, the reduction does not carry over to the dynamic setting. We obtain the following results: 1) First, we consider the more general problem of Monoid Membership, where G is a monoid input by its multiplication table. When G is a commutative monoid we show there is a deterministic dynamic AC⁰ algorithm for membership testing that supports O(1) insertions and deletions in each step. 2) Building on the previous result we show that there is a dynamic randomized AC⁰ algorithm for abelian CGM that supports polylog(|G|) insertions/deletions to S in each step. 3) If the number of insertions/deletions is at most O(log n/log log n) then we obtain a deterministic dynamic AC⁰ algorithm for abelian CGM. 4) Applying these algorithms we obtain analogous results for the dynamic abelian Group Isomorphism. We can also handle sub-linearly many changes to the multiplication table for G, utilizing the hamming distance between multiplication tables of any two distinct groups.
Cite as

V. Arvind, Samir Datta, Asif Khan, Shivdutt Sharma, Yadu Vasudev, and Shankar Ram Vasudevan. The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2024.4,
  author =	{Arvind, V. and Datta, Samir and Khan, Asif and Sharma, Shivdutt and Vasudev, Yadu and Vasudevan, Shankar Ram},
  title =	{{The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.4},
  URN =		{urn:nbn:de:0030-drops-221939},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.4},
  annote =	{Keywords: Dynamic Complexity, Group Theory, Cayley Group Membership, Abelian Group Isomorphism}
}
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.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}
}
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 About DROPS Imprint Privacy Contact