Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Saikrishna Badrinarayanan:

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

ISSN 1433-8092 | Imprint