2 citations · 5 across the 6 of their papers we have counts for
14 papers · 1 filter
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…
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…
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions
Lijie Chen, Ce Jin, R. Ryan Williams +1
We consider low-space algorithms for the classic Element Distinctness problem: given an array of input integers with bit-length, decide whether or not all elements…
Near-Optimal Quantum Algorithms for String Problems
Shyan Akmal, Ce Jin
We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. Th…