Bounded Round Interactive Proofs in Finite Groups

DOI10.1137/0405008zbMath0741.68047OpenAlexW2171847006MaRDI QIDQ3989015

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

complexityexpansionrandomizationgroupnondeterminisminteractive proofs

Mathematics Subject Classification ID

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

Related Items (11)

New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. ⋮ Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes ⋮ Short presentations for finite groups ⋮ On the Satisfiability of Quantum Circuits of Small Treewidth ⋮ On the satisfiability of quantum circuits of small treewidth ⋮ Solvable black-box group problems are low for PP ⋮ Unnamed Item ⋮ SZK proofs for black-box group problems ⋮ Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas ⋮ Graph Isomorphism is in SPP ⋮ The counting complexity of group-definable languages

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