Can LLMs be Used to Simplify Algorithms? Simpler Algorithms for Vertex Coloring and Edge Connectivity

Abstract

Having simple algorithms is important for the practical adoption of new algorithms. However, simplifying existing algorithms is a field that does not usually receive a lot of attention from the theoretical computer science community. It also seems like a task that LLMs might perform well. Thus, in this paper we study how well LLMs can simplify algorithms by evaluating three different LLMs on ten different algorithmic problems. Our study resulted in the discovery of two novel algorithms. The first algorithm is for vertex coloring, and gives a refined bound for the so-called asymmetric palette sparsification proposed by Assadi and Yazdanyar [SOSA 2025] with a very simple proof. The second is a further simplification of the algorithm of Saranurak [SOSA 2021] for deterministically computing a global minimum cut in an unweighted graph using expanders.