7 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…
A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions
Yuzhou Gu, Xin Li, Yinzhan Xu
We study the query complexity of Boolean functions in the noisy query model introduced by Feige, Raghavan, Peleg and Upfal [SICOMP 1994]. In th…
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…
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,…
Subquadratic Algorithms and Hardness for Attention with Any Temperature
Shreya Gupta, Boyang Huang, Barna Saha +2
Despite the popularity of the Transformer architecture, the standard algorithm for computing Attention suffers from quadratic time complexity in context length . Alman and Song…