Document

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

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

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} }

Document

**Published in:** LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $2^{O(b)}N^{O(1)}$, where the parameter $b$ is the maximum size of the color classes of the given hypergraphs and $N$ is the input size. We also describe fpt algorithms for certain permutation group problems that are used as subroutines in our algorithm.

V. Arvind, Bireswar Das, Johannes Köbler, and Seinosuke Toda. Colored Hypergraph Isomorphism is Fixed Parameter Tractable. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 327-337, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2010.327, author = {Arvind, V. and Das, Bireswar and K\"{o}bler, Johannes and Toda, Seinosuke}, title = {{Colored Hypergraph Isomorphism is Fixed Parameter Tractable}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {327--337}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.327}, URN = {urn:nbn:de:0030-drops-28751}, doi = {10.4230/LIPIcs.FSTTCS.2010.327}, annote = {Keywords: Fixed parameter tractability, fpt algorithms, graph isomorphism, computational complexity} }

Document

**Published in:** LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Reachability and shortest path problems are \NLC\ for general graphs. They are known to be in \Log\ for graphs of tree-width $2$ \cite{JT07}. However, for graphs of tree-width larger than $2$, no bound better than \NL\ is known.
In this paper, we improve these bounds for $k$-trees, where $k$ is a constant. In particular, the main results of our paper are log-space algorithms for reachability in directed $k$-trees, and for computation of shortest and longest paths in directed acyclic $k$-trees.
Besides the path problems mentioned above, we consider the problem of deciding whether a $k$-tree has a perfect macthing (decision version), and if so, finding a perfect matching (search version), and prove that these problems are \Log-complete.
These problems are known to be in \Ptime\ and in \RNC\ for general graphs, and in \SPL\ for planar bipartite graphs \cite{DKR08}.
Our results settle the complexity of these problems for the class of $k$-trees. The results are also applicable for bounded tree-width graphs, when a tree-decomposition is given as input. The technique
central to our algorithms is a careful implementation of divide-and-conquer approach in log-space, along with some ideas from \cite{JT07} and \cite{LMR07}.

Bireswar Das, Samir Datta, and Prajakta Nimbhorkar. Log-space Algorithms for Paths and Matchings in k-trees. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 215-226, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.STACS.2010.2456, author = {Das, Bireswar and Datta, Samir and Nimbhorkar, Prajakta}, title = {{Log-space Algorithms for Paths and Matchings in k-trees}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {215--226}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2456}, URN = {urn:nbn:de:0030-drops-24563}, doi = {10.4230/LIPIcs.STACS.2010.2456}, annote = {Keywords: k-trees, reachability, matching, log-space} }

Document

**Published in:** LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time~\cite{Bo90},\cite{YBFT}.We give restricted space algorithms for these problems proving the following results:
\begin{itemize}
\item Isomorphism for bounded tree distance width graphs is in \Log\ and thus complete for the class. We also show that for this kind of graphs a canon can be computed within logspace.
\item For bounded treewidth graphs, when both input graphs are given together with a tree decomposition, the problem of whether there is an isomorphism which respects the decompositions (i.e.\ considering only isomorphisms mapping bags in one decomposition blockwise onto bags in the other decomposition)
is in \Log.
\item For bounded treewidth graphs, when one of the input graphs is given with a tree decomposition the isomorphism problem is in \LogCFL.
\item As a corollary the isomorphism problem for bounded treewidth graphs is in \LogCFL. This improves the known \TCone\ upper bound for the problem given by Grohe and Verbitsky~\cite{GV06}.
\end{itemize}

Bireswar Das, Jacobo Torán, and Fabian Wagner. Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 227-238, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.STACS.2010.2457, author = {Das, Bireswar and Tor\'{a}n, Jacobo and Wagner, Fabian}, title = {{Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {227--238}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2457}, URN = {urn:nbn:de:0030-drops-24570}, doi = {10.4230/LIPIcs.STACS.2010.2457}, annote = {Keywords: Complexity, Algorithms, Graph Isomorphism Problem, Treewidth, LogCFL} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail