On the computational complexity of self-attention

MaRDI QIDQ7022754zbMATH OpenFDO

Authors Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, Chinmay Hegde

Publication date 24 February 2025

Full work available at URL https://proceedings.mlr.press/v201/duman-keles23a.html

zbMATH Keywords

complexitylearningself attention

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Cites work

• A new algorithm for optimal 2-constraint satisfaction and its implications
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Fine-grained complexity theory: conditional lower bounds for computational geometry
• Hardness of approximate nearest neighbor search
• If the current clique algorithms are optimal, so is Valiant's parser
• On the complexity of k-SAT
• Quadratic conditional lower bounds for string problems and dynamic time warping
• Tight hardness results for LCS and other sequence similarity measures
• Which problems have strongly exponential complexity?
• Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails

Cited in

(1)

• An efficient deep attention framework for multi-rotor UAVs fault diagnosis

This page was built for publication: On the computational complexity of self-attention

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7022754)