5 papers · 2 filters
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…