Attention-based representations for multi-task computation
It is proved that a single attention head requires exponentially higher embedding dimension or precision level and generalize to arbitrary (symmetric) Boolean functions, where the bound is given in terms of the threshold degree.