Showing 2024Show all
3 papers · 1 filter
cs.DS2024
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
Jakob Nogler, Adam Polak, Barna Saha +3
The tree edit distance (TED) between two rooted ordered trees with nodes labeled from an alphabet is the minimum cost of transforming one tree into the other by a sequence…
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/…