A No-Go Theorem for Derandomized Parallel Repetition: Beyond
Feige-Kilian
A No-Go Theorem for Derandomized Parallel Repetition: Beyond
Feige-Kilian
In this work we show a barrier towards proving a randomness-efficient parallel repetition, a promising avenue for achieving many tight inapproximability results. Feige and Kilian (STOC'95) proved an impossibility result for randomness-efficient parallel repetition for two prover games with small degree, i.e., when each prover has only few possibilities for …