Short Non-Interactive Proofs for Time-Space ComputationsResearch Paper
An interactive proof lets a slow prover convince a fast verifier. Merlin–Arthur (MA) protocols remove the interaction: the prover sends one message, and the verifier tosses coins and decides. For circuit satisfiability and related problems, a line of work gives MA protocols that run faster than the known algorithms, starting from Williams, 2016, who gave a …