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 , Γ=Zp and function f:G→Γ, by using a λ-biased set S of size poly(log|G|), we show that, on any given bipartite graph H=(V1,V2;E), there exists a graph test for linearity over G with randomness complexity |V1|log|G|+|V2|O(loglog|G|), query complexity |V1|+|V2|+|E| and if the test accepts f:G→Γ with probability at least p−|E|+(1−p−|E|)δ, then f has agreement 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, Γ and function f:G→Γ, we introduce k random walks of some length, ℓ 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 klog|G|+ℓO(loglog|G|), query complexity k+ℓ+kℓ and if the test accepts f with probability at least , then f is 2μ/(1−λ)-far from being affine homomorphism, here . It is a graph test version of the derandomized test for homomorphism of Shpilka and Wigderson (2004) [14].