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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this work, we introduce bidirectional collision detection --- a newalgorithmic tool that applies to the collision problems that arise in manyisomorphism problems. For the group isomorphism problem, we show thatbidirectional collision detection yields a deterministic n^((1 / 2) log n +O(1)) time algorithm whereas previously the n^(log n + O(1))generator-enumeration algorithm was the best result for several decades. Forthe hard special case of solvable groups, we combine bidirectional collisiondetection with methods from the author's previous work to obtain adeterministic square-root speedup over the best previous algorithm. We alsoshow a deterministic square-root speedup over the best previous algorithm fortesting isomorphism of rings. We can even apply bidirectional collisiondetection to the graph isomorphism problem to obtain a deterministic T^(1 /sqrt(2)) speedup over the best previous deterministic algorithm. Although thespace requirements for our algorithms are greater than those for previousdeterministic isomorphism tests, we show time-space tradeoffs that interpolatebetween the resource requirements of our algorithms and previous work.

Bidirectional Collision Detection and Faster Deterministic Isomorphism Testing