2 citations · 2 across the 9 of their papers we have counts for
6 papers · 1 filter
Online Tokenization with Optimal Delay in Linear Time
Mina Dalirrooyfard, Christopher Ye
Tokenization is an essential preprocessing step in almost all large language models (LLMs). One of the most popular frameworks is BPE tokenization, which consists of special token…
Almost Optimal Multiple Source Shortest Paths and Reachability
Barna Saha, Yinzhan Xu, Christopher Ye
Given a graph, computing distances and reachabilities from a small set of vertices to the whole graph is an important primitive both in theory and in practice. In undirected unweig…
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…
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…
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…
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems
Monika Henzinger, Barna Saha, Martin P. Seybold +1
{\em Algorithms with predictions} incorporate machine learning predictions into algorithm design. A plethora of recent works incorporated predictions to improve on worst-case optim…