Titlebook: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques; 6th International Wo Sanjeev Arora,Klaus Jansen,Am

SMART

Testing Low-Degree Polynomials over ,(2)monomials). For a given integer . ≥ 1 and a given real . >0, the algorithm queries . at . points. If . is a polynomial of degree at most ., the algorithm always accepts, and if the value of . has to be modified on at least an . fraction of all inputs in order to transform it to such a polynomial, th