Arthur-Merlin games and the problem of isomorphism testing

DOI10.1007/11494645_61MaRDI QIDQ5717081zbMATH OpenOpenAlexFDO

Authors Jacobo Torán

Publication date 11 January 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b136981

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The complexity of game isomorphism
• Derandomizing Arthur-Merlin games under uniform assumptions
• Derandomizing Arthur-Merlin games under uniform assumptions
• On the Complexity of Game Isomorphism
• Arthur-Merlin games in Boolean decision trees
• scientific article; zbMATH DE number 1335880
• Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
• Derandomizing Arthur-Merlin games using hitting sets
• NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES

Cited in

(6)

• Derandomizing Arthur-Merlin games under uniform assumptions
• Complexity of ring morphism problems
• Solvable group isomorphism is (almost) in \(\mathsf{NP} \cap \mathsf{coNP}\)
• scientific article; zbMATH DE number 4050983 (Why is no real title available?)
• Bounded Round Interactive Proofs in Finite Groups
• Derandomizing Arthur-Merlin games under uniform assumptions

This page was built for publication: Arthur-Merlin games and the problem of isomorphism testing

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