Ce Jin (金策)
I am a Miller Postdoctoral Fellow at UC Berkeley, hosted by Jelani Nelson.
I recently completed my PhD at MIT, co-advised by Virginia Vassilevska Williams and Ryan Williams. Before that, I was an undergraduate student in Yao Class, Tsinghua University. (CV)
Email: cejin@berkeley.edu or 2014jcvb@gmail.com
I have a broad interest in theoretical computer science, in particular on fine-grained complexity and algorithm design. I study algorithms and conditional lower bounds for fundamental computational problems in combinatorial optimization, pattern matching, graph theory, and computational geometry. I am also interested in algorithmic applications of algebraic methods and additive combinatorics.
Publications
Near-Optimal Property Testers for Pattern Matching
Ce Jin and Tomasz Kociumaka
To appear in Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025)
New Algorithms for Pigeonhole Equal Subset Sum
Ce Jin, Ryan Williams, and Stan Zhang
To appear in Proceedings of the 33rd Annual European Symposium on Algorithms (ESA 2025)
All-Pairs Shortest Paths with Few Weights per Node
Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, and Zoe Xi
In Proceedings of the 57th ACM Symposium on Theory of Computing (STOC 2025)
Approximately Counting Knapsack Solutions in Subquadratic Time
Weiming Feng and Ce Jin
In Proceedings of the 36th ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
Nick Fischer, Ce Jin, and Yinzhan Xu
In Proceedings of the 36th ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
Beyond 2-approximation for k-Center in Graphs
Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams, and Nicole Wein
In Proceedings of the 36th ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)
A Faster Algorithm for Pigeonhole Equal Sums
Ce Jin and Hongxun Wu
In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Best Student Paper Award
Streaming Algorithms for Connectivity Augmentation
Ce Jin, Michael Kapralov, Sepideh Mahabadi, and Ali Vakilian
In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
Ce Jin and Yinzhan Xu
In Proceedings of the 56th ACM Symposium on Theory of Computing (STOC 2024)
Invited to SICOMP special issue
Danny Lewin Best Student Paper Award
0-1 Knapsack in Nearly Quadratic Time
Ce Jin
In Proceedings of the 56th ACM Symposium on Theory of Computing (STOC 2024)
(see also independent work by Bringmann)
A VLSI Circuit Model Accounting for Wire Delay
Ce Jin, Ryan Williams, and Nathaniel Young
In Proceedings of the 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation
Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams, and Zixuan Xu
In Proceedings of the 35th ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel–Ziv Factorization
Daniel Gibney, Ce Jin, Tomasz Kociumaka, and Sharma V. Thankachan
In Proceedings of the 35th ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)
Ce Jin, Virginia Vassilevska Williams, and Renfei Zhou
In Proceedings of the 7th SIAM Symposium on Simplicity in Algorithms (SOSA 2024)
Faster Algorithms for Text-to-Pattern Hamming Distances
Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, and Yinzhan Xu
In Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS 2023)
An Efficient Algorithm for All-Pairs Bounded Edge Connectivity
Shyan Akmal and Ce Jin
In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Journal version in Algorithmica
Removing Additive Structure in 3SUM-Based Reductions
Ce Jin and Yinzhan Xu
In Proceedings of the 55th ACM Symposium on Theory of Computing (STOC 2023)
Invited to SICOMP special issue
Journal version in SICOMP
Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching
Ce Jin and Jakob Nogler
In Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
slides@IRIF Jakob's slides@SODA
Journal version in TALG
Approximating Knapsack and Partition via Dense Subset Sums
Mingyang Deng, Ce Jin, and Xiao Mao
In Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA 2023)
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams, and Nicole Wein
In Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022)
Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
Ce Jin and Yinzhan Xu
In Proceedings of the 54th ACM Symposium on Theory of Computing (STOC 2022)
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity
Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, and Ryan Williams
In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Journal version in Algorithmica
Near-Optimal Quantum Algorithms for String Problems
Shyan Akmal and Ce Jin
In Proceedings of the 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)
Accepted as a regular talk at Quantum Information Processing (QIP) 2022
Journal version in Algorithmica
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions
Lijie Chen, Ce Jin, Ryan Williams, and Hongxun Wu
In Proceedings of the 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)
Constructive Separations and Their Consequences
Lijie Chen, Ce Jin, Rahul Santhanam, and Ryan Williams
In Proceedings of the 62nd IEEE Symposium on Foundations of Computer Science (FOCS 2021)
Journal version in TheoretiCS
Faster Algorithms for Bounded Tree Edit Distance
Shyan Akmal and Ce Jin
In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
An Improved Sketching Algorithm for Edit Distance
Ce Jin, Jelani Nelson, and Kewen Wu
In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Fast Low-Space Algorithms for Subset Sum
Ce Jin, Nikhil Vyas, and Ryan Williams
In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)
Fast and Simple Modular Subset Sum
Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, and Hongxun Wu
In Proceedings of the 4th SIAM Symposium on Simplicity in Algorithms (SOSA 2021)
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
Mohsen Ghaffari, Christoph Grunau, and Ce Jin
In Proceedings of the 34th International Symposium on Distributed Computing (DISC 2020)
A Massively Parallel Algorithm for Minimum Weight Vertex Cover
Mohsen Ghaffari, Ce Jin, and Daan Nilis
In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)
Sharp Threshold Results for Computational Complexity
Lijie Chen, Ce Jin, and Ryan Williams
In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC 2020)
Hardness Magnification for all Sparse NP Languages
Lijie Chen, Ce Jin, and Ryan Williams
In Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS 2019)
An Improved FPTAS for 0-1 Knapsack
Ce Jin
In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Faster Algorithms for All Pairs Non-decreasing Paths Problem
Ran Duan, Ce Jin, and Hongxun Wu
In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Cooperation via Codes in Restricted Hat Guessing Games
Kai Jin, Ce Jin, and Zhaoquan Gu
In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019)
Simulating Random Walks on Graphs in the Streaming Model
Ce Jin
In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum
Ce Jin and Hongxun Wu
In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Fast Modular Subset Sum using Linear Sketching
Kyriakos Axiotis, Arturs Backurs, Ce Jin, Christos Tzamos, and Hongxun Wu
In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
Misc
Competitive programming: Codeforces, Topcoder, AtCoder. A team photo.
Sudoku speed solving: Fed-SuDoKu