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

ISSN 1433-8092 | Imprint