Derandomizing Graph Tests for Homomorphism

摘要

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-tradeoff (between number of queries and error probability) and the randomness complexity of the homomorphism test simultaneously. For an abelian group G = Z_p~m, by using the λ-biased set S of G, we show that, on any given bipartite graph H = (V_1, V_2; E), the graph test for linearity over G is a test with randomness complexity |V_1|log|G| + |V_2|O(log|S|), query complexity |V_1| + |V_2| + |E| and error probability at most p~(-|E|) + (1 - p~(-|E|)) · δ for any f which is 1 - p~(-1)(1 + √δ~2-λ/2)-far from being affine linear. For a non-abelian group G, we introduce a random walk of some length, e say, on expander graphs to design a probabilistic homomorphism test over G with randomness complexity log |G| + O(log log |G|), query complexity 2e + 1 and error probability at most 1 -δ~2e~2/(δe+δ~2e~2-δ~2e)+2Ψ(λ,e) for any f which is 2δ/(1 - λ)-far from being affine homomorphism, here Ψ(λ, e) = ∑_(0≤i＜j≤e-1 λ~(j-i-1)).