Pseudorandom binary functions on rooted plane trees
Pascal Hubert, Katalin Gyarmati, Andràs Sárközy · Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) · 2012
In an earlier paper the authors considered r-almost s-uniform trees, i.e. rooted planar trees T such that the root has r successors, and every other vertex has s successors.They considered binary functions f : V(T ) → {-1, +1} defined on the set V(T ) of the vertices of such a tree T and studied the pseudorandomness of binary functions of this type.Here the authors extend the problem to general rooted plane trees: the measures of pseudorandomness of binary functions defined on trees of this type are introduced; the connection between these measures is analyzed; the size of these measures for truly random binary functions is studied; binary functions with strong pseudorandom properties are constructed; pseudorandom properties of important special binary functions are studied.