Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with No-Signaling Proofs:
TR18-009 | 9th January 2018
Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

Non-Interactive Delegation for Low-Space Non-Deterministic Computation

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifi cally, letting $n$ denote the input length, we construct a delegation scheme for any language veri fiable in non-deterministic time and space $(T(n);S(n))$ with communication complexity $poly(S(n))$, verifi er ... more >>>

TR18-161 | 13th September 2018
Justin Holmgren, Ron Rothblum

Delegating Computations with (almost) Minimal Time and Space Overhead

The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as ... more >>>

TR20-035 | 23rd February 2020
Justin Holmgren

No-Signaling MIPs and Faster-Than-Light Communication, Revisited

We revisit one original motivation for the study of no-signaling multi-prover
interactive proofs (NS-MIPs): specifically, that two spatially separated
provers are guaranteed to be no-signaling by the physical principle that
information cannot travel from one point to another faster than light.

We observe that with ... more >>>

ISSN 1433-8092 | Imprint