Bounds for Cube Coloring
Barton R. Plumstead, Joan B. Plumstead · SIAM Journal on Algebraic and Discrete Methods · 1985
An n-cube is properly colored if each vertex having an even number of ones is colored white and each vertex having an odd number of ones is colored black. This paper considers programs that color the n-cube with a coloring operation that in one step colors all uncolored vertices of a subcube either all black or all white and leaves previously colored vertices as before. An upper bound of $1.06 ( \sqrt[3]{5} )^n $ steps and a lower bound of $\frac{4}{3} ( 1.5 )^n $ steps for coloring the n-cube are proved. There are relationships between this model of computation and both width-two branching programs and depth 3 circuits for parity.