15 citations · 58 across the 17 of their papers we have counts for
22 papers
Streaming Algorithms for Connectivity Augmentation
Ce Jin, Michael Kapralov, Sepideh Mahabadi +1
We study the -connectivity augmentation problem (-CAP) in the single-pass streaming model. Given a -edge connected graph that is stored in memory, and a stre…
Solving Knapsack with Small Items via L0-Proximity
Ce Jin
We study pseudo-polynomial time algorithms for the fundamental \emph{0-1 Knapsack} problem. In terms of and , previous algorithms for 0-1 Knapsack have cubic time com…
0-1 Knapsack in Nearly Quadratic Time
Ce Jin
We study pseudo-polynomial time algorithms for the fundamental \emph{0-1 Knapsack} problem. Recent research interest has focused on its fine-grained complexity with respect to the…
An Efficient Algorithm for All-Pairs Bounded Edge Connectivity
Shyan Akmal, Ce Jin
Our work concerns algorithms for an unweighted variant of Maximum Flow. In the All-Pairs Connectivity (APC) problem, we are given a graph on vertices and edges, and are…
Approximating Knapsack and Partition via Dense Subset Sums
Mingyang Deng, Ce Jin, Xiao Mao
Knapsack and Partition are two important additive problems whose fine-grained complexities in the -approximation setting are not yet settled. In this work, we make…
Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching
Ce Jin, Jakob Nogler
Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS…