Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ARTHUR MERLIN GAMES:
Reports tagged with Arthur Merlin games:
TR21-127 | 30th August 2021
Ron D. Rothblum, Michael Ezra

Small Circuits Imply Efficient Arthur-Merlin Protocols

The inner product function $\langle x,y \rangle = \sum_i x_i y_i \bmod 2$ can be easily computed by a (linear-size) ${AC}^0(\oplus)$ circuit: that is, a constant depth circuit with AND, OR and parity (XOR) gates. But what if we impose the restriction that the parity gates can only be on ... more >>>




ISSN 1433-8092 | Imprint