Computing boolean functions on anonymous hypercube networks : extended abstract
Evangelos Kranakis, Danny Kriz̧anc · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1990
Abstract: "We study the bit-complexity (i.e. total number of bits transmitted) of computing boolean functions on anonymous oriented hypercubes. We characterize the class of boolean functions computable in the anonymous oriented hypercube as exactly those boolean functions which are invariant under all bit-complement automorphisms of the hypercube and provide an algorithm for computing all such functions with bit complexity O(N [times] log4 N). Thus among all studied oriented networks (rings, tori, etc) the hypercube seems to achieve 'optimal' bit complexity for a given number of nodes."