Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with verifiable computation:
TR13-165 | 28th November 2013
Michael Walfish, Andrew Blumberg

Verifying computations without reexecuting them: from theoretical possibility to near-practicality

Revisions: 3

How can we trust results computed by a third party, or the integrity of data stored by such a party? This is a classic question in systems security, and it is particularly relevant in the context of cloud computing.

Various solutions have been proposed that make assumptions about the class ... more >>>

TR13-180 | 17th December 2013
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

On Interactivity in Arthur-Merlin Communication and Stream Computation

Revisions: 1

We introduce {\em online interactive proofs} (OIP), which are a hierarchy of communication complexity models that involve both randomness and nondeterminism (thus, they belong to the Arthur--Merlin family), but are {\em online} in the sense that the basic communication flows from Alice to Bob alone. The complexity classes defined by ... more >>>

TR23-107 | 20th July 2023
Uma Girish, Ran Raz, Wei Zhan

Quantum Logspace Computations are Verifiable

In this note, we observe that quantum logspace computations are verifiable by classical logspace algorithms, with unconditional security. More precisely, every language in BQL has an information-theoretically secure) streaming proof with a quantum logspace prover and a classical logspace verifier. The prover provides a polynomial-length proof that is streamed to ... more >>>

ISSN 1433-8092 | Imprint