Abstract
This talk is concerned with the design of coding schemes for interactive communication that are computationally efficient and can tolerate optimal rates. We show that list decodable coding schemes are a key ingredient for achieving both goals.
We give a general black-box reduction which reduces unique decoding, in various settings, to list decoding while preserving computational efficiency. In particular, we give the first computational efficient non-adaptive protocol tolerating the optimal 1/4 error rate. We also define adaptive protocols and show that, given a list decoder, adaptive coding schemes can tolerate a higher error rate of 2/7, which is optimal.
As a second ingredient we show how to boost the computational and communication efficiency of any list decoder to become near linear. Put together with the list decoder of Braverman and Effremenko (see day 4) this leads to coding schemes with optimal error tolerance, constant rate, and near linear computational complexity for all settings considered.
This talk is based on joint work with Mohsen Ghaffari (STOC'14,FOCS'14) and Madhu Sudan (FOCS'14).