Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-109 | 21st August 2019 13:11

Decoding Downset codes over a finite grid

RSS-Feed




TR19-109
Authors: Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh
Publication: 23rd August 2019 16:39
Downloads: 686
Keywords: 


Abstract:

In a recent paper, Kim and Kopparty (Theory of Computing, 2017) gave a deterministic algorithm for the unique decoding problem for polynomials of bounded total degree over a general grid $S_1\times\cdots \times S_m.$ We show that their algorithm can be adapted to solve the unique decoding problem for the general family of Downset codes. Here, a downset code is specified by a family $\mathcal{D}$ of monomials closed under taking factors: the corresponding code is the space of evaluations of all polynomials that can be written as linear combinations of monomials from $\mathcal{D}.$



ISSN 1433-8092 | Imprint