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

Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams

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 >>>