Nov. 11, 2019

room 201 building 37

In this talk I will present a deterministic interactive coding scheme against adversarial errors that approaches capacity. Prior to this work, deterministic coding schemes for any constant fraction of adversarial errors could obtain rate no larger than one half. Achieving higher rate was obtained either using probabilistic coding schemes or otherwise assumed weaker error models such as binary symmetric channels, erasure channels or feedback channels.

No prior knowledge is required.