9 papers
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…
Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH
Barna Saha, Yinzhan Xu, Christopher Ye
Several fundamental problems in computational geometry admit algorithms with running time for points in dimensions, making them among the most pr…
Deterministic Monotone Min-Plus Product and Convolution
Ce Jin, Jaewoo Park, Barna Saha +1
The Monotone Min-Plus Product problem is a useful primitive that has seen many algorithmic applications over the past decade. In this problem, we are given two integer…
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…
Hardness of Dynamic Tree Edit Distance and Friends
Bingbing Hu, Jakob Nogler, Barna Saha
String Edit Distance is a more-than-classical problem whose behavior in the dynamic setting, where the strings are updated over time, is well studied. A single-character substituti…
Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Hadley Black, Arya Mazumdar, Barna Saha +1
The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components,…