Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ONLINE INTERACTIVE PROOFS:
Reports tagged with online interactive proofs:
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