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

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


TR25-145 | 2nd October 2025
Sabee Grewal, William Kretschmer

Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs

We investigate two resources whose effects on quantum interactive proofs remain poorly understood: the promise of unentanglement, and the verifier’s ability to condition on an intermediate measurement, which we call post-measurement branching. We first show that unentanglement can dramatically increase computational power: three-round unentangled quantum interactive proofs equal NEXP, even ... more >>>




ISSN 1433-8092 | Imprint