In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. However, this scheme is not computationally {\em efficient}: the running time to construct ... more >>>

In a breakthrough in the long-going attempt to construct good explicit tree codes, Cohen, Haeupler and Schulman (CHS) (STOC 2018) constructed constant-distance tree codes with rate 1/O(log log n). In their construction a large-alphabet tree code is used as a core element - and they were able to utilize polynomials ... more >>>

Finding good tree code constructions is among the most natural questions in error-correcting codes over the Hamming channel. Unlike the usual setting, where one encodes a single message against adversarial errors, tree codes allow a sender to encode and send a stream, in an online manner, while protecting it from ... more >>>