Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs \cite{DPW10} as an elegant generalization of the classical notions of error detection, where the corruption of a codeword is viewed as a tampering function acting on it. Informally, a non-malleable code with respect to a family of tampering functions $\mathcal{F}$ consists ... more >>>

We study internal compression of communication protocols
to their internal entropy, which is the entropy of the transcript from the players' perspective.
We first show that errorless compression to the internal entropy
(and hence to the internal information) is impossible.
We then provide two internal compression schemes with error.
One ... more >>>

"Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity.

Amir, Beigel, and Gasarch ... more >>>