Seminar| Institute of Mathematical Sciences
Time: Wednesday, August 5th 2026,15:00-16:00
Location: IMS S408
Speaker: Chen Yuan, Shanghai Jiao Tong University
Abstract: Linear error-correcting codes play a crucial role in pseudorandom correlation generator and secure multiparty computation. Basically, the key to practical efficiency is a linear code with a concretely fast encoding and a high minimum distance. However, to date, none of the candidate codes achieves the best of the two worlds: codes with provable high minimum distance, e.g., Reed-Solomon codes, suffer from quasi-linear time encoding, while linear-time encodable codes, e.g., Spielman's code, have low provable minimum distance. In this work, we resolve this problem by explicitly constructing a family of Quasi-Abelian (QA) codes over arbitrarily large prime fields with concretely high minimum distance and practically efficient encoding algorithms. At the heart of our technical contribution is a fine-grained analysis on the concrete minimum distance of random QA codes. We show that in practical regimes it attains the well-known Gilbert-Varshamov bound up to a small constant gap n/(c log2 p).