Testing low-degree polynomials over prime fields

DOI10.1002/RSA.20262MaRDI QIDQ3055771zbMATH OpenOpenAlexFDO

Authors Anindya C. Patthak, Atri Rudra, David Zuckerman, C. 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

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

Recommendations

• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Optimal testing of multivariate polynomials over small prime fields
• Testing Polynomials over General Fields
• Local decoding and testing of polynomials over grids
• Optimal testing of Reed-Muller codes

Cites work

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

Cited in

(32)

• On Sums of Locally Testable Affine Invariant Properties
• Low-degree tests at large distances
• On the bias of Reed-Muller codes over odd prime fields
• Polynomial fitting of data streams with applications to codeword testing
• Local decoding and testing of polynomials over grids
• Local decoding and testing of polynomials over grids
• Improved optimal testing results from global hypercontractivity
• Testing Lipschitz functions on hypergrid domains
• Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
• Polynomial functions as splines
• Exploring crypto dark matter: new simple PRF candidates and their applications
• Testing Linear-Invariant Non-linear Properties: A Short Report
• A new upper bound on the query complexity for testing generalized Reed-Muller codes
• Exponentially improved algorithms and lower bounds for testing signed majorities
• Hard functions for low-degree polynomials over prime fields
• Reed-Muller Codes
• Characterizations of locally testable linear- and affine-invariant families
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Algorithmic regularity for polynomials and applications
• Invariance in property testing
• Smoothness testing of polynomials over finite fields
• Hard functions for low-degree polynomials over prime fields
• Testing algebraic geometric codes
• Robust multiplication-based tests for Reed-Muller codes
• Optimal testing of multivariate polynomials over small prime fields
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Testing Low Degree Trigonometric Polynomials
• Lower bounds for testing triangle-freeness in Boolean functions
• Property testing with online adversaries
• Testing Polynomials over General Fields
• Testing computability by width-two OBDDs
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

This page was built for publication: Testing low-degree polynomials over prime fields

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