Testing low-degree polynomials over prime fields
From MaRDI portal
Publication:3055771
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
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