I am interested in designing efficient and exact algorithms for solving intractable combinatorial optimization problems.

My research can be divided into two main parts: general theory and focal theory.

The general theory focuses on the principles of algorithm design, we employ a formal formalism, known as transformational programming,  to design reliable and efficient algorithms. We show that classical combinatorial optimization methods, such as dynamic programming, greedy, branch-and-bound, and divide-and-conquer can all be characterised in the same framework and derived from brute-force algorithms.

The focus theory is centered on developing practical algorithms for solving machine learning problems, particularly those involving finite points and hyperplanes. For example, we have designed exact algorithms to solve classification problems, K-clustering, decision tree optimization, and empirical risk minimization (ERM) for ReLU neural networks. All the algorithms developed within our framework are polynomial-time in the worst case and embarrassingly parallelizable.

Experience

Education

• Dec. 2021- present: I am a third-year PhD student from the Department of Computer Science, University of Birmingham, supervised by Dr. Max. Little.
• Sept. 2017- June 2021: Bachelor of Science at Zhejiang Normal University. Where I majored in Mechanical Design Manufacturing and Automation.

Research

• An efficient, provably exact, practical algorithm for the 0-1 loss linear classification problem Xi He, Waheed Ul Rahman, Max A. Little (Under review)
• Dynamic programming by polymorphic algebraic shortcut fusion Max A. Little, Xi He, Ugur Kayas, Formal Aspects of Computing (in press).
• EKM: An exact, polynomial-time algorithm for the K-medoids problem Xi He, Max A. Little (Under review).
• The first empirical risk minimization algorithm for the ReLU neural networks Xi He, Max A. Little (in preparation).
• Optimal decision tree algorithms: A divide-and-conquer approach Xi He, Max A. Little (in preparation).
• Recursive optimization: Exact and efficient combinatorial optimization algorithm design principles Xi He, Max A. Little (in preparation).

All the papers that are in preparation can be found in the discussion of my (draft) thesis Recursive optimization framework.

Software

You can find the Python implementations of my algorithms from my Git repositories.

Activities

• 2-6 April, 2023 Attending Midlands Graduate School 2023 (bham.ac.uk), Birmingham, UK
• 13 June, 2023 Attending Advances in Data Science and AI Conference 2023 (manchester.ac.uk), Manchester

Profile

My name is Xi He, which is the Chinese transcription of “何希”, “Xi” pronounce as “She”, it means “hope” in Chinese.

I enjoy lifting weights, basketball and hiking in my free time. I also write some blogs sometimes.