Miklos Ajtai

Abstract. We show that oblivious on-line simulation with only

polylogarithmic increase in the time and space requirements is possible

on a probabilistic (coin flipping) RAM without using any cryptographic

assumptions. The simulation will fail with a negligible probability.

If $n$ memory locations are used, then the probability of failure is ...
more >>>

Balthazar Bauer, Shay Moran, Amir Yehudayoff

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