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 these seminal works, there have been many followup works which improve the error rate, the communication rate, and the computational efficiency.

All these works assume that in each round each party sends a single bit, an assumption that may cause a substantial increase in the {\em round complexity}. Moreover, they assume that the communication complexity of the underlying protocol is {\em fixed} and a priori known.

In this work, we show how to convert any protocol $\Pi$, with {\em no a priori} known {\em communication bound}, into an error-resilient protocol $\Pi'$, with comparable computational efficiency, that is resilient to constant fraction of adversarial error, while blowing up both the communication complexity and the {\em round complexity} by at most a constant factor.
We consider the model where in each round each party may send a message of {\em arbitrary length}, where the length of the messages and the length of the protocol may be {\em adaptive}, and may depend on the private inputs of the parties and on previous communication. We consider the adversarial error model, where $\epsilon$-fraction of the communication may be corrupted, where we allow each corruption to be an {\em insertion} or {\em deletion} (in addition to toggle).

In addition, we try to minimize the blowup parameters: In particular, we construct such $\Pi'$ with $(1+\tilde{O}\left(\epsilon^{1/4}\right))$ blowup in communication and $O(1)$ blowup in rounds. We also show how to reduce the blowup in rounds at the expense of increasing the blowup in communication, and construct $\Pi'$ where both the blowup in rounds and communication, approaches one (i.e., no blowup) as $\epsilon$ approaches zero. We give ``evidence" that our parameters are ``close to" optimal.

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 these seminal works, there have been many followup works which improve the error rate, the communication rate, and the computational efficiency.

All these works assume that in each round each party sends a single bit, an assumption that may cause a substantial increase in the {\em round complexity}. Moreover, they assume that the communication complexity of the underlying protocol is {\em fixed} and a priori known.

In this work, we show how to convert any protocol $\Pi$, with {\em no a priori} known {\em communication bound}, into an error-resilient protocol $\Pi'$, with comparable computational efficiency, that is resilient to constant fraction of adversarial error, while blowing up both the communication complexity and the {\em round complexity} by at most a constant factor.
We consider the model where in each round each party may send a message of {\em arbitrary length}, where the length of the messages and the length of the protocol may be {\em adaptive}, and may depend on the private inputs of the parties and on previous communication. We consider the adversarial error model, where $\epsilon$-fraction of the communication may be corrupted, where we allow each corruption to be an {\em insertion} or {\em deletion} (in addition to toggle).

In addition, we try to minimize the blowup parameters: In particular, we construct such $\Pi'$ with $(1+\tilde{O}\left(\epsilon^{1/4}\right))$ blowup in communication and $O(1)$ blowup in rounds. We also show how to reduce the blowup in rounds at the expense of increasing the blowup in communication, and construct $\Pi'$ where both the blowup in rounds and communication, approaches one (i.e., no blowup) as $\epsilon$ approaches zero. We give ``evidence" that our parameters are ``close to" optimal.