All reports by Author Yael Kalai:

__
TR18-203
| 1st December 2018
__

Yael Kalai, Dakshita Khurana#### Non-Interactive Non-Malleability from Quantum Supremacy

__
TR18-054
| 24th March 2018
__

Klim Efremenko, Elad Haramaty, Yael Kalai#### Interactive Coding with Constant Round and Communication Blowup

Revisions: 1

__
TR18-009
| 9th January 2018
__

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs#### Non-Interactive Delegation for Low-Space Non-Deterministic Computation

Yael Kalai, Dakshita Khurana

We construct non-interactive non-malleable commitments with respect to replacement, without setup in the plain model, under well-studied assumptions.

First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon>0$, under the following assumptions:

- Sub-exponential hardness of factoring or discrete ... more >>>

Klim Efremenko, Elad Haramaty, Yael Kalai

The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since ... more >>>

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

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