3 papers
cs.DS2024
Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu +1
Single Source Shortest Paths () is among the most well-studied problems in computer science. In the incremental (resp. decremental) setting, the goal is to maintain…
cs.LG2024
The I/O Complexity of Attention, or How Optimal is Flash Attention?
Barna Saha, Christopher Ye
Self-attention is at the heart of the popular Transformer architecture, yet suffers from quadratic time and memory complexity. The breakthrough FlashAttention algorithm revealed I/…
cs.DS2023
Faster Approximate All Pairs Shortest Paths
Barna Saha, Christopher Ye
The all pairs shortest path problem (APSP) is one of the foundational problems in computer science. For weighted dense graphs on vertices, no truly sub-cubic algorithms exist t…