15 citations · 58 across the 17 of their papers we have counts for
5 papers · 1 filter
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…
Removing Additive Structure in 3SUM-Based Reductions
Ce Jin, Yinzhan Xu
Our work explores the hardness of SUM instances without certain additive structures, and its applications. As our main technical result, we show that solving SUM on a size-$n…
Approximation Algorithms and Hardness for -Pairs Shortest Paths and All-Nodes Shortest Cycles
Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams +1
We study the approximability of two related problems on graphs with nodes and edges: -Pairs Shortest Paths (-PSP), where the goal is to find a shortest path between $…
Constructive Separations and Their Consequences
Lijie Chen, Ce Jin, Rahul Santhanam +1
For a complexity class and language , a constructive separation of gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for…
Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
Ce Jin, Yinzhan Xu
The main theme of this paper is using -dimensional generalizations of the combinatorial Boolean Matrix Multiplication (BMM) hypothesis and the closely-related Online Matrix Vect…