3 papers
cs.LG2026
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…
cs.LG2025
Learning Compositional Functions with Transformers from Easy-to-Hard Data
Zixuan Wang, Eshaan Nichani, Alberto Bietti +4
Transformer-based language models have demonstrated impressive capabilities across a range of complex reasoning tasks. Prior theoretical work exploring the expressive power of tran…
stat.ML2024
Transformers Provably Learn Sparse Token Selection While Fully-Connected Nets Cannot
Zixuan Wang, Stanley Wei, Daniel Hsu +1
The transformer architecture has prevailed in various deep learning settings due to its exceptional capabilities to select and compose structural information. Motivated by these ca…