Search Results

Documents authored by Khan, Asif

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.MFCS.2024.46
Query Maintenance Under Batch Changes with Small-Depth Circuits

Authors: Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, and Thomas Zeume

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Which dynamic queries can be maintained efficiently? For constant-size changes, it is known that constant-depth circuits or, equivalently, first-order updates suffice for maintaining many important queries, among them reachability, tree isomorphism, and the word problem for context-free languages. In other words, these queries are in the dynamic complexity class DynFO. We show that most of the existing results for constant-size changes can be recovered for batch changes of polylogarithmic size if one allows circuits of depth 𝒪(log log n) or, equivalently, first-order updates that are iterated 𝒪(log log n) times.
Cite as

Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, and Thomas Zeume. Query Maintenance Under Batch Changes with Small-Depth Circuits. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.MFCS.2024.46,
  author =	{Datta, Samir and Khan, Asif and Mukherjee, Anish and Tschirbs, Felix and Vortmeier, Nils and Zeume, Thomas},
  title =	{{Query Maintenance Under Batch Changes with Small-Depth Circuits}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.46},
  URN =		{urn:nbn:de:0030-drops-206027},
  doi =		{10.4230/LIPIcs.MFCS.2024.46},
  annote =	{Keywords: Dynamic complexity theory, parallel computation, dynamic algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.39
Dynamic Planar Embedding Is in DynFO

Authors: Samir Datta, Asif Khan, and Anish Mukherjee

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Planar Embedding is a drawing of a graph on the plane such that the edges do not intersect each other except at the vertices. We know that testing the planarity of a graph and computing its embedding (if it exists), can efficiently be computed, both sequentially [John E. Hopcroft and Robert Endre Tarjan, 1974] and in parallel [Vijaya Ramachandran and John H. Reif, 1994], when the entire graph is presented as input. In the dynamic setting, the input graph changes one edge at a time through insertion and deletions and planarity testing/embedding has to be updated after every change. By storing auxilliary information we can improve the complexity of dynamic planarity testing/embedding over the obvious recomputation from scratch. In the sequential dynamic setting, there has been a series of works [David Eppstein et al., 1996; Giuseppe F. Italiano et al., 1993; Jacob Holm et al., 2018; Jacob Holm and Eva Rotenberg, 2020], culminating in the breakthrough result of polylog(n) sequential time (amortized) planarity testing algorithm of Holm and Rotenberg [Jacob Holm and Eva Rotenberg, 2020]. In this paper we study planar embedding through the lens of DynFO, a parallel dynamic complexity class introduced by Patnaik et al [Sushant Patnaik and Neil Immerman, 1997] (also [Guozhu Dong et al., 1995]). We show that it is possible to dynamically maintain whether an edge can be inserted to a planar graph without causing non-planarity in DynFO. We extend this to show how to maintain an embedding of a planar graph under both edge insertions and deletions, while rejecting edge insertions that violate planarity. Our main idea is to maintain embeddings of only the triconnected components and a special two-colouring of separating pairs that enables us to side-step cascading flips when embedding of a biconnected planar graph changes, a major issue for sequential dynamic algorithms [Jacob Holm and Eva Rotenberg, 2020; Jacob Holm and Eva Rotenberg, 2020].
Cite as

Samir Datta, Asif Khan, and Anish Mukherjee. Dynamic Planar Embedding Is in DynFO. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.MFCS.2023.39,
  author =	{Datta, Samir and Khan, Asif and Mukherjee, Anish},
  title =	{{Dynamic Planar Embedding Is in DynFO}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.39},
  URN =		{urn:nbn:de:0030-drops-185736},
  doi =		{10.4230/LIPIcs.MFCS.2023.39},
  annote =	{Keywords: Dynamic Complexity, Planar graphs, Planar embedding}
}
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