1
Preliminaries: notation and library facts
2
The transformer architecture
3
Document similarity embeddings and problems
4
Fine-grained complexity: hypotheses and intermediate problems
5
Fine-grained reductions between intermediate problems
6
Hardness of document similarity
7
Proof of the \(\gamma \)-MSD hardness (Appendix B)
8
Representational strength of transformers
9
MLP constructions (Appendix D)
Dependency graph
Fundamental Limitations on Subquadratic Alternatives to Transformers
Alman, Yu (blueprint)
1
Preliminaries: notation and library facts
2
The transformer architecture
3
Document similarity embeddings and problems
4
Fine-grained complexity: hypotheses and intermediate problems
5
Fine-grained reductions between intermediate problems
6
Hardness of document similarity
7
Proof of the \(\gamma \)-MSD hardness (Appendix B)
8
Representational strength of transformers
9
MLP constructions (Appendix D)