Henry Yuen

Quantum soundness of the classical low individual degree test

2020 · arXiv (Cornell University)

Low degree tests play an important role in classical complexity theory, serving as basic ingredients in foundational results such as $\mathsf{MIP} = \mathsf{NEXP}$ [BFL91] and the PCP theorem [AS98,ALM+98]. Over the last ten years, versions …