This paper studies how well LLMs can simplify algorithms by evaluating three different LLMs on ten different algorithmic problems, and results in the discovery of two novel algorithms.
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.
Coloring the vertices, edges or faces of a graph so that no two adjacent elements share a label is among the oldest problems in graph theory, and one of the few whose reach extends into exam timetables and wireless spectrum allocation as it does into pure combinatorics. This survey draws together the problem’s theoretical core – vertex, edge, face, list and total coloring – with the algorithms built to solve it and the industries that now depend on those algorithms. Because coloring is NP-hard, we trace the field’s progression from exact and greedy methods (Welsh-Powell, DSATUR, backtracking) through metaheuristics that trade optimality for scale (genetic algorithms, tabu search, simulated annealing, ant colony and artificial bee colony optimization), to the graph neural network and quantum-inspired solvers that have emerged in recent years. Rather than treating theory, algorithms and applications as separate literatures, we connect them directly: each application – examination and crew scheduling, frequency assignment, compiler register allocation, cartographic map coloring – is traced back to the specific coloring variant and algorithm family the literature actually uses, while the algorithm families themselves are compared head-to-head on complexity, solution quality and scalability rather than catalogued one at a time. This comparative structure, together with its coverage of recent learning-based solvers, is what distinguishes this survey from the standard references on the subject. We close by outlining where the field’s open problems remain, from long standing conjectures to the still-unanswered question of whether learned heuristics can match classical methods at real-world scale.
Jisha Ann Abraham, C. Wilfred, Thomaskutty Stephen· International journal of com...· 0 citations
We give a new $O(\log n)$ approximation algorithm for Node Weighted Steiner Tree and Node Weighted Steiner Forest. Our algorithm matches the bounds of Klein&Ravi [J. Algorithms'95] which are best possible unless P = NP, but have the advantage that they work in the online setting when the terminal pairs are revealed in random order. To obtain our results, we combine the LearnOrCover framework due to Gupta, Kehne, Levin [FOCS'21] with the Augmented Greedy algorithm of Berman&Coulston [STOC'97] for online edge-weighted Steiner Forest. Neither algorithm suffices on its own, but the analyses dovetail to imply our guarantee. Run offline, the algorithm reduces to a very simple randomized rounding scheme that (in spirit) reduces Node Weighted Steiner Forest to Edge Weighted Steiner Forest, and we hope this idea finds further applications.
Joseph Koutsoutis, Jessica Lerner, Roie Levin et al.· 0 citations
We show that a simple extension of the randomized greedy maximal independent set algorithm yields a constant approximation for the maximum matching problem. The algorithm is a simplification of an algorithm used by Assadi et al. [JACM 2026] in the context of processing data streams in the dynamic setting where edges may be inserted and deleted. In contrast to the previous work, our analysis avoids consideration of fractional matchings and yields a significantly shorter and more direct proof of the approximation factor for the basic algorithm.
The Pettie-Su's algorithm is adapted so that the resulting LLL instances can be solved in $\log^{O(1)}\log n$ rounds, by employing the'resilience'definition of Davies [SODA 2023].
This work presents a novel algorithm named HP-MC that, like prior approaches, is based on the branch and bound search, but which outperforms the leading maximum clique codes on large sparse graphs of various topologies by up to 10x on average.
Cameron Bradley, M. Burtscher· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
