Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Yael Kalai:

TR22-050 | 12th April 2022
Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena

Circuits Resilient to Short-Circuit Errors

Given a Boolean circuit $C$, we wish to convert it to a circuit $C'$ that computes the same function as $C$ even if some of its gates suffer from adversarial short circuit errors, i.e., their output is replaced by the value of one of their inputs [KLM97]. Can we ... more >>>

TR18-203 | 1st December 2018
Yael Kalai, Dakshita Khurana

Non-Interactive Non-Malleability from Quantum Supremacy

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

TR18-054 | 24th March 2018
Klim Efremenko, Elad Haramaty, Yael Kalai

Interactive Coding with Constant Round and Communication Blowup

Revisions: 1

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

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