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. 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 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 D. |
Year | Venue | DocType |
---|---|---|
2019 | Electronic Colloquium on Computational Complexity (ECCC) | Journal |
Volume | Citations | PageRank |
26 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Srikanth Srinivasan | 1 | 132 | 21.31 |
Utkarsh Tripathi | 2 | 1 | 3.05 |
S. Venkitesh | 3 | 1 | 3.05 |