Local decoding and testing of polynomials over grids

DOI10.4230/LIPICS.ITCS.2018.26MaRDI QIDQ4993289zbMATH OpenFDO

Authors Srikanth Srinivasan, Madhu Sudan

Publication date 15 June 2021

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2018.26

zbMATH Keywords

property testingcoding theorylow-degree testinglocal testinglocal decoding

Mathematics Subject Classification ID

Randomized algorithms (68W20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Decoding (94B35)

Recommendations

• Local decoding and testing of polynomials over grids
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Testing Polynomials over General Fields
• Testing low-degree polynomials over prime fields
• Optimal testing of multivariate polynomials over small prime fields

Cites work

• scientific article; zbMATH DE number 4191094 (Why is no real title available?)
• scientific article; zbMATH DE number 4213418 (Why is no real title available?)
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• A probabilistic remark on algebraic program testing
• Algebraic methods for interactive proof systems
• Algebraic property testing: the role of invariance
• Decoding Reed-Muller codes over product sets
• Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• How to share a secret
• Locally testable codes and PCPs of almost-linear length
• Matching is as easy as matrix inversion
• On the efficiency of local decoding procedures for error-correcting codes
• Optimal testing of Reed-Muller codes
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Some 3CNF Properties Are Hard to Test
• Testing Polynomials over General Fields
• Testing Reed–Muller Codes
• Testing low-degree polynomials over prime fields
• The PCP theorem by gap amplification

Cited in

(3)

• Local decoding and testing of polynomials over grids
• Local Decoding and Testing for Homomorphisms
• Good polynomials for optimal LRC of low locality

This page was built for publication: Local decoding and testing of polynomials over grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993289)