On the derandomization of the graph test for homomorphism over groups
In this article, we study the randomness-efficient graph tests for homomorphism over arbitrary groups (which can be used in locally testing the Hadamard code and PCP construction). We try to optimize both the amortized query complexity and the randomness complexity of the homomorphism test simultaneously. For abelian groups G = Z(p)(m), Gamma = Z(p) and function f : G -> Gamma, by using a lambda-biased set S of size poly(log |G|), we show that, on any given bipartite graph H = (V(1), V(2); E), there exists a graph test for linearity over G with randomness complexity |V(1)|log|G| + |V(2)|O(log log |G|), query complexity |V(1)| + |V(2)| + |E| and if the test accepts f : G -> Gamma with probability at least p(-|E|) + (1 - p(-|E|))delta then f has agreement >= p(-1)(1 + root delta(2)-lambda/2) with some affine linear function. It is a derandomized version of the graph test for linearity of Samorodnitsky and Trevisan (2000) [13]. For general groups G, Gamma land function f : G -> Gamma, we introduce k random walks of some length, l say, on expander graphs to design a probabilistic homomorphism test, which could be thought as a graph test on a graph which is the union of k paths. This gives a homomorphism test over general groups with randomness complexity k log |G| + lO(log log |G|), query complexity k + l + kl and if the test accepts f with probability at least 1 - k mu l(2)/kl(1+mu l-mu)+2 psi(lambda,l), then f is 2 mu/(1 - lambda)-far from being affine homomorphism, here psi(lambda, l) = Sigma(l-1)(t=1) t lambda(l-1-t). It is a graph test version of the derandomized test for homomorphism of Shpilka and Wigderson (2004) [14]. (C) 2010 Elsevier B.V. All rights reserved.
graph test homomorphism over groups lambda-biased set random walk expanding cayley graph