TY - GEN
T1 - Derandomizing graph tests for homomorphism
AU - Li, Angsheng
AU - Tang, Linqing
PY - 2008
Y1 - 2008
N2 - 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 , 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 -far from being affine linear. For a non-abelian group G, we introduce a random walk of some length, l say, on expander graphs to design a probabilistic homomorphism test over G with randomness complexity log|G|+O(loglog|G|), query complexity 2l+1 and error probability at most for any f which is 2δ/(1-λ)-far from being affine homomorphism, here .
AB - 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 , 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 -far from being affine linear. For a non-abelian group G, we introduce a random walk of some length, l say, on expander graphs to design a probabilistic homomorphism test over G with randomness complexity log|G|+O(loglog|G|), query complexity 2l+1 and error probability at most for any f which is 2δ/(1-λ)-far from being affine homomorphism, here .
UR - https://www.scopus.com/pages/publications/70349316949
U2 - 10.1007/978-3-540-79228-4_9
DO - 10.1007/978-3-540-79228-4_9
M3 - 会议稿件
AN - SCOPUS:70349316949
SN - 3540792279
SN - 9783540792277
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 105
EP - 115
BT - Theory and Applications of Models of Computation - 5th International Conference, TAMC 2008, Proceedings
PB - Springer Verlag
T2 - 5th International Conference on Theory and Applications of Models of Computation, TAMC 2008
Y2 - 25 April 2008 through 29 April 2008
ER -