金恺 Kai Jin 副教授Associate Professor 中山大学智能工程学院 SYSU-School of Intelligent Systems Engineering cscjjk@gmail.com

Brief introduction

I joined SYSU (School of Intelligent Systems Engineering) on July 2020,
as a member of Hundred talents program of Sun Yat sen University.
Previously, I was a postdoc in HKU (2016-2018) and in HKUST (2018-2020).

I am most interested in solving open problems that have clean definitions in theoretical computer science. My current research area includes:
- Computational Geometry
- Game Theory
- Algorithm Design
- Combinatorics
- Discrete and Convex Geometry

I am recruiting self-motivated (master) students who are good at mathematics or computer programming.

Education background

B.S., Special Pilot CS Class (YAO class), Tsinghua University (2008）
Ph.D, Theoretical Computer Science, Tsinghua University (2016)  
My supervisor is Prof Andrew C. Yao. My PhD. Thesis is shown in the following.

When Convexity Meets Parallelism – a New Geometric Structure and Its Application See http://arxiv.org/abs/1512.03897 Supervised by Prof Andrew Yao and Haitao Wang

Journal publications

• Sum-of-Max Partition under a Knapsack Constraint
  Computers and Electrical Engineering (Volume 105, Jan 2023)
  Coauthors: D. Zhang, C. Zhang

• Latin Matchings and Ordered Designs OD(n − 1, n, 2n − 1)
  Mathematics (10(24), 4703; 11 Dec 2022)
  Coauthors: T. Zhu, Z. Gu, X. Sun

• A Generalization of Self-Improving Algorithms
  ACM Transactions on Algorithms (Volume 18, July 2022)
  Coauthors: S. Cheng, M. Chiu, M.T. Wong

• Fast Algorithms for Computing the Statistics of Pattern Matching
  IEEE Access (Volumne 9, 16 Aug 2021)
  Coauthors: D. Zhang

• Dynamic Task Allocation in Multi-Robot System Based on a Team Competition Model
  Frontiers in Neurorobotics (Volumne 15, 20 May 2021)
  Coauthors: P. Tang, S. Chen, J. Peng

• On 1-factorizations of Bipartite Kneser Graphs
  Theoretical Computer Science (Volume 838, 24 October 2020)

• Extensions of Self-Improving Sorters
  Algorithmica (Volume 82, January 2020)
  Coauthors: Siu-Wing Cheng, Lie Yan

• Near-Linear Time Approximation Schemes for Geometric Maximum Coverage
  Theoretical Computer Science (Volume 725, 16 May 2018)
  Coauthors: J. Li, H. Wang, B. Zhang, N. Zhang

• Ascending Sequences with Neighboring Elements add up to Perfect Square Numbers
  Notes on Number Theory and Discrete Mathematics (NNTDM, Volume 23, 2017)

Conference papers

• String Rearrangement Inequalities and a Total Order Between Primitive Words
  16th Conference on Frontiers of Algorithmic Wisdom (FAW’2022)
  Coauthors: R. Luo, T. Zhu

• A Generalization of Self-Improving Algorithms
  36th Symposium on Computational Geometry (SoCG’2020)
  Coauthors: S.-W. Cheng, M.-K. Chiu, M.T. Wong

• Cooperation via Codes in Restricted Hat Guessing Games
  18th Conference in Autonomous Agents and Multiagent Systems (AAMAS’19)
  Coauthors: Ce Jin, Zhaoquan Gu

• On 1-factorizations of Bipartite Kneser Graphs
  25th International Computing and Combinatorics Conference (COCOON’19)

• Optimal Partitioning Which Maximizes the Weighted Sum of Products
  11th International Frontiers of Algorithmics Workshop (FAW’17)
  See the full version here

• Fluctuated Fitting under the $\ell_1$-metric
  11th International Frontiers of Algorithmics Workshop (FAW’17)
  See the full version here

• On the Power of Dominated Players in Team Competitions
  15th Conference in Autonomous Agents and Multiagent Systems (AAMAS’16)
  Coauthors: Pingzhong Tang, Shiteng Chen

• Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach
  27th International Symposium on Algorithms and Computation (ISAAC’16)

• Finding the Maximum Area Parallelogram in a Convex Polygon
  23rd Canadian Conference on Computational Geometry (CCCG’11)
  Coauthor: Kevin Matulef

Unpublished papers

• A Geometric Structure Associated with the Convex Polygon
  Comment: A small world is created here. It is my representative work!

• A Technique for Solving the Polygon Inclusion Problems
  Comment: A general technique for solving many polygon inclusion problems

• Finding all Maximal Area Parallelograms in a Convex Polygon
  Comment: This paper is the full version of my CCCG11 paper.
  Among others, it presents an $O(n^2)$ time algorithm for finding Maximal Area Parallelogram.

Ongoing projects

1. I am looking for more applications of my technique for solving the polygon inclusion problems.
2. I am attracted by some open problems in game theory and will study them recently. I am particularly interested in cooperation and competition between multiple players.
3. I am trying to extend the results given in my PhD. dissertation to the 3d case.
4. I am working on several geometric optimization problems.

Selected honors

2002  Gold medal in China National Olympiad in Informatics
2003  Gold medal in China National Olympiad in Informatics
2005  Champion of ACM/ICPC regional contest, Chengdu (as the team leader)  
2006  19-th place of ACM/ICPC word finals (as the team leader)

Services

I was/am a program committee of - AAMAS’21 - AAMAS’22 - COCOON 2022 - IJTCS-FAW 2022

I was/am a reviewer or sub-reviewer for

• “Journal of Computational Geometry”,
• “Algorithmica”,
• “Information Process Letter”,
• “Discrete Applied Mathematics”,
• “European Symposium of Algorithms”,
• “International Symposium on Algorithms and Computation”,
• “International Conference on Computing and Combinatorics”,
• “International Journal of Foundations of Computer Science”.

Received funding

• National Natural Science Foundation of China (Grant No. 62002394).
• Sun Yat-sen University’s “Hundred Talents Program” research funding.
• Shenzhen Science and Technology Program (Grant No. 202206193000001, 20220817175048002).

Other experiences

I serve as a student coach in China Olympiad Informatics team (2006-2017)
I design creative problems for many Olympic competition of Information, e.g.,

• Ingenious Latin, Fragments, Dead4gon (ACM-HK-regional 2018)
• Cipher (CTSC 2017)
• Daydayup (CTSC 2016)
• Transitivity (CCPC 2016)
• Parallelogram (CCPC 2016)
• Dice (SCOI 2009)
• Polya’s Pocket (NOI2006)
• Shooting Game (CTSC2006)
• Comb and etc. (HNTSC 2005)

Coach for ACM/ICPC in SYSU-school of ISE

I am the head coach for the training of ACM/ICPC in our department.
Please contact me if you are a student from ISE who want to join the training.

APIO2023 lecture note完整版 母函数及DP的综合运用

Teaching (Autumn 2020)

Game Theory (AI frontier lesson 2) Fair-Allocation

Data Structures and Algorithms

slide1 slide2 slide3 slide4 slide5 slide6 slide7 slide8 slide9 slide10 slide11 slide12 slide13 slide14 slide15 slide16 slide17 slide18 slide19 slide20 slide22 slide23 slide24 slide25

Teaching (Spring 2021)

Data Structures and Algorithms

slide1 EXP1 slide2 EXP2 slide3 EXP3 slide4 EXP4 slide5 EXP5 slide6 EXP6=EXAM slide7 EXP7 slide8 EXP8 slide9 EXP9 slide10 EXP10 slide11 EXP11 slide12 EXP12 slide13 EXP13=EXAM slide14 EXP14 slide15 EXP15 slide16 EXP16 slide17 slide18

Teaching (Autumn 2022)

Data Structures and Algorithms

Discrete Mathematics

Operation Research