6 papers · 1 filter
LLCT: Learnable Linear Canonical Transform Family with Stability for Visual Feature Processing
Zunwei Fu, Zhen Wang, Dachun Yang +1
Visual structures are often characterized by directional geometry, local oscillation, and spatial--frequency coupling. To overcome the limitations of conventional spatial convoluti…
Faster Deterministic Approximation for Counting Knapsack
Ce Jin, Jaewoo Park, Barna Saha
Given nonnegative integer weights and an integer knapsack capacity , the Knapsack problem asks to count the number of subsets $I \subseteq \{1, 2, \do…
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 pro…
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…