| Partner: Barcelo Pablo |
Prace konferencyjne
| 1. | Pablo B.♦, Kozachinskiy A.♦, Steifer T., Ehrenfeucht-Haussler Rank and Chain of Thought, PMLR, 42nd International Conference on Machine Learning, 2025-07-13/07-19, Vancouver (CA), Vol.267, No.2968-2977, pp.1-10, 2025 Streszczenie: The notion of rank of a Boolean function has been a cornerstone in PAC learning, enabling quasipolynomial-time learning algorithms for polynomial-size decision trees. We present a novel characterization of rank, grounded in the well-known Transformer architecture. We show that the rank of a function f corresponds to the minimum number of Chain of Thought (CoT) steps required by a single-layer Transformer with hard attention to compute f. Based on this characterization we establish tight bounds on the number of CoT steps required for specific problems, showing that ℓ-fold function composition necessitates exactly ℓ CoT steps. Furthermore, we analyze the problem of identifying the position of the k-th occurrence of 1 in a Boolean sequence, proving that it requires k CoT steps Afiliacje autorów:
|  |