Search problems in groups and branching processes

DOI10.1142/S0218196715500058zbMath1327.20038arXiv1407.1685MaRDI QIDQ5252307

Pavel V. Morar, Alexander Ushakov

Publication date: 29 May 2015

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.1685

zbMATH Keywords

finitely presented groupspolynomial time algorithmsCrump-Mode-Jagers processgroup-based cryptographyconjugacy search problemmembership search problemword search problemannular diagramsgeneralized van Kampen diagramsWagner-Magyarik cryptosystem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Complexity of computation (including implicit computational complexity) (03D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Cancellation theory of groups; application of van Kampen diagrams (20F06)

Related Items (1)

Conjugacy search problem and the Andrews-Curtis conjecture

Cites Work

• Algorithmically finite groups.
• Filling length in finitely presentable groups.
• Security analysis of word problem-based cryptosystems
• Topology of finite graphs
• Asymptotical growth of a class of random trees
• On growing random binary trees
• Branching processes in the analysis of the heights of trees
• The use of Knuth-Bendix methods to solve the word problem in automatic groups
• Postulates for subadditive processes
• The first birth problem for an age-dependent branching process
• Presentations of groups and monoids
• A strong law for the height of random binary pyramids
• A note on the growth of random trees
• Generic-case complexity, decision problems in group theory, and random walks.
• Stallings foldings and subgroups of free groups
• A reaction attack on a public key cryptosystem based on the word problem
• The growth and spread of the general branching random walk
• On Dehn's algorithm and the conjugacy problem
• A general age-dependent branching process. I
• Simple examples of groups with unsolvable word problem
• Search and witness problems in group theory
• THE WORD PROBLEM
• The growth and composition of branching populations
• A FAST ALGORITHM FOR STALLINGS' FOLDING PROCESS
• On the convergence of supercritical general (C-M-J) branching processes
• A note on the height of binary search trees
• Chernoff's theorem in the branching random walk
• Note on the heights of random recursive trees and random m‐ary search trees
• A practical method for enumerating cosets of a finite abstract group
• The word problem

This page was built for publication: Search problems in groups and branching processes