Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky ... more >>>

We present an information-theoretically secure continuously non-malleable code in the constant split-state model, where there is a self-destruct mechanism which ensures that the adversary loses access to tampering after the first failed decoding. Prior to our result only codes with computational security were known for this model, and it has ... more >>>

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>>