Bounded Round Interactive Proofs in Finite Groups

DOI10.1137/0405008zbMATH Open0741.68047OpenAlexW2171847006MaRDI QIDQ3989015FDOQ3989015

Authors: László Babai 

Publication date: 28 June 1992

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0405008

Recommendations

• SZK proofs for black-box group problems
• Polynomial-time theory of matrix groups
• scientific article; zbMATH DE number 1284153
• Solvable group isomorphism is (almost) in \(\mathsf{NP} \cap \mathsf{coNP}\)
• New Computational Paradigms

zbMATH Keywords

randomizationcomplexityexpansiongroupnondeterminisminteractive proofs

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Arithmetic and combinatorial problems involving abstract finite groups (20D60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (13)

• Solvable group isomorphism is (almost) in \(\mathsf{NP} \cap \mathsf{coNP}\)
• SZK Proofs for Black-Box Group Problems
• The counting complexity of group-definable languages
• Title not available (Why is that?)
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas
• New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
• Solvable black-box group problems are low for PP
• On the satisfiability of quantum circuits of small treewidth
• On the satisfiability of quantum circuits of small treewidth
• Short presentations for finite groups
• SZK proofs for black-box group problems
• Graph Isomorphism is in SPP

This page was built for publication: Bounded Round Interactive Proofs in Finite Groups

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