Structural complexity of rational interactive proofs

DOI10.1007/978-3-031-36978-0_19arXiv2305.04563OpenAlexW4384788943MaRDI QIDQ6149048

Daniil Musatov, Georgii Potapov

Publication date: 12 January 2024

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

Full work available at URL: https://arxiv.org/abs/2305.04563

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• The complexity of combinatorial problems with succinct input representation
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• On the power of multi-prover interactive protocols
• Efficient rational proofs with strong utility-gap guarantees
• Efficient rational proofs for space bounded computations
• PP is closed under truth-table reductions
• Rational Proofs with Multiple Provers
• Rational arguments
• PP is as Hard as the Polynomial-Time Hierarchy
• Sequentially Composable Rational Proofs
• The Knowledge Complexity of Interactive Proof Systems
• Algebraic methods for interactive proof systems
• IP = SPACE
• Rational proofs

This page was built for publication: Structural complexity of rational interactive proofs