Seminar

We typically have seminars on Wednesday at noon in Malone 228.  All seminar announcements will be sent to the theory mailing list.

Nov
29
Wed
[Theory Seminar] Samson Zhou
Nov 29 @ 12:00 pm – 1:00 pm

Speaker: Samson Zhou
Affiliation: Purdue University

Title: TBA

Abstract: TBA

Dec
6
Wed
[Theory] Venkata Gandikota @ Malone 228
Dec 6 @ 12:00 pm – 1:00 pm

Speaker: Venkata Gandikota
Affiliation: Johns Hopkins University

Title: NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem

Abstract: Establishing the complexity of Bounded Distance Decoding for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when it is efficiently solvable (i.e., the Johnson radius).

We show the first NP-hardness results for asymptotically smaller decoding radii than the maximum likelihood decoding radius of Guruswami and Vardy. Specifically, for Reed-Solomon codes of length N and dimension K = O(N), we show that it is NP-hard to decode more than N-K-O(log N / log log N) errors.

These results follow from the NP-hardness of a generalization of the classical Subset Sum problem to higher moments, called Moments Subset Sum, which has been a known open problem, and which may be of independent interest. We further reveal a strong connection with the well-studied Prouhet-Tarry-Escott problem in Number Theory, which turns out to capture a main barrier in extending our techniques. We believe the Prouhet-Tarry-Escott problem deserves further study in the theoretical computer science community.

This is a joint work with Badih Ghazi (MIT) and Elena Grigorescu (Purdue).