Testing low-degree polynomials over prime fields

No abstract is available for this paper.

• Publication year

  2004

• Venue

  45th Annual IEEE Symposium on Foundations of Computer Science

• Publication date

  2004-10-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1002/rsa.20262
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The probabilistic analysis of a greedy satisfiability algorithm

  2006cited by this paper
• Non-deterministic exponential time has two-prover interactive protocols

  2005cited by this paper
• Testing Reed-Muller codes

  2005cited by this paper
• Almost orthogonal linear codes are locally testable

  2005cited by this paper
• Tolerant Locally Testable Codes

  2005cited by this paper
• Testing polynomials over general fields

  2004cited by this paper
• Some 3CNF properties are hard to test

  2003cited by this paper
• Testing Low-Degree Polynomials over GF(2(

  2003cited by this paper
• Minimum-weight codewords as generators of generalized Reed-Muller codes

  2000cited by this paper
• Regular languages are testable with a constant number of queries

  1999cited by this paper
• Probabilistic checking of proofs: a new characterization of NP

  1998cited by this paper
• Improved Low-Degree Testing and its Applications

  1997cited by this paper
• Interactive proofs and the hardness of approximating cliques

  1996cited by this paper
• Robust Characterizations of Polynomials with Applications to Program Testing

  1996influential reference
• Some improvements to total degree tests

  1995cited by this paper
• Proof verification and hardness of approximation problems

  1992cited by this paper
• Checking computations in polylogarithmic time

  1991cited by this paper
• Approximating clique is almost NP-complete

  1991cited by this paper
• Self-testing/correcting for polynomials and for approximate functions

  1991cited by this paper
• Self-testing/correcting with applications to numerical problems

  1990cited by this paper
• Nondeterministic exponential time has two-prover interactive protocols

  1990cited by this paper
• Functions and polynomials in vector spaces

  1987cited by this paper
• On cyclic codes that are invariant under the general linear group

  1970cited by this paper
• On Generalized Reed-Muller Codes and Their Relatives

  1970cited by this paper

• Strong Pseudorandom Functions in AC0[2] in the Bounded-Query Setting

  2025cites this paper
• Homomorphism Testing with Resilience to Online Manipulations

  2025cites this paper
• Polynomial Freiman-Ruzsa, Reed-Muller codes and Shannon capacity

  2024influential citation
• Testing Sumsets is Hard

  2024cites this paper
• Adversarial Low Degree Testing

  2023cites this paper
• A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels

  2023cites this paper
• Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries

  2023cites this paper
• Low-Degree Testing Over Grids

  2023cites this paper
• Reed-Muller Codes

  2023cites this paper
• Property Testing with Online Adversaries

  2023cites this paper
• (Quantum) complexity of testing signed graph clusterability

  2023cites this paper
• Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

  2022cites this paper
• The plane test is a local tester for multiplicity codes

  2022cites this paper
• Improved Optimal Testing Results from Global Hypercontractivity

  2022cites this paper
• Sublinear-Time Computation in the Presence of Online Erasures

  2021cites this paper
• Approximating Sumset Size

  2021cites this paper
• D S ] 2 6 Ju l 2 02 1 Approximating Sumset Size

  2021cites this paper
• Sublinear-Time Computation in the Presence of An Online Adversary

  2021cites this paper
• Properties of High Rank Subvarieties of Affine Spaces

  2019cites this paper
• Polynomial functions as splines

  2019cites this paper
• Higher-order Fourier Analysis and Applications

  2019cites this paper
• Is your function low dimensional?

  2018cites this paper
• Exploring Crypto Dark Matter: - New Simple PRF Candidates and Their Applications

  2018cites this paper
• Is your data low-dimensional?

  2018cites this paper
• Extending weakly polynomial functions from high rank varieties

  2018cites this paper
• Local decoding and testing of polynomials over grids

  2017cites this paper
• Extending linear and quadratic functions from high rank varieties

  2017cites this paper
• Introduction to Property Testing

  2017cites this paper
• Polynomial functions as splines

  2017cites this paper
• On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]

  2016cites this paper
• Robust Testing of Lifted Codes with Applications to Low-Degree Testing

  2015cites this paper
• Linearity and Group Homomorphism Testing / Testing Hadamard Codes

  2015cites this paper
• Lecture Notes on Low Degree Tests

  2015cites this paper
• New error correcting codes from lifting

  2015cites this paper
• Preface to SICOMP ' s Special Issueon Randomness and ComplexityOded

  2014cites this paper
• Algebraic Properties of the Cube Attack

  2013cites this paper
• Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities

  2013cites this paper
• Absolutely Sound Testing of Lifted Codes

  2013cites this paper
• Some closure features of locally testable affine-invariant properties

  2012cites this paper
• New affine-invariant codes from lifting

  2012cites this paper
• A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes

  2012cites this paper
• Every locally characterized affine-invariant property is testable

  2012cites this paper
• MONTAGE: A Methodology for Designing Composable End-to-End Secure Distributed Systems

  2012cites this paper
• Testing Lipschitz Functions on Hypergrid Domains

  2012cites this paper
• Guest column: testing linear properties: some general theme

  2011cites this paper
• Limits on the Rate of Locally Testable Affine-Invariant Codes

  2011cites this paper
• Hard Functions for Low-Degree Polynomials over Prime Fields

  2011cites this paper
• Sublinear Time Algorithms

  2011cites this paper
• New Extension of the Weil Bound for Character Sums with Applications to Coding

  2011cites this paper
• Nearly tight bounds for testing function isomorphism

  2011cites this paper
• Characterizations of locally testable linear- and affine-invariant families

  2011cites this paper
• Symmetric Functions Capture General Functions

  2011cites this paper
• Optimal Testing of Multivariate Polynomials over Small Prime Fields

  2011influential citation
• Testing Linear Properties: Some general themes

  2011cites this paper
• On Sums of Locally Testable Affine Invariant Properties

  2011cites this paper
• Algebraic Property Testing

  2011cites this paper
• Separations of Matroid Freeness Properties

  2010cites this paper
• Algorithmic and Analysis Techniques in Property Testing

  2010cites this paper
• Testing of exponentially large codes, by a new extension to Weil bound for character sums

  2010cites this paper
• A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security

  2010cites this paper
• Property Testing via Set-Theoretic Operations

  2010cites this paper
• Local list-decoding and testing of random linear codes from high error

  2010cites this paper
• Invariance in Property Testing

  2010influential citation
• Lower bounds for testing triangle-freeness in Boolean functions

  2010cites this paper
• A Fourier-Analytic Approach to Reed–Muller Decoding

  2010cites this paper
• Testing Linear-Invariant Non-linear Properties: A Short Report

  2010cites this paper
• Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2)

  2010cites this paper
• Breaking the Epsilon-Soundness Bound of the Linearity Test over GF(2)

  2010cites this paper
• Succinct Representation of Codes with Applications to Testing

  2009cites this paper
• Tolerant Linearity Testing and Locally Testable Codes

  2009cites this paper
• Optimal Testing of Reed-Muller Codes

  2009cites this paper
• Testing Computability by Width-Two OBDDs

  2009cites this paper
• Green's conjecture and testing linear-invariant properties

  2009cites this paper
• Testing algebraic geometric codes

  2009cites this paper
• Breaking the epsilon-Soundness Bound of the Linearity Test over GF(2)

  2008cites this paper
• Testing Linear-Invariant Non-Linear Properties

  2008cites this paper
• Linearity Testing/Testing Hadamard Codes

  2008cites this paper
• Algebraic property testing: the role of invariance

  2008influential citation
• Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols

  2008cites this paper
• 2 KEY RESULTS

  2007cites this paper
• Property Testing: A Learning Theory Perspective

  2007cites this paper
• List decoding and property testing of error-correcting codes

  2007cites this paper
• Error correcting codes: local testing, list decoding, and applications

  2007cites this paper
• Testing for Concise Representations

  2007cites this paper
• Testing for Concise Representations

  2007cites this paper
• Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols

  2007cites this paper
• Long Extended BCH Codes Are Spanned by Minimum Weight Words

  2006cites this paper
• New correlation bounds for GF(2) polynomials using Gowers uniformity

  2006cites this paper
• Almost orthogonal linear codes are locally testable

  2005cites this paper
• Gowers uniformity, influence of variables, and PCPs

  2005cites this paper
• Testing Reed-Muller codes

  2005cites this paper
• Testing polynomials over general fields

  2004influential citation
• Malicious Security Comes (almost) for Free in Private Information Retrieval

  year unknowncites this paper