This paper presents a novel characterization of the rank of Boolean functions. Previously considered a key concept in PAC learning theory that enables near-term learning algorithms for polynomial-sized decision trees, we re-characterize the rank of Boolean functions based on the well-known Transformer architecture. Specifically, we show that the rank of a function f matches the minimum number of Chain of Thought (CoT) steps required for a single-layer Transformer using hard attention to compute f. Based on this characterization, we establish a strict bound on the number of CoT steps required for a given problem and prove that exactly ℓ-fold function composition requires ℓ CoT steps. Furthermore, we analyze the problem of identifying the kth occurrence of 1 in a Boolean sequence to prove that k CoT steps are required. Finally, we introduce the concept of multi-head rank, which captures the multi-headed single-layer Transformer, and analyze the PAC learnability of a class of functions with a limited number of multi-head ranks.
