English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Let $G$ be a finite group given as input by its multiplication table. For asubset $S$ of $G$ and an element $g\in G$ the Cayley Group Membership Problem(denoted 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 itsparallel complexity has been of research interest over the years. In this paperwe further explore the parallel complexity of the abelian CGM problem, withfocus on the dynamic setting: the generating set $S$ changes with insertionsand deletions and the goal is to maintain a data structure that supportsefficient membership queries to the subgroup $\angle{S}$. We obtain thefollowing results:  1. We first consider the more general problem of Monoid Membership. When $G$is a commutative monoid we give a deterministic dynamic algorithm  constant time parallel 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 randomizedconstant-time parallel algorithm for abelian CGM that supportspolylogarithmically many 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 constant-time parallel algorithm for theproblem.  4. We obtain analogous results for the dynamic abelian Group Isomorphism.

The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem