Download Proceedings of the 6th Workshop on Algorithm Engineering and by Lars Arge PDF

F and a row through x0 (column through y0) the row ( column ) polynomial, is the univariate polynomial 32 3. Low-degree tests r��, d) (c£�· d) ) of degree d which agrees with f on the most points on the row (column). Ties may be broken arbitrarily. The neighborhoods for this test consists of all sets of d + 2 points from a single row or from a single column. 2. 3 shows that the distance of f from a bivariate polynomial of degree d is within a constant multiplicative factor of the number of violated constraints.

D+ 1}] 2: 1-8, where the probability is t aken over the uniform distribution over all d + 2tuples < xo, . . , p(d)[x] ) � 8. Proof: Let g be the degree d polynomial which minimizes d(f, g) and let the distance between f and g be [/. Now fix z0, ... , Zd and let h be the unique degree d polynomial such that h(zi) = f(zi), for i E { 0 , . . , d}. By the definition of we have that 8', Thus Pr [3pE p(d )[x] s . t . ViE {0, . . , d + 1}, p (xi) =! (xi)] max Pr [poly through . , Zd also passes through Xd+I] xo, ...

1 (  ) . Given oracles for a sequence of functions f( l ) , . . , f( l ) , an oracle for an initial polynomial g(o), and a construction rule r1 , , rz of width w for degree d polynomials g( l ) , . . , g(l) (g( i ) : pm -> F} there ezists a tester which verifies that the f(i ) is 6-close to g(i) for all i E { 1 , . . , l} . Moreover the test probes the sequence f in poly ( l, w , d) points. • . Proof: The tester for this sequence steps through the sequence establishing inductively that f(i ) is 6-close to g(i).