REMARKS ON A QUERY-BASED VARIANT OF THE PARALLEL REPETITION THEOREM

DOI10.1142/S012905410100062XzbMath1319.68096OpenAlexW2030082723MaRDI QIDQ5249275

Oleg Verbitsky

Publication date: 30 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s012905410100062x

zbMATH Keywords

interactive proof systemsextremal graph theoryerror reduction by parallel repetitiontwo-person cooperative games of incomplete information

Mathematics Subject Classification ID

Applications of game theory (91A80) Cryptography (94A60) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• On games of incomplete information
• On the power of multi-prover interactive protocols
• Towards the parallel repetition conjecture
• On the maximum density of 0-1 matrices with no forbidden rectangles
• A one-round, two-prover, zero-knowledge protocol for NP
• A Parallel Repetition Theorem
• Intersection theorems for systems of finite sets

This page was built for publication: REMARKS ON A QUERY-BASED VARIANT OF THE PARALLEL REPETITION THEOREM