Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Arguments:
TR16-049 | 28th March 2016
Cynthia Dwork, Moni Naor, Guy Rothblum

Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems

We are interested in constructing short two-message arguments for various languages, where the complexity of the verifier is small (e.g. linear in the input size, or even sublinear if the input is coded appropriately).

In 2000 Aiello et al. suggested the tantalizing possibility of obtaining such arguments for all of ... more >>>

ISSN 1433-8092 | Imprint