Testing low-degree polynomials over prime fields

DOI10.1002/rsa.20262zbMath1216.94068OpenAlexW3083444063MaRDI QIDQ3055771

Anindya C. Patthak, David Zuckerman, Atri Rudra, Charanjit S. Jutla

Publication date: 9 November 2010

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20262

zbMATH Keywords

polynomialsgeneralized Reed-Muller codelocal correctionlocal testing

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Other types of codes (94B60) Randomized algorithms (68W20)

Related Items

Testing Lipschitz functions on hypergrid domains ⋮ Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Unnamed Item ⋮ Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes ⋮ Breaking the ε-Soundness Bound of the Linearity Test over GF(2) ⋮ Polynomial functions as splines ⋮ Invariance in Property Testing ⋮ Testing Linear-Invariant Non-linear Properties: A Short Report ⋮ On Sums of Locally Testable Affine Invariant Properties ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ Characterizations of locally testable linear- and affine-invariant families ⋮ Testing computability by width-two OBDDs ⋮ Testing algebraic geometric codes ⋮ Reed-Muller Codes ⋮ Lower bounds for testing triangle-freeness in Boolean functions ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities

Cites Work

• Non-deterministic exponential time has two-prover interactive protocols
• Functions and polynomials in vector spaces
• Self-testing/correcting with applications to numerical problems
• Improved low-degree testing and its applications
• Minimum-weight codewords as generators of generalized Reed-Muller codes
• Regular Languages are Testable with a Constant Number of Queries
• Testing Polynomials over General Fields
• Testing Reed–Muller Codes
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques
• Robust Characterizations of Polynomials with Applications to Program Testing
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Robust locally testable codes and products of codes
• On cyclic codes that are invariant under the general linear group
• On generalized ReedMuller codes and their relatives
• Some 3CNF Properties Are Hard to Test