Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MERLIN-ARTHUR GAMES:
Reports tagged with Merlin-Arthur games:
TR16-002 | 18th January 2016
Ryan Williams

#### Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ and degree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in {\mathbb F}^n$,
$\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K) \in {\mathbb F}$ and ... more >>>

ISSN 1433-8092 | Imprint