A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian

DOI10.4230/LIPIcs.APPROX-RANDOM.2016.42zbMath1398.68185arXiv1607.07130OpenAlexW2963106827MaRDI QIDQ4636476

Govind Ramnarayan, Henry C. Yuen, Dana Moshkovitz

Publication date: 19 April 2018

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

zbMATH Keywords

derandomizationfortificationparallel repetitionFeige-Kilian

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Low-degree test with polynomially small error

This page was built for publication: A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian