Ce Jin
I am a third-year PhD student at MIT. I am fortunate to be co-advised by Virginia Vassilevska Williams and Ryan Williams. Previously, I was an undergraduate student in Yao Class, Tsinghua University.
I am interested in theoretical computer science, in particular fine-grained complexity and algorithms. (CV)
Еmаil: cejin at mit dot edu
Manuscripts
Publications
Faster Algorithms for Text-to-Pattern Hamming Distances
Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, and Yinzhan Xu
To appear 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)
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
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)
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, 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)
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
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)
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
My {surname + given name} in Chinese: 金策 (鏼)
Competitive programming: Codeforces, Topcoder, AtCoder. A team photo.
Sudoku speed solving: Fed-SuDoKu