Computer Science/Discrete Mathematics Seminar I

We consider the problem of explicitly constructing binary linear codes achieving the optimal rate-distance tradeoff.  In 2017, Ta-Shma gave an almost-optimal construction in the low-rate regime, i.e., he gave a construction of binary linear codes with distance 1/2 - ε and rate ε^{2+o(1)}.  For comparison, random codes achieve distance 1/2 - ε at rate Ω(ε^2).  Ta-Shma's approach is based on starting with a good code, and amplifying its distance with the "expander walk" approach of Rozenman and Wigderson, but is fairly involved technically.

In this talk, I will describe the expander walk amplification approach, along with a simpler route to obtain Ta-Shma's result using what we call "free expander walks".

This talk is based on a recent joint work with Jun-Ting (Tim) Hsieh and Rachel Yun Zhang (https://arxiv.org/abs/2601.12606