Polynomial-time theory of matrix groups

DOI10.1145/1536414.1536425zbMath1304.68065OpenAlexW2044388955WikidataQ60587912 ScholiaQ60587912MaRDI QIDQ5172698

Robert Beals, Seress, Ákos, László Babai

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536425

zbMATH Keywords

matrix groupscomputational group theorydiscrete log

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Other matrix groups over finite fields (20H30)

Related Items (19)

Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ General linear group action on tensors: a candidate for post-quantum cryptography ⋮ Recognising simplicity of black-box groups by constructing involutions and their centralisers. ⋮ Constructing composition factors for a linear group in polynomial time ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Unnamed Item ⋮ Random generation of finite and profinite groups and group enumeration. ⋮ Computing conjugacy classes of elements in matrix groups. ⋮ Black box exceptional groups of Lie type. II. ⋮ A practical model for computation with matrix groups. ⋮ Linear decomposition method in analyzing hidden information protocols on algebraic platforms ⋮ Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas ⋮ The use of permutation representations in structural computations in large finite matrix groups ⋮ Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography ⋮ Linear groups and computation ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ The hidden subgroup problem and MKTP

This page was built for publication: Polynomial-time theory of matrix groups