Proving properties of interactive proofs by a generalized counting technique

DOI10.1016/0890-5401(89)90053-9MaRDI QIDQ1825663zbMATH OpenOpenAlexFDO

Authors László Babai, Shlomo Moran

Publication date 1989

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(89)90053-9

zbMATH Keywords

interactive protocolinteractive proofsIP hierarchyArthur Merlin game

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 66620
• Randomness in interactive proofs
• scientific article; zbMATH DE number 512981
• scientific article; zbMATH DE number 412256
• On the power of interaction

Cites work

• scientific article; zbMATH DE number 4002078 (Why is no real title available?)
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The knowledge complexity of interactive proof-systems
• Universal classes of hash functions

Cited in

(3)

• Randomness in interactive proofs
• Results on resource-bounded measure
• Parallel repetition of \((k_1,\dots ,k_{\mu }) \)-special-sound multi-round interactive proofs

This page was built for publication: Proving properties of interactive proofs by a generalized counting technique

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