Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Malvika Raj:

TR21-165 | 21st November 2021
Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams

Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity

Revisions: 1

In a Merlin-Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability $1$, and rejects invalid proofs with probability arbitrarily close to $1$. The running time of such a system is defined to be the length of Merlin's proof plus the running time of Arthur. We ... more >>>

ISSN 1433-8092 | Imprint