Derandomized parallel repetition theorems for free games

DOI10.1007/s00037-013-0071-yzbMath1290.68043OpenAlexW2134409102MaRDI QIDQ371195

Ronen Shaltiel

Publication date: 30 September 2013

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-013-0071-y

zbMATH Keywords

derandomization2-prover systemsparallel repetitionrandomness extractors

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

On derandomized composition of Boolean functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomness in interactive proofs
• On the power of multi-prover interactive protocols
• Error reduction by parallel repetition - a negative result
• Towards proving strong direct product theorems
• A one-round, two-prover, zero-knowledge protocol for NP
• Randomness is linear in space
• On Yao’s XOR-Lemma
• A Sample of Samplers: A Computational Perspective on Sampling
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• Strong Parallel Repetition Theorem for Free Projection Games
• Products and Help Bits in Decision Trees
• Randomized graph products, chromatic numbers, and Lovasz j-function
• A Parallel Repetition Theorem
• Communication Complexity

This page was built for publication: Derandomized parallel repetition theorems for free games