A nonadaptive NC checker for permutation group intersection

DOI10.1016/S0304-3975(00)00159-6MaRDI QIDQ5941295zbMATH OpenOpenAlexFDO

Authors Vikraman Arvind, Jacobo Torán

Publication date 20 August 2001

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(00)00159-6

zbMATH Keywords

interactive proofsparallel algorithmspermutation groupsprogram checking

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Parallel algorithms in computer science (68W10)

Review text

We design a nonadaptive NC checker for permutation group intersection, sharpening a result of \textit{M. Blum} and \textit{S. Kannan} [J. Assoc. Comput. Mach. 43, 269-291 (1995; Zbl 0886.68046)]. Additionally, we also get nonadaptive NC checkers for some related group-theoretic problems.

Recommendations

• Monte Carlo circuits for the abelian permutation group intersection problem
• On the computational complexity of the Abelian permutation group structure, membership and intersection problems
• The Parallel Complexity of Abelian Permutation Group Problems
• Designing programs that check their work
• scientific article; zbMATH DE number 841570

Cites work

• Arithmetization: A new method in structural complexity theory
• Designing programs that check their work
• Efficient checkers for number-theoretic computations
• Group-theoretic algorithms and graph isomorphism
• scientific article; zbMATH DE number 3137403 (Why is no real title available?)
• scientific article; zbMATH DE number 475362 (Why is no real title available?)
• scientific article; zbMATH DE number 549854 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3341276 (Why is no real title available?)
• IP = PSPACE
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Parallel concepts in graph theory

Cited in

(3)

• On the Complexity of the Hidden Subgroup Problem
• On the complexity of the hidden subgroup problem
• On the asymmetric complexity of the group-intersection problem

This page was built for publication: A nonadaptive NC checker for permutation group intersection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941295)