Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Arthur Merlin games:
TR21-127 | 30th August 2021
Ron D. Rothblum, Michael Ezra

Small Circuits Imply Efficient Arthur-Merlin Protocols

Revisions: 1

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

TR22-074 | 20th May 2022
Michael Saks, Rahul Santhanam

On Randomized Reductions to the Random Strings

We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants.

As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language $L$ that has a randomized ... more >>>

ISSN 1433-8092 | Imprint