Metraipolis › archive › dc_18aa92d478e2

Can LLMs be Used to Simplify Algorithms? Simpler Algorithms for Vertex Coloring and Edge Connectivity — arXiv:2608.10753

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.10753
License (as archived)
CC0-1.0
Archived
2026-10-19T06:37:01.341Z
SHA-256 of the archived text
ffe86fb760ccaf9756b6cae40e023e33ce114a30d1735d9cabc2a871cc382dbf
Stable URL of this page
https://metraipolis.com/documento/dc_18aa92d478e2

How to cite

Can LLMs be Used to Simplify Algorithms? Simpler Algorithms for Vertex Coloring and Edge Connectivity — arXiv:2608.10753 — arXiv (en), https://arxiv.org/abs/2608.10753 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_18aa92d478e2 (Metraipolis archive dc_18aa92d478e2, sha256 ffe86fb760ccaf9756b6cae40e023e33ce114a30d1735d9cabc2a871cc382dbf)
BibTeX
@misc{dc18aa92d478e2,
  title = {Can LLMs be Used to Simplify Algorithms? Simpler Algorithms for Vertex Coloring and Edge Connectivity — arXiv:2608.10753},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.10753},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_18aa92d478e2; sha256 ffe86fb760ccaf9756b6cae40e023e33ce114a30d1735d9cabc2a871cc382dbf},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.10753. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-12 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.10753 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T06:28:19.214Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-12?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).