Error Correcting Codes, finding polynomials of bounded degree agreeing on a dense fraction of a set of points

2020/06/29 by Priyank Deshpande, Deshpande, Priyank
Computer Science · Engineering · #Coding theory and cryptography #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Symbolic Computation (cs.SC) #cs.DS #cs.SC #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2007.00445

arxiv created 2020/06/29 · openalex publication_date 2020/06/29 · arxiv updated 2020/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Here we present some revised arguments to a randomized algorithm proposed by Sudan to find the polynomials of bounded degree agreeing on a dense fraction of a set of points in \mathbbF² for some field \mathbbF.

Related

• Bias vs structure of polynomials in large fields, and applications in information theory
• Polynomial evaluation over finite fields: new algorithms and complexity bounds
• Points-Polynomials Incidence Theorem with Applications to Coding Theory
• Algorithmic regularity for polynomials and applications
• Computing points in connected components defined by a real inequation: algorithms, complexity and implementations, Part I