scientific article; zbMATH DE number 512981

MaRDI QIDQ4281691zbMATH OpenFDO

Authors Ulrich Hertrampf, K. W. Wagner

Publication date 20 June 1994

zbMATH Keywords

interactive proof systemspolynomial time complexity classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the power of multi-prover interactive protocols
• PSPACE is provable by two provers in one round
• Alternation in interaction

Cited in

(30)

• PSPACE is provable by two provers in one round
• On the power of multi-prover interactive protocols
• A note on PCP vs. MIP
• Interactive protocols over the reals
• Multi-prover encoding schemes and three-prover proof systems
• Proving properties of interactive proofs by a generalized counting technique
• A logic of interactive proofs
• Interactive proofs and a Shamir-like result for real number computations
• Multi-prover interactive proofs: unsound foundations
• Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
• IP = PSPACE using error-correcting codes
• On the power of many one-bit provers
• scientific article; zbMATH DE number 176510 (Why is no real title available?)
• scientific article; zbMATH DE number 176552 (Why is no real title available?)
• scientific article; zbMATH DE number 1024045 (Why is no real title available?)
• scientific article; zbMATH DE number 1555928 (Why is no real title available?)
• Real interactive proofs for VPSPACE
• A hierarchy theorem for interactive proofs of proximity
• ON HELPING AND INTERACTIVE PROOF SYSTEMS
• Round complexity versus randomness complexity in interactive proofs
• Interactive proof systems with public coin: lower space bounds and hierarchies of complexity classes
• scientific article; zbMATH DE number 7563815 (Why is no real title available?)
• Constant-Round Interactive Proof Systems for AC0[2] and NC1
• On Input Indistinguishable Proof Systems
• Alternation in interaction
• Parallel repetition of \((k_1,\dots ,k_{\mu }) \)-special-sound multi-round interactive proofs
• Doubly efficient interactive proofs over infinite and non-commutative rings
• Interactive proof systems and alternating time-space complexity
• Non-deterministic exponential time has two-prover interactive protocols
• On the power of interaction

This page was built for publication:

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