Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
On the Computational Hardness of Transformers
Barna Saha, Yinzhan Xu, Christopher Ye +1
The transformer has revolutionized modern AI across language, vision, and beyond. It consists of layers, each running attention heads in parallel and feeding the combined o…
cs.CC2025
Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
Mina Dalirrooyfard, Andrea Lincoln, Barna Saha +1
This work establishes conditional lower bounds for average-case {\em parity}-counting versions of the problems -XOR, -SUM, and -OV. The main contribution is a set of self-…