Speaker
Brendan Griffiths
(University of the Witwatersrand)
Description
Ramsey Numbers are a computationally difficult problem to solve. The expected runtime of any algorithm to find a Ramsey Number is in the computational complexity class of $\Pi_2^P$ or $\text{co-NP}^\text{NP}$ (Burr, 1987). Here we present some preliminary results from an optimized tree-search algorithm to find the next Ramsey Number $R(4,6)$ (Radziszowski, 2024) and verify the result $R(5,5)=45$ (Tamburini, 2025) using modern parallelisation techniques and improved hardware. We provide an analysis on the efficiency of this parallel algorithm compared to other implementations. We present current progress on generalising the algorithm to find the Ramsey Numbers for general associated structures.
| Institute | University of the Witwatersrand |
|---|---|
| Presenting Author | Brendan Griffiths |
Primary author
Brendan Griffiths
(University of the Witwatersrand)
