3 papers
cs.LG2025
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…
cs.CC2024
The Computational Complexity of Factored Graphs
Shreya Gupta, Boyang Huang, Russell Impagliazzo +2
While graphs and abstract data structures can be large and complex, practical instances are often regular or highly structured. If the instance has sufficient structure, we might h…
cs.CC2024
The Greedy Coin Change Problem
Shreya Gupta, Boyang Huang, Russell Impagliazzo
The Coin Change problem, also known as the Change-Making problem, is a well-studied combinatorial optimization problem, which involves minimizing the number of coins needed to make…