Tao Zixu He
Logo UNSW Sydney

I am an Honours student at UNSW, fortunate to be supervised by Serge Gaspers and Simon Mackenzie.

My research interests lie in theoretical computer science, with a focus on algorithms, fine-grained complexity and computational social choice.

Google Scholar GitHub ORCID
Education
  • University of New South Wales
    University of New South Wales
    Bachelor (Honours) Student in Computer Science
    2021 - 2025
Selected Awards
Selected Publications (view all )
A Faster FPT Algorithm for Vertex Cover on Subcubic Graphs: A Randomized Automated Approach
A Faster FPT Algorithm for Vertex Cover on Subcubic Graphs: A Randomized Automated Approach

Katie Clinch, Serge Gaspers, Zixu He, Simon Mackenzie, Tiankuang Zhang

Submitted to STACS 2025 Spotlight

In this paper, we present a novel algorithm for solving the Vertex Cover problem on subcubic graphs in \(O(1.1313^k)\), beating the previous best running time of \(O(1.1442^k)\) due to Harris and Narayanaswamy (2022). We achieve this by combining two contributions of independent interest: 1) developing a new framework for the automated design of branching algorithms based on the idea of case analysis of local structures, and 2) introducing an extension of Measure & Conquer to randomized branching algorithms.

A Faster FPT Algorithm for Vertex Cover on Subcubic Graphs: A Randomized Automated Approach
A Faster FPT Algorithm for Vertex Cover on Subcubic Graphs: A Randomized Automated Approach

Katie Clinch, Serge Gaspers, Zixu He, Simon Mackenzie, Tiankuang Zhang

Submitted to STACS 2025 Spotlight

In this paper, we present a novel algorithm for solving the Vertex Cover problem on subcubic graphs in \(O(1.1313^k)\), beating the previous best running time of \(O(1.1442^k)\) due to Harris and Narayanaswamy (2022). We achieve this by combining two contributions of independent interest: 1) developing a new framework for the automated design of branching algorithms based on the idea of case analysis of local structures, and 2) introducing an extension of Measure & Conquer to randomized branching algorithms.

A Piecewise Approach for the Analysis of Exact Algorithms
A Piecewise Approach for the Analysis of Exact Algorithms

Katie Clinch, Serge Gaspers, Zixu He, Abdallah Saffidine, Tiankuang Zhang

WALCOM 2025 Spotlight

This paper presents piecewise analysis, a new general method that analyzes the running time of branching algorithms. We reanalyze two 17-year-old algorithms from Fomin et al. (2007) that solve 4-Coloring and #3-Coloring and we improve their running time from \(O(1.7272^n)\) to \(O(1.7207^n)\) and from \(O(1.6262^n)\) to \(O(1.6225^n)\) respectively.

[arXiv] [Code]

A Piecewise Approach for the Analysis of Exact Algorithms
A Piecewise Approach for the Analysis of Exact Algorithms

Katie Clinch, Serge Gaspers, Zixu He, Abdallah Saffidine, Tiankuang Zhang

WALCOM 2025 Spotlight

This paper presents piecewise analysis, a new general method that analyzes the running time of branching algorithms. We reanalyze two 17-year-old algorithms from Fomin et al. (2007) that solve 4-Coloring and #3-Coloring and we improve their running time from \(O(1.7272^n)\) to \(O(1.7207^n)\) and from \(O(1.6262^n)\) to \(O(1.6225^n)\) respectively.

[arXiv] [Code]

All publications