Computing Boolean Functions on Cayley Networks (Extended Abstract)

摘要

The bit complexity (i.e., total number of bits transmitted) of computing booleanfunctions on anonymous Cayley networks is studied. Algorithms for computing Boolean functions in all such networks are given. The results give even better complexity bounds for several well known networks: rings, tori, hypercubes and star, pancake and bubble sort networks.