Lower bounds for one-layer transformers that compute parity

Daniel Hsu

This note shows that no self-attention layer post-processed by a rational function can sign-represent the parity function unless the product of the number of heads and the degree o…