Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ZHENGFENG JI:
All reports by Author Zhengfeng Ji:

TR18-105 | 30th May 2018
Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen

Quantum proof systems for iterated exponential time, and beyond

We show that any language in nondeterministic time \exp(\exp(\cdots\exp(n))), where the number of iterated exponentials is an arbitrary function R(n), can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness 1 and soundness 1 - \exp(-C\exp(\cdots\exp(n))), ... more >>>




ISSN 1433-8092 | Imprint