8 papers · 1 filter
Subset Sum in Almost-Linear Time
Ce Jin, Xiao Mao
We give a deterministic algorithm for finding a subset of the input integers that sums to the target in time. This impro…
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…
Min-Plus Convolution Lower Bounds via a Higher-Order BSG Theorem
Nick Fischer, Ce Jin, Yinzhan Xu
Min-Plus Convolution is a central problem in fine-grained complexity, and the associated Min-Plus Convolution Hypothesis forms the basis for a wide range of conditional lower bound…
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…
Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
Bartłomiej Dudek, Nick Fischer, Geri Gokaj +4
We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schul…
New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
Nick Fischer, Ce Jin, Yinzhan Xu
The 3SUM problem is one of the cornerstones of fine-grained complexity. Its study has led to countless lower bounds, but as has been sporadically observed before -- and as we will…
Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
Ce Jin, Yinzhan Xu
In sparse convolution-type problems, a common technique is to hash the input integers modulo a random prime for some parameter , which reduces the range of the in…
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization
Daniel Gibney, Ce Jin, Tomasz Kociumaka +1
Classically, the edit distance of two length- strings can be computed in time, whereas an -time procedure would falsify the Orthogonal Vectors Hypothesis. I…