Bounded Round Interactive Proofs in Finite Groups

DOI10.1137/0405008MaRDI QIDQ3989015zbMATH OpenOpenAlexFDO

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

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)

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

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
• scientific article; zbMATH DE number 7378343 (Why is no real title available?)
• 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
• Short presentations for finite groups
• SZK proofs for black-box group problems
• On the satisfiability of quantum circuits of small treewidth
• On the satisfiability of quantum circuits of small treewidth
• 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)