@inbook{865cbd11052a4325b3f5c76193914389,
title = "Testing low-degree polynomials over GF(2)",
abstract = "We describe an efficient randomized algorithm to test if a given binary function f : {0, 1}n → {0, 1} is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k ≥ 1 and a given real ε > 0, the algorithm queries f at O(1/ε + k4k) points. If f is a polynomial of degree at most k, the algorithm always accepts, and if the value of f has to be modified on at least an ε fraction of all inputs in order to transform it to such a polynomial, then the algorithm rejects with probability at least 2/3. Our result is essentially tight: Any algorithm for testing degree-k polynomials over GF(2) must perform Ω(1/e + 2k) queries.",
author = "Noga Alon and Tali Kaufman and Michael Krivelevich and Simon Litsyn and Dana Ron",
note = "Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",
year = "2003",
doi = "10.1007/978-3-540-45198-3_17",
language = "English (US)",
isbn = "3540407707",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "188--199",
editor = "Sanjeev Asora and Amit Sahai and Klaus Jansen and Rolim, {Jose D.P.}",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
address = "Germany",
}